> For the complete documentation index, see [llms.txt](https://trance.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://trance.gitbook.io/blog/notes/oj-tricks.md). # 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 的一维数组即可，因为可以覆盖，但是算法书上 那个背包就不可以， 因为它还需要之前的数值，我们只需要俩个数值 即可。 ``` {% hint style="info" %} 总结一下，一般只是最优解，可以填表，但是不一定\~ 我觉得两者结合应该是最舒服的吧。 {% endhint %}