346. Moving Average from Data Stream
Google电面题，15min，bug-free。考虑优化时间复杂度可以过关，考虑滚动数组会加分。
最直接的想法自然是弄一个list或者array，每次来一个数就放进去一个，然后再计算window size内的所有数的平均值。
这样做的时间复杂度是O(n * size)，如果我们利用前缀和的话，可以把时间复杂度降低至O(n)，当然这题最低也就是O(n)了，因为每一个进来的数你至少要读一次。
前缀和顾名思义就是前面总共的和，sum[i] = d[1] + d[2] + d[3] + ... + d[i]
如果window size是 x 加到 y 的话，我们有d[x] + ... + d[y] = sum[y] - sum[x - 1]。
所以说如果我们维持一个前缀和，就可以在O(1)的时间内计算出我们要的平均值。如下面的代码。
public class MovingAverage {
double[] sum;
int size;
int count;
/** Initialize your data structure here. */
public MovingAverage(int size) {
sum = new double[1000000];
count = 0;
this.size = size;
}
public double next(int val) {
count++;
sum[count] = sum[count - 1] + val;
if (count <= size) return sum[count] / count;
else return (sum[count] - sum[count - size]) / size;
}
}
至此我们降低了时间复杂度的问题，那么空间复杂度怎么办？上面的代码中关于前缀和数组的声明看起来也十分的丑，因为我们不知道到底要读几个数，所以要准备一个尽量大的数组，上面是一百万个元素空间。但是这始终不是一个好的解决方案，更何况很占用空间。
其实在计算前缀和的时候就应该能够注意到，我们在计算后面的平均值的时候，前面用过的前缀和就失去价值了。所以如果 window 大小是 size 的话，其实我们一共只需要 size + 1 个元素空间就够了。比如说我们计算大小为 3 的 window 的平均值，每次算的时候：
sum(3) - sum(0)
sum(4) - sum(1)
sum(5) - sum(2)
sum(6) - sum(3)
sum(7) - sum(4)
我们只用到了 4 个元素，当sum(0)空出来之后，可以把sum(4)放到sum(0)的位置去。只需要对下标取模就可以做到。
这就是滚动数组。
别忘了计算结果是double，不是int。
public class MovingAverage {
double[] sum;
int count;
public MovingAverage(int size) {
sum = new double[size + 1];
count = 0;
}
public double next(int val) {
count++;
sum[count % sum.length] = sum[(count - 1) % sum.length] + val;
if (count < sum.length) return sum[count] / count;
else return (sum[count % sum.length] - sum[(count - sum.length + 1) % sum.length])
/ (sum.length - 1);
}
}
看起来有点乱，对于每一个涉及到的下标都进行size + 1的取模。两点注意：
写完主体程序没问题了之后再加滚动数组，上来直接写滚动数组容易乱
滚动数组如果没有把握的话，就开大一点，size + 2甚至size + 10，这是保证不会出错的方法
这道题的答案是用queue做的，但是实际上queue的底层也是用这种滚动数组的方法实现的。
public class MovingAverage {
int size;
Queue<Integer> queue;
double sum;
/** Initialize your data structure here. */
public MovingAverage(int size) {
queue = new LinkedList<>();
this.size = size;
sum = 0;
}
public double next(int val) {
sum += val;
if (queue.size() == size) {
sum = sum - queue.poll();
}
queue.offer(val);
return sum / queue.size();
}
}
170. Two Sum III - Data structure design
这题的testcase有点恶心人。
class TwoSum {
Map<Integer, Integer> map;
/** Initialize your data structure here. */
public TwoSum() {
map = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
map.put(number, map.getOrDefault(number, 0) + 1);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int num1 = entry.getKey();
int num2 = value - num1;
if (num1 == num2 && entry.getValue() > 1 || num1 != num2 && map.containsKey(num2)) return true;
}
return false;
}
}
/**
* Your TwoSum object will be instantiated and called as such:
* TwoSum obj = new TwoSum();
* obj.add(number);
* boolean param_2 = obj.find(value);
*/
146. LRU Cache
class LRUCache {
class Node{
private Node prev;
private Node next;
private int key;
private int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, Node> map;
private int capacity;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node curt = map.get(key);
curt.next.prev = curt.prev;
curt.prev.next = curt.next;
moveLast(curt);
return map.get(key).value;
}
public void put(int key, int value) {
if (get(key) != -1) {
map.get(key).value = value;
return;
}
if (map.size() == capacity) {
Node curt = head.next;
curt.next.prev = head;
head.next = curt.next;
map.remove(curt.key);
}
Node node = new Node(key, value);
map.put(key, node);
moveLast(node);
}
private void moveLast(Node node) {
node.prev = tail.prev;
tail.prev.next = node;
node.next = tail;
tail.prev = node;
}
}