多做多说

Recap of Scala tutorial

A cheatsheet that gets you started. The original tutorial can be found here Main function The normal version: object Hello { def main(args: Array[String]) = { println("Hello, world") } } The version that extends App trait object Hello extends App { println("Hello, world") } // To access args. object Hello extends App { if (args.size == 0) println("Hello, you") else println("Hello, " + args(0)) } As you may notice: no ; needed as ending in Scala....

详解水塘抽样(Reservoir sampling)

一个场景当内存无法加载全部数据时，如何从包含未知大小的数据流中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。水塘抽样把上述问题具体化为给定一个未知大小数组data[]，从中选取k个数，要求每个数被选中的概率相等。假设数组长度为n，则每个数被选中概率应为k/n。策略是：对最前面k个数，直接放到数组chosen[]即chosen[i] = data[i] 0 <= i < k。对data[i], i >= k，先生成个[0...i)间的随机数(左闭右开)，假设rand(0, i) = j，则如果j < k,则做替换chosen[j] = data[i]。否则，nothing happens. 如此反复直到结束。 Java实现如下： public class ReservoirSampling { private Random rand = new Random(); public int[] sampling(int[] data, int k) { int[] chosen = new int[k]; int i = 0; for (int d : data) { if (i < k) { chosen[i] = d; } else { int j = rand....

Java集合速览

A quick review of Java Collection and Map key methods. Array based collections usually have: Method Time complexity add O(1) insert(int index) O(N) remove O(1) remove(int index) O(N) find(Object value) O(N) PriorityQueue, TreeSet and TreeMap are implemented based on balanced tree, thus: Method Time complexity offer O(logN) poll O(logN) peek O(1) Overview via a diagram Collections extends Iterable which has below key methods: Method Description boolean hasNext() This method returns true if the iterator has more elements....

详解线段树之进阶(Segment Tree)

懒更新(lazy update) 上文留下一个问题没有解决，就是对一个区间更新。对一个元素的更新复杂度为O(N),N为数组长度,按上文方法对区间更新，则复杂度为L*O(N), L为区间长度。另外，更新原数组元素，是从线段树中对应的叶子节点，一路向上更新到根节点。如果所要更新的区间有很多公共祖先节点，那么这些节点每次都需要被更新一次。如图中如果我们要更新数组中的2, 8, 6分别+5, +1, +9，可以看到图中公共节点如19会更新2次，37则有3次。另外，在实际应用中，可能只是某些热点数据会频繁被读取，而大部分数据是在冷宫常年不见天日。有些更新没有必要立即落实到每一个节点，而可以在其被读取时再落实更新。这就是懒更新的登场时刻。基于数组的实现既然需要将更新延后落实，那么就需要保存这些更新，所以需要一个与tree长度一致的lazy数组来保存对应节点没有落实的更新。代码如下。几个注意点：进入queryCore时，首先需要检查有无当前节点index的更新，如果有，先执行更新，清空该更新，然后继续，其余与正常线段树query区别。进入updateCore时，也是首先要检查有无当前节点index的更新，如果有，重复上面。另外，当更新范围[left, right]完全覆盖当前节点代表区间[segLeft, segRight]时，要再次执行更新，但这次update参数是newVal。这是关键点所在，执行完更新，就不用继续递归调用了，因为孩子节点的更新被保存在了lazy[leftChild]和lazy[rightChild]。下次再调用query或者update时，如果执行到节点leftChild或rightChild，则会执行之前保存的更新。 class SegmentTree { private int[] tree; private int[] lazy; private int n; public SegmentTree(int n) { this.n = n; int len = (1 << (1 + (int)(Math.ceil(Math.log(n) / Math.log(2))))) - 1; tree = new int[len]; lazy = new int[len]; } public int query(int left, int right) { return queryCore(left, right, 0, n - 1, 0); } public void update(int left, int right, int newVal) { updateCore(left, right, 0, n - 1, 0, newVal); } private int queryCore(int left, int right, int segLeft, int segRight, int index) { if (lazy[index] !...

详解线段树之入门(Segment Tree)

何为线段树线段树是基于要研究的数组而构建的数据结构，呈二叉树状。线段树的叶子结点就是所要研究的数组，非叶子节点表示数组的一段区间的某个性质的值。比如此区间的和，或者最大值最小值等等。为什么需要线段树呢？试想你需要设计一个功能，给定一个数组，需要你提供两个操作，一是更改某个元素，而是索引某个区间的和，或者最大值，或者最小值，这里以和举例。最直接也是最简单做法当然是直接在数组上操作，O(1)更新，O(N)索引和，N为区间长度。 class NumArray { public NumArray(int[] nums) { //TODO } // Updates nums[index] = val. public void update(int index, int val) { //TODO} // Gets sum of nums[left ... right]. public int query(int left, int right) { //TODO } } 再进一步，如果需要更新一个区间的元素呢，比如，nums[i] += val, for left <= i <= right。 class NumArray { // ... // Add val, for nums[i] with left <= i <= right public int add(int left, int right, int val) { //TODO } } 继续以上方法，就是遍历区间，一一更新，与索引相同复杂度:O(N)。...