第二章 模拟算法和字符串处理技巧
1 Sliding Window Average from Data Stream
public class MovingAvage { int id, size; double[] sum; public MovingAvage(int s) { size = s; sum = new double[100000]; } public double add(int num) { id++; sum[id] = sum[id - 1] + num; if (id - size >= 0) { return (sum[id] - sum[id - size]) / size; } else { return sum[id] / id; } } }
使用滚动数组 1 缩减数组 2 写mod函数 3 所有用到数组的地方改变量
public class MovingAvage { int id, size; double[] sum; public MovingAvage(int s) { size = s; sum = new double[size + 1]; // 1 } int mod(int x) { // 2 return x % (size + 1); } // 3 public double add(int num) { id++; sum[mod(id)] = sum[mod(id - 1)] + num; if (id - size >= 0) { return (sum[mod(id)] - sum[mod(id - size)]) / size; } else { return sum[mod(id)] / id; } } }