基础
数组
4. 寻找两个正序数组的中位数
33. 搜索旋转排序数组 直接使用二分法
287. 寻找重复数 dict
34. 在排序数组中查找元素的区间 取开始下标(mid = (l + r) // 2); 取结束下标(mid = (a + b + 1) // 2)
矩阵
240. 搜索二维矩阵 II 从左下/右上开始search, O(m+n)
378. 有序矩阵中第K小的元素 依次添加右和下，pop出其中较小的，每次pop k-1，pop k次返回
其他
378. 二叉搜索树中第K小的元素 中序遍历从小到大，取nums[k-1]
69. X的平方根 在[0, x]中二分查找
链表
基础题
206. 反转链表
重难点 (M->H)
138. 复制带随机指针的链表 di[node] = Node, key为原节点，val为新节点, di[node].next = di.get(node.next), O(2n)
21. 合并两个有序链表 递归，迭代(dummy_node)
23. 合并K个排序链表 for i in range(0, cnt-interval, interval*2)
25. K 个一组翻转链表 cnt++, cnt--
双指针技巧
141. 环形链表
142. 环形链表 II
160. 相交链表 di
19. 删除倒数第N个节点 快指针先走n步
其他
234. 回文链表 left数组, left从后往前，指针从前往后，依次对比，slow, fast = head, head.next
328. 奇偶链表 保存下even_head, odd.next, even.next = odd.next.next, even.next.next
2. 两数相加 迭代(dummy_node), 最后不要忘了 if carry>0: h.next = ListNode(1)
148. 排序链表 mergesort (slow, fast找到mid，再分别mergesort); merge dummynode
注：一般要分为两段的链表的双指针slow,fast = head, head.next; 不需要分为两段的slow,fast = head, head
字符串
滑动窗口
76. 最小覆盖子串 - M while all(map(lambda x: s_c[x] >= t_c[x], t_c.keys())):
3+. 无重复字符的最长子串 - M
340. 至多包含 K 个不同字符的最长子串 - H if not di[s[start]]: di.pop(s[start]) # 记得pop if value == 0
DP
5. 最长回文子串 - M dp[i][j], dp[0][0]=1, 要for r再for l以确保dp[i+1][j-1赋值
1143. 最长公共子序列 - M dp[i+1][]j+1], dp = (max(dp[i-1][j], dp[i][j-1])) or dp[i-1][j-1]+1
91. 解码方法 dp[i] = dp[i-1] + dp[i-2] (有条件的), 1. s[i] != "0"; 10<=s[i-1:i+1]<=26
其他高频题
28. 实现 strStr() - E
14. 最长公共前缀 - E 先排序再比较first,last; for z in zip(*strs): if len(set(z)) == 1:res += z[0]
125. 验证回文串 - E s[start].isalnum()
49. 字母异位词分组 - M di["".join(sorted(s))].append(s)
其他杂题
8. 字符串转换整数 (atoi) - M try: int(s[:idx]) except: break
227. 基本计算器 II stack存数字和+-*/，数字一添加结束就看能不能做*/，最后一起算+-
二叉树
二叉树的构造
297. 序列化与反序列化 - H se: return " ".join(res); de: nums = iter(data.split()), num = next(nums)
144. 二叉树前序遍历 根左右
94. 二叉树中序遍历 左根右
145. 二叉树后序遍历 左右根; 迭代(dfs+stack从上到下右到左)：r, stack = [], [root] while stack:
102. 层序遍历 单队列，q = deque([(root, layer)])，q.popleft()
103. 锯齿形层次遍历 双队列, cur, nex = deque([root]), deque()
二叉树的对角线遍历 递归，helper(node, layer)
105. 前序与中序构造二叉树 递归，自调，idx = inorder.index(preorder[0])
106. 中序与后序构造二叉树
高频题目
101. 对称二叉树 helper: isMatch(left, right)
116. 填充每个节点的下一个右侧节点指针 对于任意一次递归，只需要考虑如何设置子节点的 next 属性
117. 填充每个节点的下一个右侧节点指针 II 思路同上，在l&r的时候先设置好l，追加设置r or l，很复杂多看看
104. 二叉树的最大深度 return max(maxdepth(root.left), maxdepth(root.right))+1
662. 二叉树最大宽度 self.left[], 每层碰到的第一个节点为left, dfs(node, layer, pos*2(+1))
543.二叉树的直径 helper: maxgain, self.res = max(left + right + 1, self.res)
236. 二叉树的最近公共祖先 helper(root), if left + right + mid >=2: res, return left or right or mid
113. 路径总和 II
437.路径总和 III
124. 最大路径和 - H helper: maxgain, self.res = max(left + right + root.val, self.res)
二叉搜索树
98. 验证二叉搜索树 helper(root, low = float("-inf"), high = float("inf"))
426. BST转排序的双向链表 中序, 处理当前节点，last.right = cur, cur.left = last
450. 删除BST中的节点 - M 找到后三种情况, 无子节点/一个子节点/有两子结点(max,remove_max)
删除区间内的节点
堆
347. 前 K 个高频元素 heapq.nlargest(k, c.keys(), key = c.get)；长度为k的堆
215. 数组中的第K个最大元素 堆；二分搜索牛逼
378. 有序矩阵中第K小的元素 堆，klogk: 一次添加右和下，pop出其中较小的，每次pop k-1，pop k次返回
218. 天际线问题
动态规划
基础篇
数学系列
300. 最长上升子序列 dp[n], if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1)
53. 最大子序和 dp[n], dp[i] = max(nums[i], dp[i-1] + nums[i])
152. 最大乘积子序列 dp[n][2], return max(dp, key=lambda x:x[1])[1]
279. 完全平方数 dp[n+1], 找零钱问题
其他
70. 爬楼梯 dp[n+1], dp[0], dp[1], dp[2] = 0, 1, 2 ；dp[i] = dp[i-2] + dp[i-1]
198. 打家劫舍 dp[n], dp[i] = max(dp[i-1], dp[i-2]+nums[i])
62. 不同路径
背包问题
dp对容量的init都是dp[v+1], 从空开始init
如果要减少空间的话，把dp[i]省掉，dp[v+1]的循环逆序
01背包问题
416. 割等和子集
494. 目标和 di={0:1}, nex_di, di.get(s, 0)
完全背包问题
322. 零钱兑换 if i in coins: dp[i] = 1
377. 组合总和 IV if i-c>=0: dp[i] += dp[i-c]
二维费用的背包问题
474. 一和零 dp[i][j] = max(dp[i][j], dp[i-c["0"]][j-c["1"]]+1)
进阶算法
回溯算法
46. 全排列 used = [False]*len(nums)
78. 子集 for j in range(i, len(nums)): backtrack(track+[nums[j]], j+1)
22. 括号生成 for p in ["(", ")"]: if counter[p] < n:
131. 分割回文串 for i in range(1, len(s)+1): if s[:i] == s[:i][::-1]: backtrack()
图：拓扑排序和Union Find
Union Find if self.parent[idx] != idx: self.parent[idx] = self.find(self.parent[idx])
200. 岛屿数量 uf = UnionFind(row*col+1) dummy_node = row*col
323. 无向图中连通分量的数目
拓扑排序 indegree记录流入个数, outdegree记录流出数组
207. 课程表 初始化出入度, 找到入度为0的节点们, 从他们开始dfs, 不断找到入读为0的。
210. 课程表 II
269. 火星词典 建图，key为前序，value为后继，然后拓扑排序逐个添加入度为零的节点。
数据结构设计
146. LRU缓存机制 init cache, capacity, head, tail
380. 常数时间插入、删除和获取随机元素 return random.choice(arr); di的key为value, val为value在数组中的位置
706. 设计哈希映射 size1000的1000个list，表头为空；Node(key, val, nex)
155. 最小栈 stack, minstack
295-. 数据流的中位数 最大堆+1，最小堆，每次入堆，都有从另一个堆里挤出一个元素
208. 实现 Trie (前缀树)
高频系列专题
数组矩阵杂题
双指针
42. 接雨水 O(3n), res[i] = min(left_max, right_max), 一次性求好左边最大值和右边最大值
11. 盛最多水的容器 l从前往后，r从后往前，每次移动l和r中较小的值，算当前面积
数组
239. 滑动窗口最大值 - H
41. 缺失的第一个正数 置换，保证数组的第x−1个元素为x
51.上一个排列
238. 除自身之外的乘积
矩阵
48. 旋转图像 - M
54. 螺旋矩阵 - M
304. 2D区域和检索(不可变)
Math
204. 计算质数
Board相关题
200. 岛屿数量
Solution-DFS
Solution-BFS
Solution-UF
NSum及股票系列
NSum系列
1. 2Sum 1. 一遍Dict, On；2. 排序，双指针，Onlogn
15. 3Sum 排序+双指针，On2，固定一个i，l,r从左右开始扫描
18. 4Sum 和3Sum思路一样，固定两个再双指针，On3
股票系列
121. 买卖股票的最佳时机 维护最小值，不断更新最大收益
122. 买卖股票的最佳时机 II 只要后一天比前一天大，就交易
123. 买卖股票的最佳时机 III dp[i][s]，i为天数，s为状态
188. 买卖股票的最佳时机 IV dp[i][s]，i为天数，s为状态