滑动窗口
题目 |
关键点/难点 |
时间 |
209. 长度最小的子数组 |
变化长度的滑动窗口,这个滑动窗口扩展右边界的条件是不符合sum < target ,所以往往内部需要一个循环来调整左边的的指针,更新窗口内部的值,以及更新全局的结果, |
6.5 |
904. 水果成篮 |
` 010 13030303030当遇到3的时 010都要删除,前面的当 len(window)>2`的时候,需要从左边开始缩小窗口直到窗口的大小符合条件。 |
6.5 |
76. 最小覆盖子串 |
|
|
209. 长度最小的子数组 |
|
|
438. 找到字符串中所有字母异位词 |
|
|
930. 和相同的二元子数组 |
slideWindow(nums, goal) - slideWindow(nums, goal-1) 滑动窗口+差分的思路来解决。因为内部是当sum > goal 的时候开始。开始缩小到sum <= goal 然后计算总和。 |
6.5 |
992. K 个不同整数的子数组 |
维护一个窗口,使得其中最多包含 k 个不同的整数。我们使用一个计数器 count 来记录满足条件的子数组的数量,初始值为 0。我们从左侧开始向右移动窗口,直到窗口中包含了超过 k 个不同的整数。然后,我们从左侧开始收缩窗口,直到窗口中包含了最多 k 个不同的整数。在此过程中,我们可以将每个包含最多 k 个不同整数的子数组的数量加入到计数器 count 中。以 right 为结尾的子数组的左侧边界可以是 left 到 right 中的任意一个位置,因此,以 right 为结尾的子数组的数量为 right - left + 1 最后为了得到恰好包含n个十数字,那么atMostKDistinct(nums, k) - atMostKDistinct(nums, k-1) |
6.5 |
978. 最长湍流子数组 |
滑动窗口问题:不断移动右边的指针,每次判断的时候,拿着arr[right]与arr[right-1]以及 arr[right]与arr[right+1]对比大小,如果符合就+1 不符合就left=right 边界条件是left==right 的时候,如果arr[left]==arr[left+1]对于相等的条件就右移指针。 |
6.5 |
1004. 最大连续1的个数 III |
技巧:left:=right-(window[0]+window[1])+1来定位left指针的位置,找到窗口中第一个为0的位置,移动的过程中不断的更新窗口的大小。 |
6.6 |
第3题-无重复字符的最长子串 |
window[s[left]]-- |
6.7 |
第159题-至多包含两个不同字符的最长子串 |
Plus |
|
第340题-至多包含 K 个不同字符的最长子串 |
Plus |
|
1234. 替换子串得到平衡字符串 |
for window['Q']<= k && window['W']<=k && window['E']<=k && window['R']<= k{res=min(res, right-left+1) window[s[left]]++ left++} window[left]++我是真不能理解 |
6.7 |
1248. 统计「优美子数组」 |
count =count+(right-left+1) +slideWindow(nums,k)-slideWindow(nums,k-1) 重出江湖 |
6.7 |
1658. 将 x 减到 0 的最小操作数 |
移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。简言之就是连续数组的值为numsSum - x= target 使得构成target的连续数组的最长,那么操作的次数就最小。 |
6.7 |
485. 最大连续 1 的个数 |
|
|
二分
题目 |
类别 |
难度 |
难点 |
上次复习时间 |
3 |
滑动窗口 |
mid |
|
|
76 |
二分 |
mid |
|
|
209 |
二分 |
mid |
|
|
438 |
二分 |
mid |
|
|
904 |
二分 |
mid |
|
|
930 |
二分 |
mid |
|
|
992 |
二分 |
mid |
|
|
978 |
|
|
|
|
1004 |
|
|
|
|
1234 |
|
|
|
|
1658 |
|
|
|
|
|
|
|
|
|
二分
题号 |
类别 |
难度 |
题目 |
上次复习时间 |
154 |
二分 |
hard |
|
|
153 |
二分 |
mid |
|
|
34 |
二分 |
mid |
排序数组查找元素的第一个和最后一个位置 |
4.12 |
35 |
二分 |
mid |
|
|
189 |
二分 |
mid |
|
|
81 |
二分 |
mid |
|
|
33 |
二分 |
mid |
|
4.11 |
658 |
二分/定长滑动窗口 |
mid |
找到k个最接近的元素 |
4.12 |
162 |
二分 |
mid |
寻找峰值 |
4.11 |
278 |
二分 |
mid |
第一个错误的版本 |
4.11 |
374 |
二分 |
mid |
|
4.11 |
69 |
二分 |
mid |
x的平方根 |
4.11 |
704 |
二分 |
mid |
二分查找 |
4.11 |
875 |
二分 |
mid |
爱吃⾹蕉的珂珂 |
4.12 |
475 |
二分 |
mid |
供暖器 |
4.12 |
1708 |
二分+贪心 |
mid |
面试题 17.08. 马戏团人塔 |
4.13 |
动态规划
双指针
前缀树
树专题
图专题
题目 |
方法 |
时间 |
547. 省份数量 |
标准遍历-图的遍历 |
4.18 |
802. 找到最终的安全状态 |
递归超时/反向图+出度 |
4.20 |
841. 钥匙和房间 |
判断是不是一棵树 |
|
1129. 颜色交替的最短路径 |
BFS 队列+len(queue) ,然后不断取出这k个节点。 |
|
329. 矩阵中的最长递增路径 |
BFS+DP DP 用来计算以某个点结尾的最长递增的长度 |
4.27 |
1042. 不邻接植花 |
BFS+全局染色存储+从未被染色的节点开始+双向边+存在孤立节点 |
4.27 |
207. 课程表 |
拓扑排序+从入度为0的点开始 |
4.27 |
743. 网络延迟时间 |
最短路径问题 核心:dis[]记录起点到每个点的最短的距离,并把节点入队列,堆队列排序,取出距离最小的点,去判断这个点再到它的邻接点的距离,。 一个集合 dis 来记录起点 s 到各个节点的最短路径长度 一个优先队列或堆来维护当前还未处理的节点 每次从堆中取出时间最小的点正好符合上述的要求,因为该节点距离起点 s 最近,并且它的最短路径长度已经被确定,可以作为最终结果之一 Dijkstra |
4.27 |
1063 |
最短路径问题 |
|
1135 |
最小生成树问题 |
|
1584 |
最小生成树问题 |
|
1319. 连通网络的操作次数 |
如果边少于n-1不能连通。最开始默认n个点就是个n个独立的集合。每连通两个点,group–最后的答案是group-1。 groupNum 表示当前图中的连通分量数,最终结果就是将所有的连通分量合并为一。在添加第一条边时,就可以将两个连通分量合并为一个,因此连通分量数减 1。假设有以下 4 个节点,它们之间的边还未建立:初始状态下,这 4 个节点分别处于独立的连通分量中。因此 groupNum 的初始值为 4。为了将所有连通分量合并成一个,需要建立 3 条边。具体来说: 首先连接节点 1 和节点 2,这时候它们就连通了,剩余连通分量数量减少 1,也就是 groupNum 减少 1,此时 groupNum 的值为 3。 然后连接节点 3 和节点 4,同样地,它们也连通了,此时 groupNum 的值减少到 2。 最后连接连通分量 1 和连通分量 2 即可,此时 groupNum 的值变成了 1,所有连通分量都已经被合并成了一个。 |
5.4 |
最短路径问题
题目 |
方法 |
时间 |
127. 单词接龙 |
BFS+hashMap存储单词可以构成的状态 |
4.21 |
200. 岛屿数量 |
BFS+visted[][]bool |
4.21 |
279. 完全平方数 |
BFS减枝优化 +DP动态规划 |
4.21 |
542. 01 矩阵 |
BFS从终点出发遍历,感觉像染色 那么其他点到终点的距离就是res[cur.x][cur.y-1] = res[cur.x][cur.y] + 1 0-1-1-1-1 和802一样都是从终点开始.802. 找到最终的安全状态 |
4.21 |
|
|
|
752. 打开转盘锁 |
BFS+HasMap 和127单词接龙有点类似,都是寻找某个状态对应的邻居状态,这么才能寻找到下一个需要注意的是一次只能转动一个,顺时针转+1,逆时针转+9。773 |
4.21 |
773. 滑动谜题 |
BFS+node.status +node.step+visited[string]bool |
4.21 |
207. 课程表 |
BFS+nodeInDegreeMap 统计儿子节点的入度+构建邻接表+遍历visitedMap判断存不存在某个节点没有被访问 |
4.22 |
210. 课程表 II |
|
|
启发式搜索
题目 |
关键点/难点 |
时间 |
1239 |
|
|
1723 |
|
|
127 |
|
|
752 |
|
|
堆
多路归并
题目 |
关键点/难点 |
时间 |
264. 丑数 II |
定义指针数组,然后都代表某个因数的指针被使用填充结果数组的一个数,那么就移动该因数指针。1-起始先将最小丑数1 放入队列。2-每次从队列取出最小值x ,然后将 x 所对应的丑数 2x 、3x 和 5x 进行入队 3-对步骤 2 循环多次,第 n 次出队的值即是答案。4-防止同一丑数多次进队,我们需要使用数据结构 Set 来记录入过队列的丑数。往后产生的丑数」都是基于「已有丑数」而来(使用「已有丑数」乘上「质因数」2 、3 、5 )。 |
|
313. 超级丑数 |
定义指针数组,然后都代表某个因数的指针被使用填充结果数组的一个数,那么就移动该因数指针。1-所有丑数的有序序列为 a1,a2,a3,…,an由以下三个有序序列合并而来:丑数 * 2 所得的有序序列1*2 2*2 3*2 4*2 5*2 丑数 * 3 所得的有序序列1*3 2*3 3*3 4*3 丑数 * 5 所得的有序序列1*5 2*5 3*5 4*5 使用三个指针来指向目标序列 arr的某一位下标,p2 ,p3 p5代表三个有序队列当前各自到了自己序列的哪个位置。 |
|
786. 第 K 个最小的素数分数 |
找到以每个元素为分母的链表,把,每个元素都放入到小顶堆里面,不断的弹出元素,直到第K个元素。 |
5.2 |
1508. 子数组和排序后的区间和 |
前缀和,把结果放入堆,然后弹出小的数 |
5.5 |
719. 找出第 K 小的数对距离 |
某个mid D1对应K个,还要继续往左找直到mid D2对应K个 |
5.2 |
1439. 有序矩阵中的第 k 个最小数组和 |
放入小顶堆的是node{pointer []int sum int} 其中node.pointer 保存着每一行取出数字的列坐标,知道列坐标和行坐标就可以知道新加入的数字和旧的被剪去的数字。 |
5.2 |
373. 查找和最小的 K 对数字 |
放入小顶堆的是node{pointer []int sum int} 其中node.pointer 保存着每一行取出数字的列坐标,知道列坐标和行坐标就可以知道新加入的数字和旧的被剪去的数字。 set 记录的是被访问过的坐标,那么其中set[key]bool key 是[2]int 类型 |
5.2 |
632. 最小区间 |
维持大小为K的堆,堆的最大值,靠新加入节点的值与堆的最大值不断比较。初始状态的最大值可以求出,然后最小的节点的值,不断被弹出,距离的最小值,不断更新大小为K的堆中元素大小的区间。 |
5.3 |
1675. 数组的最小偏移量 |
思路:维护最堆和堆的最小值。最开始处理的时候,把所有的奇数都乘以2加入到堆里面。偶数直接加入堆。对堆不断的除以2,直到堆顶为奇数。奇数只能乘一次2,偶数可以多次除以2,直到变成一个奇。操作时有限的。相当于数组的每个元素都是一个链表:1 2 3 4 1代表1-2-4-8 2代表2-1 3代表3-6-12 4代表4-2-1 |
5.3 |
871. 最低加油次数 |
把终点当作一个加油站加入到数组,然后找到终点应该存在的位置,在循环中,不断的判断当前知否能到达下一站,如果能到达下一站,那么就消耗富有,如果不能到达下一站就不断的弹出历史中的加油站台,加油直到可以到达下一站。事后诸葛 |
5.4 |
1488. 避免洪水泛滥 |
把晴天入队列,记录晴天是第几天,把雨天入MAP记录改天是在往哪个湖加水,并且给湖加水的日期,因为,找到的晴天必须是该湖填完水之后。事后诸葛 |
5.4 |
973. 最接近原点的 K 个点 |
最小堆 |
5.4 |
347. 前 K 个高频元素 |
最小堆 |
5.4 |
剑指 Offer 40. 最小的k个数 |
最小堆 |
5.4 |
|
|
|
合并 n
个有序链表极其相似
Kruskal
Dijkstra
题目 |
关键点/难点 |
时间 |
1631. 最小体力消耗路径 |
|
|
1654. 到家的最少跳跃次数 |
BFS解决的最短路径问题A是向前跳。B是向后跳。上一步是往后跳而且再往后跳会跳到 forbidden 数组中的位置,则不能再往后跳。记录同一种状态是否被访问过,被访问过的则不在加入 |
5.6 |
1631. 最小体力消耗路径 |
定义全局记录着起点每个点的最小的消耗,只有在小于全局的这个值的时候,才会把他放入到队列中间,上下左右四个方向就相当于是图中的邻居,邻居A与B只有在小于全局Dis[B]的情况下,才会被加入到堆中 |
5.6 |
|
|
|
贪心问题
| 题目 | | |
| ———————————————————— | ———————————————————— | —- |
| 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 |
回溯
题目 |
关键点/难点 |
时间 |
79. 单词搜索 |
defer func() { visited[i][j] = false }() 的作用是在当前函数返回之前执行这段代码,无论函数是正常返回还是异常返回。这保证了在 DFS 函数返回时,visited 标记一定会被重置为 false,避免了在递归回溯过程中出现 visited 标记不正确的问题。+减枝 |
6.3 |
212. 单词搜索 II |
如果某些单词含有相同的前缀,但是如果找到一个就直接返回了,那么得到的结果一定是不全的+减枝 减枝的关键是:避免根本不是答案的递归。对回溯算法进行记忆化递归的思路是把对应状态的结果存储起来,但是如果对应状态的结果用不了,那么存起来也是没用。 |
6.3 |
401. 二进制手表 |
方法1:主要是通过双循环实现,遍历hour 和minute 在循环内部计算1的个数countBit(hour)+countBit(minute) 方法2:回溯-10个灯中选择n个 choose(0, 0, num, []int{}) 可以把10个里面选n个的问题转化为9个里面选n-1个 |
6.3 |
78. 子集 |
典型的组合问题。 |
6.3 |
816. 模糊坐标 |
求两个数组的笛卡尔积。先按照逗号拆分,然后按照小数点拆分,在拆分的时候如果遇到不合法的数字就过滤掉。 |
6.3 |
52. N 皇后 II |
假设行A是行B的上一行,rowB-colB, rowB+colB 与 rowA-colA, rowA+colA 的关系是对角线0 -1 -2 -3 -4 和1 0 -1 -2 -3 值相等刚好互为对角线。因此DFS的模版里面状态参数为DFS(row int, path []int, cols map[int]bool, left map[int]bool , right map[int]bool) left 记录上一行左对角线被占用的位置, right 记录上一行右对角线被占用的位置,cols map[int]bool 记录被占用的列。 |
6.4 |
1255. 得分最高的单词集合 |
` DFS(i, total)i代表words的下标,total。DFS内部Words[i] 这个单词选择或者是不选都要去尝试。在选择分支,对于Words[i] 单词的所有字母,如果字母统计表都满足消耗,那么就更新 total ,变为了: DFS(i+1, total).在判断的时候最关键的代码是:当字母统计表中某个字母不够的时候: for j, c := range Words[i] { for _, m := range Words[i][:j] {Left[m-‘a’]++} }撤销消耗操作..并且在DFS结束的时候也要 for _, c := range Words[i]{Left[c-‘a’]++}撤销消耗的单词` |
6.4 |
93. 复原 IP 地址 |
感觉像枚举而不是回溯。 |
6.4 |
|
|
|
位运算
题目 |
关键点/难点 |
时间 |
136. 只出现一次的数字 |
全员异或。因为相同的两个数字异或得到0,0和任何数异或都是任何数 |
6.7 |
137. 只出现一次的数字 II |
通过一个number,来记录每一位数出现的次数,然后最终把抵消后剩余的1放到对应的位数上 res |= (number) % 3 << i |
6.7 |
268. 丢失的数字 |
方法1sum 记录出现的数字的和,count 记录总的和,count -sum 得到丢失的数字。方法2:填充集合,使得每个数字数出现偶数次,那么异或就会得到的缺失的数 |
6.7 |
231. 2 的幂 |
与 位运算,统计1的个数。 |
6.7 |
191. 位1的个数 |
与 位运算,统计1的个数。 |
6.7 |
645. 错误的集合 |
没有用异或,可以说是记录非重复数字的和,然后计算总和,总和-非重复数字的和得到缺市的数字 |
6.7 |
260. 只出现一次的数字 III |
首先计算所有数的异或结果xor = 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 4 = 3 然后找xor最低位的1,也就是xor & -xor。3的二进制是011, -3的二进制是100, 所以3 & -3 = 1,diff = 1。 有了diff之后,我们就可以按那一位是否为1来分组了。 n & diff == 0 的情况,意思是n在那一位上是0,所以属于一组。异或结果就是x = 1 ^ 2 ^ 2 = 1 n & diff != 0 的情况,意思是n在那一位上是1,所以属于另一组。异或结果就是y = 3 ^ 4 = 7 于是我们得到的两个只出现一次的数就是x = 1和y = 7。还是不能理解 |
6.7 |
190. 颠倒二进制位 |
result = result<< 1 将结果左移一位,空出最低位。result = result|uint64(num & 1) 将num的最低位(num & 1)与result的最低位或运算,结果存入result的最低位。num = num >> 1将num右移一位,舍弃最低位,继续处理下一位。 |
6.8 |
338. 比特位计数 |
循环得到每个数字的二进制中1的个数。动态规划dp[6] = dp[6 & 5] + 1 = dp[4] + 1 = 1 + 1 = 2 于是有:dp[i] = dp[i&(i-1)] + 1 。 |
6.8 |
1072. 按列翻转得到最大值等行数 |
按照贪心来解决的思路似乎并不是很清晰,flipRow(row) 得到原状态和翻转后的状态,如果cnt[翻] > cnt[原] 翻转++ |
6.8 |
|
|
|
小岛问题
题目 |
关键点/难点 |
时间 |
200. 岛屿数量 |
联通块的求解,DFS原地改变岛屿,当 Grid[i][j]=='0' 的时候返回 |
6.8 |
695. 岛屿的最大面积 |
DFS 原地修改Grid[i][j]=0 |
6.8 |
1162. 地图分析 |
先把为1的点标注为已访问,BFS 从所有为1的点开始遍历,向外遍历。每遍历一层就是距离加1,与之前的不同的是queue = queue[size:]一次性弹出所有等价的点。我们首先将所有的陆地单元格加入队列中,距离为0(有点像拓扑,拓扑是入度为0的点)。然后,我们从队列中取出第一个单元格,遍历其周围的4个单元格,如果这些单元格是未访问过的海洋。 |
6.8 |
463. 岛屿的周长 |
从上往下遍历,对于每个格子,判断他的上面和他的左边是否是1,如果是相邻的两个格子都要减去2。很巧妙!!!! |
6.8 |
959. 由斜杠划分区域 |
查并集!!很变态的一道题。yue |
6.8 |
|
|
|