Test Markdown

滑动窗口

二分

二分

双指针

前缀树

树专题

图专题

最短路径问题

启发式搜索

堆

多路归并

合并 n 个有序链表极其相似

Kruskal

Dijkstra

贪心问题

| 题目 | | | | ———————————————————— | ———————————————————— | —- | | 435. 无重叠区间 | 按照结束时间从小到大排序，快慢指针用来判断是第二个起始时间小于第一个结束时间，如果是大于等于left=right而不是left=left+1 | 5.5 | | 455. 分发饼干 | 孩子的胃口从小到大，饼干的尺寸从小到大 | 5.4 | | 45. 跳跃游戏 II | 汽车加油问题，统计边界范围内，哪一格能跳得更远，统计下一步的最优情况，如果到达了边界，那么一定要跳了，下一跳的边界下标就是之前统计的最优情况maxPosition，并且步数加1 | 5.7 | | 55. 跳跃游戏 | 在这个过程中，贪心的思想体现在每一步决策上。我们从第一个位置开始，计算出当前位置所能到达的最远距离，即maxJump。然后看下一个位置能否到达这个maxJump，如果可以，就更新maxJump为新位置所能到达的最远距离；如果不能到达，直接返回false。 | 5.7 | | 1306. 跳跃游戏 III | DFS | 5.7 | | 1345. 跳跃游戏 IV | indexMap[arr[cur.index]] 中存储了值为 arr[cur.index] 的数在原数组中出现的所有下标，也就是从当前节点可以直接跳转到的所有节点。每当我们遍历完所有从当前节点可以抵达的节点的时候，将这些节点的下标从 indexMap[val] 中移除，以保证后续的遍历不会重复访问已经访问过的节点。BFS+贪心 | 5.7 | | 1340. 跳跃游戏 V | 动态规划，得到高度从小到大的序号，依次访问这些序号，并且判断旁边的邻居是否比自己小或者右边的邻居是否比自己小，小就更新该位置最多可以访问的下标。如何得到从小到大访问的序号，一个序号index[i]=i,然后就是对应的array[index[i]] < array [index[j]] | 5.8 | | 1696. 跳跃游戏 VI | len(queue)>0 && DP[queue[len(queue)-1]] < DP[i] 类似 3 2 1 4遇到四的时候删除前面的3 2 1都是从尾部开始删除，维护一个单调递减的index ，里面存储的是的单调递减的DP的下标 | 5.8 | | 1871. 跳跃游戏 VII | ` start := max(cur+minJump, farthest+1)优化后的BFS可以通过 | 5.8 | | [452. 用最少数量的箭引爆气球](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/) | *每次选择局部最优解* points[i][1] < points[j][1]按照左端点坐标从小到大排序。 如果当前气球的左端点小于等于 end，说明它与前一个气球有重叠部分，此时我们不需要增加箭的数量，因为这个区间已经被覆盖了。 如果当前气球的左端点大于 end，说明它与前一个气球没有重叠部分，此时我们需要增加箭的数量，将当前气球的右端点赋值给 end。 | 5.8 | | [605. 种花问题](https://leetcode.cn/problems/can-place-flowers/) | 为了确保边界情况的正确性，我们需要在花坛左边、右边各增加一个未种植的位置，即 bed = [0] + flowerbed + [0]。这样可以保证每个位置都有前一个位置和后一个位置可以供我们检查。 | 5.8 | | [122. 买卖股票的最佳时机 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/) | 当前价格高于前一天价格，说明股票价格在上涨，我们就应该在前一天买入，在当前天卖出，这样可以获得当天的利润。而如果当前价格低于等于前一天价格，说明股票价格不变或者下跌，此时我们应该不进行任何操作，继续向后扫描即可 | 5.8 | | [121. 买卖股票的最佳时机](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/) | 在买卖股票时，我们应该尽可能地以更低的价格买入，以更高的价格抛售，那么我们在遍历股票价格数组时，可以通过记录当前的最低价格来确保能够以相对较低的价格进行买入，而如果在之后的某个时间找到了更高的股票价格，我们则可以考虑抛售股票并计算利润，维护一个全局的最大利润，不断更新即可。 | 5.8 | | [188. 买卖股票的最佳时机 IV](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/) | 贪心+DP dp[i][j] = max(dp[i][j-1], prices[j]-maxDiff)` 第i次卖出，第j天卖出获得的利润，要么是前j-1天的最大利润，要么是这次买出获得的最大的利润，那么就是这次买出的价格-历史低价。更新历史低价，历史低价是这次的买出价格-前i-1次的买出利润。第i天结束时最多完成了j次交易且手上没有股票 = 前一天也没持有股票 /前一天持有股票但在当天卖出。第i天结束时最多完成了j次交易且手上持有股票时的最大收益，可以由前一天也持有股票和前一天没有持有股票但在当天买入两种情况中取较大值得到 | 5.9 |