《Cracking the Coding Interview》——第14章：Java—

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

2014-04-26 19:11

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

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

代码：

 1 // 14.6 Implement a circular array, which allows easy rotation and array access.
 2 // Combination of a vector and a rotation index.
 3 import java.io.PrintStream;
 4 import java.util.Vector;
 5 
 6 public class CircularArray<T> {
 7     public int rotateIndex;
 8     public Vector<T> v;
 9 
10     public CircularArray() {
11         v = new Vector<T>();
12         rotateIndex = 0;
13     }
14 
15     public T elementAt(int index) {
16         if (index < 0 || index > v.size() - 1) {
17             throw new ArrayIndexOutOfBoundsException();
18         }
19         return v.elementAt((index + rotateIndex) % v.size());
20     }
21 
22     public void add(T val) {
23         if (v.size() > 0) {
24             v.insertElementAt(val, (rotateIndex + v.size() - 1) % v.size() + 1);
25             if (rotateIndex > 0) {
26                 ++rotateIndex;
27             }
28         } else {
29             v.insertElementAt(val, 0);
30         }
31     }
32 
33     public void removeElementAt(int index) {
34         if (rotateIndex > 0) {
35             if (index < 0 || index > v.size() - 1) {
36                 throw new ArrayIndexOutOfBoundsException();
37             }
38             int tmp = v.size();
39             v.removeElementAt((index + rotateIndex) % v.size());
40             if (index >= tmp - rotateIndex && index <= tmp - 1) {
41                 --rotateIndex;
42             }
43         } else {
44             v.removeElementAt(index);
45         }
46     }
47 
48     public void rotate(int index) {
49         if (v.size() == 0) {
50             return;
51         }
52         index = (v.size() - (v.size() - index) % v.size()) % v.size();
53         rotateIndex = (rotateIndex + index) % v.size();
54     }
55 
56     public static void main(String[] args) {
57         CircularArray<Integer> c = new CircularArray<Integer>();
58         PrintStream cout = System.out;
59 
60         c.add(3);
61         c.add(4);
62         cout.println(c.v);
63         c.add(7);
64         cout.println(c.v);
65         c.rotate(2);
66         c.add(12);
67         c.add(25);
68         cout.println(c.v);
69         c.rotate(-1);
70         c.add(77);
71         cout.println(c.v);
72         c.removeElementAt(2);
73         cout.println(c.v);
74         cout.println(c.elementAt(0));
75     }
76 }