高频经典算法题汇总

基础

排序算法

• 快速排序
• 归并排序
• 冒泡排序

二分查找

• 数组
  • 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为状态

区间(会议室)

BFS, DFS

Radix/Bucket Sort

队列实现栈，栈实现队列