《Cracking the Coding Interview》——第14章:Java——题目6

时间:2021-07-29 23:12:20

2014-04-26 19:11

题目:设计一个循环数组,使其支持高效率的循环移位。并能够使用foreach的方式访问。

解法:foreach不太清楚,循环移位我倒是实现了一个,用带有偏移量的数组实现。修改元素不一定能做到O(1)时间,但循环移位能在O(1)时间解决。不得不说,用不熟的语言写面试题,很难~~~

代码:

 // 14.6 Implement a circular array, which allows easy rotation and array access.
// Combination of a vector and a rotation index.
import java.io.PrintStream;
import java.util.Vector; public class CircularArray<T> {
public int rotateIndex;
public Vector<T> v; public CircularArray() {
v = new Vector<T>();
rotateIndex = 0;
} public T elementAt(int index) {
if (index < 0 || index > v.size() - 1) {
throw new ArrayIndexOutOfBoundsException();
}
return v.elementAt((index + rotateIndex) % v.size());
} public void add(T val) {
if (v.size() > 0) {
v.insertElementAt(val, (rotateIndex + v.size() - 1) % v.size() + 1);
if (rotateIndex > 0) {
++rotateIndex;
}
} else {
v.insertElementAt(val, 0);
}
} public void removeElementAt(int index) {
if (rotateIndex > 0) {
if (index < 0 || index > v.size() - 1) {
throw new ArrayIndexOutOfBoundsException();
}
int tmp = v.size();
v.removeElementAt((index + rotateIndex) % v.size());
if (index >= tmp - rotateIndex && index <= tmp - 1) {
--rotateIndex;
}
} else {
v.removeElementAt(index);
}
} public void rotate(int index) {
if (v.size() == 0) {
return;
}
index = (v.size() - (v.size() - index) % v.size()) % v.size();
rotateIndex = (rotateIndex + index) % v.size();
} public static void main(String[] args) {
CircularArray<Integer> c = new CircularArray<Integer>();
PrintStream cout = System.out; c.add(3);
c.add(4);
cout.println(c.v);
c.add(7);
cout.println(c.v);
c.rotate(2);
c.add(12);
c.add(25);
cout.println(c.v);
c.rotate(-1);
c.add(77);
cout.println(c.v);
c.removeElementAt(2);
cout.println(c.v);
cout.println(c.elementAt(0));
}
}