OJ Tricks

这里主要是一些题目的技巧总结。

min max heap usage

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值
排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之
后中间两个数的平均值。


一个大堆，一个小堆，保证 大堆的头永远比小堆的头最小，并且两者数量接近（差一，或者相
等）保存4个变量，两个堆的数量，以及堆的顶值，

min_size, max_size, min_top. max_top
当获得一个新的数，如果小于 min_top, 就放进 max_heap
中，但是可以判断一下和 max_top 的大小，这样可以更新它

然后在做判断， 是否 max_size > min_size, 
是的话，就把 max_top 放入 min_heap 中，它当然是最小的，所以可以更新

这时候，我们再更新， max_size, min_size, 这样即可保证两者数量接近
并且俩个堆也一定是连续的

max_top|   |min_top 两者构成的区间，在不停的移动~~ 两堆数量相近  

N 个有序队列的合并，

一个最小堆维持N个队列的当前头节点，每次从中取出最小的，
判断来自那个队列，将新的头节点放入，然后更新队列指针，
以此重复

还有一个用途 就是 图里面最小生成树的时候， 所以大小堆的
使用场景比较明显，就是需要找最大，或者找最小的时候，其它的
元素我们都不太在乎

找出数组 K 个小元素

同理，先拿K个元素放进最大堆，每次和 max_top  对比，
比他小则放入，头部则被 pop 出来，其实不一定要用堆~

DP

DP 很重要的思想在于，从 N -> N+1 或者能从 N -> N-1 ，另外 DP 代表的就是计算机思维，这是非常重要的，计算机的思维也是迭代的思维，这种思想其实非常的重要，我们永远都不会去寻找一个精确值，而是不断的从上一次值来推出下一个更加合适的值~

长度为 N 的区间，现在有 M 个 [xi, xi+1] 的区间，是判断能否覆盖，并且最少需要的
个数选出。

DP: 先考虑 0 - xi 的区间，然后考虑 x1 -> N
也就是选择从0出发，最长的一区间 len，然后考虑
len - N 以此类推，这是将区间砍成一份一份，其实
就是逼近的思想，操作就是将其余的区间都减去当前
已经覆盖的，重新排序， 然后问题又变成了
0 - (N-xi) 的问题，直到最后选择完毕~

全排列这里不说了，下面说说 ， AABCDD 的组合数计算

假设选 M 个数，我们选第一个数之后，马上变成选 M -1
个，这就是迭代（递归就是迭代的实现方式），

我们只需要记下，当前的位置即可，以及曾经选择过的字母
1.     A    -- 当递归回来，下一个是A，即会判定重复
2. A B C D D
第二层是可以选A的，不同层之间不需要判断重复，
关键是，比如选择了D之后，子递归已经处理完了。
然后下一个选D，我们就得判定重复，简单的说
就是函数体自己判断重复即可，子函数只需要知道有
哪些可以选择即可

如果说是有重复元素的重排列呢？ 很简单，我们
在 1 个元素的时候，不需要排列，
m个元素的时候， 我们将m 和 m-1 个元素都互换一次，然后
做 m-1 排列，
我们只需要保证， m  和 [m-1] 这个集合不出现重复的集合即可，
因为 A[m-1] 集合已经全排列过了
两种情况， 1. m  和 A[i] 相同，那是白费力气，上面说过已经排列过了
2. A[i-1]内有重复元素，m和它们都交换了，那就是出现了重复集合了。
所以， m 得维持一个集合，来判断跟他们交换与否，一个数组即可~

还有一类就是背包问题，
    0
   0 0
  0 0 0
 0 0 0 0
 比如上述的节点都有一个值（路径），然后从顶部出发，计算最小的路径，
 每次只能选择其左右的两个节点，其实可以抽象为一个矩阵
 0 0 0 0 
 0 0 0 
 0 0 
 0
 上面都有数值，这不就是填表么, 比较 x4 x7 x9 x10的大小即可
 x1   x2  x3  x4
 x5   x6  x7
 x8   x9
 x10  
 还有别的方案，就是多 -> 少，即最底出发，每次就可以淘汰掉一个节点
 也就是说， 第三层和第四层的组合数其实很少，俩俩比较就可以淘汰一个
 以此迭代。但是这里主要说的 少-> 多
 
 少 -> 多 也就是上面填表的过程，我们思想是这样的，
 我们在第 N 层，我们考虑，N - 1 层的最短路径，然后我们在把
 N 节点的长度，加上，选择出最小的
 
 所以问题就变成了，我们要算的就是，第一层怎么到第二层呢？
 以此类推。
 
 现在延伸一下，变成方格, M * N
 0 0 0 0
 0 0 0 0
 0 0 0 0
 那么上面的 多到少就不适用了，中间截断也只适合方形矩阵
 
 这个 a[i,j] = min{a[i-1,j], a[i, j-1]} + value(a[i,j])
 跟上面是一样的，还是填表，
 x1 x2 x3 x4
 x5 x6 x7 x8
 x9 .... 
 其实只需要长度为 N 的一维数组即可，因为可以覆盖，但是算法书上
 那个背包就不可以， 因为它还需要之前的数值，我们只需要俩个数值
 即可。

总结一下，一般只是最优解，可以填表，但是不一定~ 我觉得两者结合应该是最舒服的吧。