算法思路总结

过去一年基本上都在练习算法了，人菜瘾大刷了不少题，做个总结吧。

Python

• 第 0 课，不要用 if not foo 这种判断来区分 None，因为无法区分默认值与 None，比如 0、[]、{} 等

• int(v) 永远是朝 0 的方向取整，不用判断正负然后选择 ceil 和 floor

• bit 移位加括号，1 << 31 - 1 其实相当于 1 << 30

• str.split() 直接按照空格切分字符串

• itertools.groupby() 把元素归类

• 日期间隔，要是真的要求我数闰年，也太没意思了

  1from datetime import date
  2
  3(date(2022, 3, 21) - date(2022, 3, 1)).days
  

• 对于需要记忆化的 DP，可以使用 functools.cache 装饰器，当然要求参数必须支持哈希

二叉树

刷题建议从二叉树开始，俗话说的好「递归在手，遇 Tree 不愁」，主要是二叉树的思路有固定的模板，而且也不太可能考到红黑树那个级别，难一点也只会和 Graph 相关，一开始比较容易建立信心。

• 前序、中序、后序遍历

  根据中序和另一个来恢复二叉树，注意查找 parent 的优化

• 理解 BST 的中序遍历，就是值的升序，所以 BST 的中序第一个不满足单调性的节点，就是出错的节点

• BST 的每个节点，都是有取值范围的，对于 root 是 (-maxsize, maxsize)，对于 node.left 是 (-maxsize, node.val)，对于 node.right 是 (node.val, maxsize)

• 反转二叉树，算是全世界出圈、成了梗了

• 按层遍历，注意使用 Deque 优化空间，首先注意 Deque 的发音，LOL

• 满二叉树求节点数，小于 O(N) 的时间 222. Count Complete Tree Nodes

• 求 ancestor 相关的题，可以记录节点的 parent，转换为链表相关的问题

• 序列化、反序列化，需要考虑极端情况树是个单链表

• 删除 BST 的指定节点

• BST 插入节点

• 二叉树的数组表示，parent 与左右节点关系

• 满二叉树的数组表示，是连续的

图

应该算是心理压力最大的一类了，但是只要没有超纲，套路并不多

• 拓扑排序

• 二分图

• 从入度、出度考虑

• 逆向图

• 最小生成树

• Dijkstra 最短路径

  最短路径有多种解法，下面会单独讨论

并查集

英文名 Union Find，其实也刚好对应需要实现的两个方法 union(p, q) -> None 和 find(p) -> int ，也刚好对应两个主要的思想「按秩合并」「路径压缩」。

一般遇到连通相关的题目，个人是优先用并查集的，因为比较模板化，相比于 DFS 和 BFS，思路比较简单，也没什么出错的空间。

需要注意连通的广义的定义，两个邮箱对应同一个人，岛屿中 land 相互连接。

但是尤其需要注意的是，这里连通的双向性，比如炸弹 A 爆炸时可以引爆 B，并不意味着炸弹 B 可以爆炸引爆 A，这里连接是单向的。

• 数组中最长的连续数字
• 被包围的陆地，即没有与边界的陆地连通
• 岛屿数量
• 已知几个数的倍数关系，返回指定 2 个数的倍数
• 冗余连接问题，N 个分量最少需要 N - 1 个连接

字典树

如果题目没有提到字典树，不太容易想到这个思路。更多时候是一种优化方案，比如矩阵中查找字符串，如果不提前建立一个 Trie，那么在搜索的时候肯定会 TLE 了。

• 不要忘记在单词结束的时候做标记，常用 '#'

• 大部分都是用递归实现的，可以使用默认参数，避免重复定义方法；当然其实不用递归更简洁的

  1def search(self, word: str, cur: Dict = None) -> bool:
  2    if cur is None:
  3        cur = self.root
  4    if not word:
  5        return "#" in cur
  6    if word[0] not in cur:
  7        return False
  8    else:
  9        return self.search(word[1:], cur[word[0]])
  

  同时呢，使用 dict.setdefault 可以让代码更干净一些

  1def insert(self, word: str, cur: Dict = None) -> None:
  2    if cur is None:
  3        cur = self.root
  4    if not word:
  5        cur["#"] = None
  6    else:
  7        self.insert(word[1:], cur.setdefault(word[0], {}))
  

数组

数组算是最难的一类了，因为花样比较多

• 寻找 f(i, j) 函数的极值，一般是 O(N) 遍历一遍，并维护左边已经访问的极值，遍历的时候计算当前值与左边极值的结果

• 有序数组的双指针，可以 O(N) 找到 nums[i] + nums[j] == target，理解为什么会覆盖解空间

• 双指针原地删除指定元素

• 当数组的元素在 [0, N - 1] 范围时，需要敏感一点，可以把 val 当作 index，类似链表处理了 287. Find the Duplicate Number

• 数组元素的值在 [0, N - 1] 或者 [1, N] 时，也可以 val 做 index，给对应的 nums[i] 修改符号来标记某个数字有没有出现

• 旋转数组的最小值，即找到旋转的轴，需要注意数组中有没有重复元素

• 桶排序 164. Maximum Gap

  简单地理解，数组排序后 N 个数会有 N-1 个间隔，相当于 N-1 个增长机会从 minV 到 maxV，那么相邻元素的最大值，一定不能小于 (maxV - minV) / (N - 1)。

  于是 bucketSize 定义为 ceil((maxV - minV) / (N - 1))，这样每个 bucket 内部的 diff 都会小于上面的值，所求的最大 diff 值一定会发生在不同的 bucket 之间。 需要注意 bucketNum 是 N 而不是 N - 1，对于刚好整除的时候是 M 个区间 M + 1 个点，比如数组 [0, 1] 我们需要 2 个桶

  每一个桶内的差值不会超过 bucketSize，所以只关注相邻桶的差值就行了，需要注意空桶

• 环形数组的子数组

  首尾如果不能同时选，那么可以分成 2 个子问题，nums[1:] 和 nums[:-1] 的最优解

  首尾都可以选，或许可以转化为求中间未选中部分的极值

矩阵

• 矩阵的 R+C 和 R-C 可以用来标记两个方向的对角线
• 修改矩阵时，试着用被修改的行、列来存储信息，空间可以从 O(N^2) 优化到 O(N)
• 行列有序的二分查找
• 矩阵中寻找字符串，需要用 Trie 优化搜索

链表

• 合并有序链表
• 数字相加、注意进位
• 合并多个链表、最小堆
• 快慢指针
  • 根据首尾距离定位到指定 node
  • 删除第 N 个 node
• 求中点，比如有序链表转 BST
• 反转链表、或每 K 个反转
• 旋转链表，注意旋转次数 K 的数量级，可以取余优化
• 有序链表去重
• 环
  • 是否有环
  • 环的长度
  • 环的起始位置
• 两个链表相交的 Node，可以反转，求链表长度更优雅一些

滑动窗口

一般按照题意就可以想到这个思路了

需要在窗口内维护顺序时，可以使用 SortedList，O(logN) 的复杂度，LeetCode 官方支持这个第三方的 sortedcontainer 库

二分

一般是 10^4 或者题目要求 O(logN) 的复杂度了

正相关的题目可以试试二分，比如吃香蕉的最慢速度、计算平方根

堆

• Python 的 heapq 只支持最小堆，添加负号就是最大堆

• 对于不支持比较的对象，不能直接扔进 heap 里，比如 ListNode，这时候可以包装成 (node.val, node) 扔进 heap

  但是如果 2 个 node 对象的 val 相同，还是会比较 node

  可以维护一个 global counter，给 heap 里扔 (node.val, counter, node)，因为 counter 递增不会重复，所以不用比较 node 对象

• 对顶堆

  求流的中位数，创建 2 个大小相同的堆

单调栈、单调队列

往往觉得这种解法很神奇

顺着题意去模拟这个过程，在求每个阶段的值的时候，可能会注意到这个方向。

84. Largest Rectangle in Histogram

239. Sliding Window Maximum

前缀和

前缀和的思想很简单，但是变种非常多

• 后缀和
• 矩阵的区域和，也就是二维前缀和
• 子数组和的极值
• 计算乘积
• 矩阵里形成的最长的 + 号，最大的正方形，归为 DP 类题目，也是前缀的思想
• 前缀异或 1310. XOR Queries of a Subarray

DP

常说状态转换方程，但是一般可能没那么容易找出来。实用一点的方法是，先寻找可能的操作，每一个操作后可能对应不同的状态。比如股票的买卖、冷冻期。

有些 DP 原型会藏的比较深

• 台阶、最短路径、不同路径数

• 子数组最大和、最大乘积（注意负数）

• N 个数，求 BST 的种类

• 矩阵内最大正方形

• 藏的比较深的

  • 368. Largest Divisible Subset
  • 799. Champagne Tower

字符串

和数组一样也是难点，因为变化可能比较多

• 回文，注意奇偶 2 种对称
• 括号匹配，栈
• 生成括号，维护当前 open 的数量，决定是否可以添加右括号
• 打乱顺序互相转换，字符计数
• 文件路径，栈
• 子序列匹配，使用首字母映射单词做优化 792. Number of Matching Subsequences
• 字符是否存在，也许可以用 bit 标记来优化
• 滚动哈希，基于 i-1 的结果，对 i 可以直接得到哈希值 2156. Find Substring With Given Hash Value
• Lexicographically Order，即字典序

Math

最绝望的一类题了吧，高考都是多少年前的事情了

• 计算幂，不要一次一次乘，二分计算幂，结果相乘

• 用 a 和 b 表示一条直线，注意平行的情况

• 找 N 以内的质数

• 两条线段的相交区域、两个矩形的相交区域

• 对于质数 M，求 N 是不是 M 的幂，可以判断 int 范围内 M 最大的幂能否整除 N

• 手动计算平方根，实现 sqrt

• 复数乘法运算

• 一个数表示为 M 的幂的和，相当于转换成 M 进制 1780. Check if Number is a Sum of Powers of Three

• 凸包算法，向量叉乘判断折线方向，用 Monotone Chain 算法比较容易理解

  需要注意共线的情况，极端情况所有点都在一条线上 587. Erect the Fence

• 海伦公式求三角形面积

  area = sqrt(S(S-a)(S-b)(S-c)) 这里 S 是半周长

• 给定数字分解质因数 952. Largest Component Size by Common Factor

• 3 个点是否共线，注意除法转乘法

• GCD，辗转相除法，依据是 gcd(a, b) = gcd(b, a mod b)，需要确保第一次传入的 a 与 b 大小关系

  1def gcd(a:int, b:int) -> int:
  2    if b == 0:
  3        return a
  4    return gcd(b, a % b)
  

  1979. Find Greatest Common Divisor of Array

BIT

• 异或的特性

  高阶异或 260. Single Number III

• 二进制只有一个 1，一定是 2 的幂

  如果是 4 的幂，1 后面的 0 一定是偶数个

BFS

• BFS 一定要标记 visited、确认搜索边界

  仍然不知道 1654. Minimum Jumps to Reach Home 是怎么得到的右边界，都在解释结果的正确性，但是没能正向推导出来

• 双向 BFS，交换两个方向，优先处理结果少的一边

• BFS 是可以添加状态的

  1293. Shortest Path in a Grid with Obstacles Elimination

  847. Shortest Path Visiting All Nodes

• 数据量不大的时候，别想太多，就用 BFS 硬算吧

  1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

回溯

几乎通用的模板：

1for o in options:
2    state[i] = o
3    if dfs(i + 1):
4        return True
5    else:
6        state[i] = None

37. Sudoku Solver

980. Unique Paths III

51. N-Queens

最短路径

大部分是 BFS，其余大多是 DP 或者 Dijkstra

建议首先考虑 Dijkstra，因为对于常见的有向加权图，只有这一种解法，没有什么变化。

对于 BFS，当路径可以重复访问时，也许需要添加状态记录访问情况

带限制的有向图最短路径，可以用 DP，如 787. Cheapest Flights Within K Stops，这个题号也是藏了个梗。

扫描线

天上最多的飞机、同时最多上自习的人、merge 区间

需要注意的是，最后结果的定义是否要包含起点与结束点，比如求人口最多的一年，那么是否需要包含这一年的死亡人数。

变体：218. The Skyline Problem 与 391. Perfect Rectangle

其他神奇的思路

• 3 次反转旋转矩阵、旋转数组

• 多数投票算法，O(1) 的空间占用就可以找到众数

• 神经病题目 237. Delete Node in a Linked List

• Digit Root，可以模拟这个过程实现，也可以从数学上直接返回结果

  找到的资料都是数论上反推直接取余的正确性，但是如果第一次遇到不太可能正向找到这个思路的

• Meeting Point，两个点双向奔赴相遇，不论相遇点在哪里，总距离是恒定的

• 直接统计偏移量 835. Image Overlap

• 藏的比较深的 DP 837. New 21 Game

• 中点相关的题目，使用对称结构

  295. Find Median from Data Stream

  1670. Design Front Middle Back Queue