# 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 %} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://trance.gitbook.io/blog/notes/oj-tricks.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.