线性结构
01 数组原地操作与排序 In-place Arrays and Sorting
读写双指针原地压缩 · 时间 O(n) · 空间 O(1)
要点
- 写指针 w 左边是已经确定保留的结果；读指针只往前扫，两个指针都只走一遍。
- 判断能不能保留时和 nums[w-k] 比，也就是和「结果」比，而不是和上一个读到的原始元素比。
- 原地合并两个有序数组时从尾部往前写，就不会覆盖还没读到的数据。
易错点
- 题目要的是新长度，判题只看前 k 个位置；返回数组本身或者去比较 k 之后的内容都会出错。
- 边遍历边删除（Python 的 list.remove、Java 的 ArrayList.remove）是 O(n²)，还会跳过元素。
- 排序比较器写成 a - b，值接近 ±2^31 时会溢出；用 Integer.compare 或直接比较大小。
func keepAtMost(nums []int, k int) int {
w := 0
for _, x := range nums {
if w < k || nums[w-k] != x {
nums[w] = x
w++
}
}
return w
}
02 哈希计数与关系建模 Hash Counting and Relationship Modeling
边扫边查的哈希表 · 时间 O(n) · 空间 O(n)
要点
- 先查补数、再存自己：一遍扫描就能找到「之前出现过」的配对，也不会把同一个元素用两次。
- 存什么取决于问什么：要位置就存下标，要个数就存次数，要最早出现的位置就只在第一次出现时存。
- 键可以组合出来：排序后的字符串、计数元组、(行, 值) 对，都能把「同一类」放进同一个桶。
易错点
- 先插入再查询，target 恰好等于 2x 时会把同一个元素和自己配成一对。
- C++ 的 map[key] 读一个不存在的键会插入默认值；只想判断存在时用 find 或 count。
- Java 里两个 Integer 用 == 比较，超过 127 时可能不相等；用 equals 或先拆箱成 int。
func twoSum(nums []int, target int) (int, int) {
seen := map[int]int{}
for i, x := range nums {
if j, ok := seen[target-x]; ok {
return j, i
}
seen[x] = i
}
return -1, -1
}
03 字符串解析与匹配 String Parsing and Matching
KMP 前缀函数匹配 · 时间 O(n + m) · 空间 O(m)
要点
- pi[i] 是 pat[0..i] 中「既是真前缀又是真后缀」的最长长度；失配时 j 退回 pi[j-1]，文本指针从不回头。
- 建 pi 表和在文本里匹配是同一段循环：建表就是模式串和自己匹配。
- 解析类题目用一个下标手动往前读数字、符号和括号，边界比 split 好处理。
易错点
- 匹配成功后要令 j = pi[j-1] 继续，否则会漏掉重叠出现（"aaaa" 里的 "aa" 出现 3 次）。
- 在循环里用 + 拼字符串是 O(n²)；Python 先收集到列表再 join，Java 用 StringBuilder。
- Go 里 s[i] 是字节、len(s) 是字节数；处理中文等多字节字符要先转成 []rune。
func findAll(text, pat string) []int {
m := len(pat)
pi := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && pat[i] != pat[j] {
j = pi[j-1]
}
if pat[i] == pat[j] {
j++
}
pi[i] = j
}
var res []int
for i, j := 0, 0; i < len(text); i++ {
for j > 0 && text[i] != pat[j] {
j = pi[j-1]
}
if text[i] == pat[j] {
j++
}
if j == m {
res = append(res, i-m+1)
j = pi[j-1]
}
}
return res
}
04 双指针与滑动窗口 Two Pointers and Sliding Windows
可变长度滑动窗口 · 时间 O(n) · 空间 O(Σ)
要点
- 右端每步前进一格，左端只在窗口不合法时收缩；两个指针都只前进，总共 O(n)。
- 求最长窗口：收缩完再更新答案；求最短窗口：在「仍然合法」的收缩循环里更新答案。
- 有序数组上求两数之和、去重、反转用相向双指针；判环、找中点用快慢指针。
易错点
- 收缩时忘了把移出窗口的元素计数减一，窗口状态就和实际内容对不上。
- 数组里有负数时，「和超过 k 就收缩」不再单调，滑动窗口失效，要改用前缀和。
- 「恰好 k 个」很难直接滑，用「至多 k 个」减去「至多 k-1 个」。
func longestUnique(s string) int {
cnt := map[byte]int{}
left, best := 0, 0
for right := 0; right < len(s); right++ {
c := s[right]
cnt[c]++
for cnt[c] > 1 {
cnt[s[left]]--
left++
}
best = max(best, right-left+1)
}
return best
}
05 前缀和与区间 Prefix Sums and Intervals
前缀和 + 哈希计数 · 时间 O(n) · 空间 O(n)
要点
- 区间和等于两个前缀和之差：sum(l..r) = pre[r+1] - pre[l]；前缀数组多开一位，pre[0] = 0。
- 统计「和为 k 的子数组」时，哈希表先放 {0: 1}，代表从下标 0 开始的子数组。
- 多次区间加值用差分数组：diff[l] += v，diff[r+1] -= v，最后求一遍前缀和；合并区间先按左端点排序。
易错点
- 忘了放 {0: 1}，会漏掉所有从下标 0 开始的子数组。
- 前缀和很容易超过 32 位整数，C++ 用 long long，Java 用 long。
- 先把当前前缀和存进表再查询，k = 0 时会把空子数组也算进去。
func countSubarrays(nums []int, k int) int {
seen := map[int]int{0: 1}
pre, ans := 0, 0
for _, x := range nums {
pre += x
ans += seen[pre-k]
seen[pre]++
}
return ans
}
06 二分查找与答案二分 Binary Search and Answer Search
左闭右开区间找「第一个为真」 · O(log n) 次判定
要点
- 先把问题改写成单调的判定 ok(x)：前面全是假、后面全是真，然后二分找第一个真。
- 区间 [lo, hi) 左闭右开：ok(mid) 时 hi = mid，否则 lo = mid + 1；循环条件 lo < hi，结束时 lo 就是答案。
- 答案范围已知、给定一个答案能 O(n) 验证时，直接对答案二分：最小速度、最大化最小值都是这一类。
易错点
- lo = mid 配合向下取整的 mid 会死循环；用这个模板时只写 lo = mid + 1。
- (lo + hi) / 2 在 C++、Java、Go 里可能溢出，写成 lo + (hi - lo) / 2。
- hi 本身不会被检查：上界要取到一定可行的值，否则返回的 hi 会被误当成答案。
func firstTrue(lo, hi int, ok func(int) bool) int {
for lo < hi {
mid := lo + (hi-lo)/2
if ok(mid) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}
func lowerBound(nums []int, target int) int {
return firstTrue(0, len(nums), func(i int) bool { return nums[i] >= target })
}
07 栈、单调队列与堆 Stacks, Monotonic Deques, and Heaps
单调栈：下一个更大元素 · 时间 O(n) · 空间 O(n)
要点
- 栈里存下标而不是值：既能取到值，也能算距离（比如「还要等几天才升温」）。
- 每个元素只进栈、出栈各一次，所以虽然套了 while，总复杂度仍是 O(n)。
- 求前 k 大用大小为 k 的小根堆；滑动窗口最值用单调双端队列，队头过期就弹出。
易错点
- 有重复值时 < 和 <= 结果不同，先想清楚要「严格更大」还是「大于等于」。
- Python 的 heapq 只有小根堆，要大根堆就存相反数。
- Java 的 Stack 类又慢又是同步的，栈和队列都用 ArrayDeque；比较器不要写成 a - b。
func nextGreater(nums []int) []int {
ans := make([]int, len(nums))
var st []int
for i, x := range nums {
ans[i] = -1
for len(st) > 0 && nums[st[len(st)-1]] < x {
ans[st[len(st)-1]] = x
st = st[:len(st)-1]
}
st = append(st, i)
}
return ans
}
08 贪心与调度 Greedy Algorithms and Scheduling
按结束时间排序选区间 · 时间 O(n log n)
要点
- 总是选结束最早的区间，给后面留的空间最多。交换论证：任何最优解的第一个区间都能换成它而不变差。
- 最少删除数 = 总数 - 最多保留数；「最少几支箭」也是同一个循环，只是端点相接也算重叠。
- 写贪心之前先说清楚「为什么局部最优不吃亏」；说不清楚时，多半要换成动态规划。
易错点
- 按开始时间排序再贪心，会被一个开始很早、持续很长的区间卡住。
- 端点相接算不算重叠由题意决定：>= 和 > 只差一个字符，答案就不一样。
- 比较器写成 a[1] - b[1]，端点接近 ±2^31 时会溢出。
import (
"math"
"sort"
)
func maxNonOverlapping(intervals [][]int) int {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
count, end := 0, math.MinInt
for _, iv := range intervals {
if iv[0] >= end {
count++
end = iv[1]
}
}
return count
}
链表与树
09 链表与指针 Linked Lists and Pointers
反转链表 + 快慢指针 · 时间 O(n) · 空间 O(1)
要点
- 改指针之前先存下 next。反转只有三步：存 next、指回前驱、整体前移。
- 头结点可能被删除或替换时，先建一个哑结点 dummy 指向 head，最后返回 dummy.next。
- 快指针一次两步、慢指针一次一步，用来找中点和判环；找倒数第 k 个结点则让前指针先走 k 步，再和后指针同速前进。
易错点
- 先改了 head.next 再去取 next，后面的链表就丢了。
- 访问 fast.next.next 之前要确认 fast 和 fast.next 都不为空。
- 把链表拆成两段后忘了把前半段的尾部置空，合并或遍历时会成环。
type ListNode struct {
Val int
Next *ListNode
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev, head = head, next
}
return prev
}
func middle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
return slow
}
10 二叉树遍历与结构 Binary Tree Traversal and Structure
按层 BFS · 时间 O(n) · 空间 O(最大层宽)
要点
- 每一轮先记下队列长度，正好处理这么多个结点，层与层就分开了。
- 写递归 DFS 前先想清楚「子树返回什么」：深度、是否平衡、结点数，都是把左右两边的结果合并。
- 前序、中序、后序的区别只在于「处理当前结点」放在两次递归的前面、中间还是后面。
易错点
- 用一直在变化的队列长度当循环上界，会把下一层的结点也算进这一层。
- Python 用 list.pop(0) 当队列是 O(n) 的，要用 collections.deque。
- 树退化成链时递归深度能到 10^5，Python 会爆栈；改成迭代或调高 recursionlimit。
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func levelOrder(root *TreeNode) [][]int {
var levels [][]int
var q []*TreeNode
if root != nil {
q = append(q, root)
}
for len(q) > 0 {
var level []int
var next []*TreeNode
for _, node := range q {
level = append(level, node.Val)
if node.Left != nil {
next = append(next, node.Left)
}
if node.Right != nil {
next = append(next, node.Right)
}
}
levels = append(levels, level)
q = next
}
return levels
}
11 树上路径与递归汇总 Tree Paths and Recursive Aggregation
后序返回单边贡献，全局记录拐弯路径 · 时间 O(n) · 递归栈 O(h)
要点
- 递归函数返回「从当前结点往下走的最好单边路径」，因为要继续往上接的路径只能选一边。
- 在当前结点拐弯的路径（左 + 根 + 右）只用来更新全局答案，不返回给父结点。
- 根到叶的路径题用「进入时加、离开时减」维护当前路径；任意起点的路径和用前缀和 + 哈希表。
易错点
- 全局答案初始化成 0，所有值都是负数的树会得到错误的 0。
- 子树贡献为负时要截成 0（这一边不接），否则会把答案拖低。
- 把拐弯路径也返回给父结点，等于让一条路径分叉，结果会偏大。
import "math"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func maxPathSum(root *TreeNode) int {
best := math.MinInt
var gain func(*TreeNode) int
gain = func(node *TreeNode) int {
if node == nil {
return 0
}
left, right := max(gain(node.Left), 0), max(gain(node.Right), 0)
best = max(best, node.Val+left+right)
return node.Val + max(left, right)
}
gain(root)
return best
}
12 二叉树构造与变换 Binary Tree Construction and Transformation
前序定根，中序分左右 · 时间 O(n) · 空间 O(n)
要点
- 前序的第一个值是根；在中序里找到它，左边是左子树，右边是右子树。
- 用哈希表存「值 → 中序下标」，每次切分 O(1)，整体 O(n)。
- 按「先左后右」递归时，前序指针顺序往后取就是下一个根，不用计算子数组长度；后序 + 中序则从后往前取、先右后左。
易错点
- 值有重复时中序位置不唯一，这个方法就不成立了。
- 每层递归都切片复制数组（Python 切片、Java copyOfRange），会退化成 O(n²)。
- 后序 + 中序时如果仍然先建左子树，取到的根的顺序就错了。
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func buildTree(preorder, inorder []int) *TreeNode {
pos := make(map[int]int, len(inorder))
for i, v := range inorder {
pos[v] = i
}
next := 0
var build func(lo, hi int) *TreeNode
build = func(lo, hi int) *TreeNode {
if lo == hi {
return nil
}
root := &TreeNode{Val: preorder[next]}
next++
mid := pos[root.Val]
root.Left = build(lo, mid)
root.Right = build(mid+1, hi)
return root
}
return build(0, len(inorder))
}
13 二叉搜索树 Binary Search Trees
迭代中序：按顺序走 BST · 时间 O(h + k) · 空间 O(h)
要点
- BST 的中序遍历是升序的：第 k 小、验证 BST、找前驱后继，都能转成中序问题。
- 验证 BST 要把上下界 (lo, hi) 往下传，每个结点都必须落在祖先给出的开区间里。
- 查找和插入只走一条路径，复杂度是 O(h)：平衡时 O(log n)，退化成链时 O(n)。
易错点
- 只拿结点和它的左右孩子比较，发现不了「右子树深处有比根还小的值」。
- 用 INT_MIN / INT_MAX 当边界，结点值恰好是极值时会误判；用 long 或空值表示「无界」。
- 迭代中序里忘了转向 node.right，会重复弹出同一批结点或者提前结束。
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func kthSmallest(root *TreeNode, k int) int {
var st []*TreeNode
node := root
for {
for ; node != nil; node = node.Left {
st = append(st, node)
}
node = st[len(st)-1]
st = st[:len(st)-1]
k--
if k == 0 {
return node.Val
}
node = node.Right
}
}
图论
14 网格遍历与多源搜索 Grid Traversal and Multisource Search
多源 BFS，一步扩一圈 · O(行数 × 列数)
要点
- 所有起点一开始就一起入队，相当于从一个虚拟的超级源点出发；BFS 的层数就是最短距离。
- 入队时就标记已访问，同一个格子不会被重复加入。
- 只问连通块（岛屿个数、面积）时 DFS、BFS 都可以；问最少步数必须用 BFS。
易错点
- 出队时才标记，同一个格子会被多个邻居重复入队，大网格上会超时。
- 一开始就没有新鲜橘子时答案是 0，既不是 -1，也不是层数。
- 递归 DFS 在 1000×1000 的网格上会爆栈；大网格用 BFS 或显式栈。
func minutesToRot(grid [][]int) int {
type cell struct{ r, c int }
rows, cols := len(grid), len(grid[0])
var q []cell
fresh := 0
for r := range grid {
for c, v := range grid[r] {
switch v {
case 2:
q = append(q, cell{r, c})
case 1:
fresh++
}
}
}
dirs := []cell{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
minutes := 0
for len(q) > 0 && fresh > 0 {
minutes++
var next []cell
for _, p := range q {
for _, d := range dirs {
nr, nc := p.r+d.r, p.c+d.c
if nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1 {
continue
}
grid[nr][nc] = 2
fresh--
next = append(next, cell{nr, nc})
}
}
q = next
}
if fresh > 0 {
return -1
}
return minutes
}
15 图连通性与并查集 Graph Connectivity and Union-Find
并查集：路径压缩 + 按大小合并 · 每次操作约 O(α(n))
要点
- find 时做路径压缩，union 时把小树挂到大树下；两者一起用，单次操作几乎是常数时间。
- union 返回 false 说明两点本来就连通：无向图判环、找冗余连接都靠它。
- 连通块个数、块的大小这类信息只记在根上，合并时累加。
易错点
- 用 parent[a] == parent[b] 判断连通是错的，必须比较 find(a) == find(b)。
- 合并时写成 parent[a] = b，而不是把两个根连起来，会破坏树的结构。
- 结点是字符串或坐标时，先映射成 0..n-1 的编号，或者用哈希表存 parent。
type DSU struct {
parent, size []int
count int
}
func NewDSU(n int) *DSU {
d := &DSU{parent: make([]int, n), size: make([]int, n), count: n}
for i := range d.parent {
d.parent[i], d.size[i] = i, 1
}
return d
}
func (d *DSU) Find(x int) int {
for d.parent[x] != x {
d.parent[x] = d.parent[d.parent[x]]
x = d.parent[x]
}
return x
}
func (d *DSU) Union(a, b int) bool {
a, b = d.Find(a), d.Find(b)
if a == b {
return false
}
if d.size[a] < d.size[b] {
a, b = b, a
}
d.parent[b] = a
d.size[a] += d.size[b]
d.count--
return true
}
16 拓扑排序与依赖关系 Topological Sorting and Dependencies
Kahn 算法：入度为 0 的先出队 · O(V + E)
要点
- 入度为 0 的点没有未完成的前置依赖，可以先放；放下之后把它指向的点入度减一。
- 输出的点数少于 n，说明剩下的点都在环上：「能不能修完所有课」就是这样判断的。
- 要求字典序最小的拓扑序时，把队列换成小根堆。
易错点
- 边的方向读反（「a 依赖 b」应该建 b → a），整个顺序就倒过来了。
- 只把一开始入度为 0 的点入队，后面减到 0 的点忘了入队。
- DFS 写拓扑排序时只有「访问过 / 没访问」两种状态是判不出环的，还需要「访问中」这第三种状态。
func topoOrder(n int, edges [][2]int) []int {
graph := make([][]int, n)
indeg := make([]int, n)
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], e[1])
indeg[e[1]]++
}
var q []int
for i, d := range indeg {
if d == 0 {
q = append(q, i)
}
}
order := make([]int, 0, n)
for len(q) > 0 {
u := q[0]
q = q[1:]
order = append(order, u)
for _, v := range graph[u] {
indeg[v]--
if indeg[v] == 0 {
q = append(q, v)
}
}
}
if len(order) < n {
return nil
}
return order
}
17 最短路径与图状态 Shortest Paths and Graph States
Dijkstra：堆 + 懒删除 · O((V + E) log V)
要点
- 每次从堆里取出当前距离最小的点，它的距离就确定了；前提是所有边权非负。
- 不做 decrease-key：直接把新距离压进堆，弹出时发现比 dist 大就跳过（懒删除）。
- 边权只有 0 和 1 时用双端队列 BFS；有负权用 Bellman-Ford；状态里带「已用次数」时，把 (点, 次数) 当成一个新结点。
易错点
- 不跳过过期的堆元素，同一个点会被反复松弛，稠密图上会超时。
- 距离累加超出 32 位整数；用 INT_MAX 当无穷大时，d + w 还会溢出成负数。
- 有向图当成无向图建边（或者反过来），所有距离都会错。
import "container/heap"
type item struct{ dist, node int }
type minHeap []item
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any) { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func dijkstra(n int, edges [][3]int, src int) []int {
graph := make([][][2]int, n)
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], [2]int{e[1], e[2]})
}
dist := make([]int, n)
for i := range dist {
dist[i] = -1
}
dist[src] = 0
h := &minHeap{{0, src}}
for h.Len() > 0 {
top := heap.Pop(h).(item)
if top.dist > dist[top.node] {
continue
}
for _, e := range graph[top.node] {
v, nd := e[0], top.dist+e[1]
if dist[v] == -1 || nd < dist[v] {
dist[v] = nd
heap.Push(h, item{nd, v})
}
}
}
return dist
}
18 生成树与树形图 Spanning Trees and Tree Graphs
Kruskal：按边权排序 + 并查集 · O(E log E)
要点
- 按边权从小到大看每条边：能连起两个不同连通块就选，否则跳过（选了会成环）。
- 选够 n-1 条边就是一棵生成树；最后不够 n-1 条，说明图不连通。
- 点少边多的稠密图（比如坐标点两两相连）用 O(n²) 的 Prim，往往比给所有边排序更快。
易错点
- 没检查是否连通，直接返回累加的边权。
- 坐标点两两连边有 n²/2 条，内存和排序时间都可能超限。
- 点的编号从 1 开始，并查集却只开了 n 个位置。
import "sort"
func mstWeight(n int, edges [][3]int) int {
sort.Slice(edges, func(i, j int) bool { return edges[i][2] < edges[j][2] })
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
total, used := 0, 0
for _, e := range edges {
ru, rv := find(e[0]), find(e[1])
if ru == rv {
continue
}
parent[ru] = rv
total += e[2]
used++
}
if used != n-1 {
return -1
}
return total
}
回溯
19 回溯枚举与去重 Backtracking Enumeration and Deduplication
选择、递归、撤销；同层跳过重复 · O(n · 2^n)
要点
- 模板只有三步：做选择、递归、撤销选择；path 是整个搜索共用的一份。
- 先排序，再用 i > start && nums[i] == nums[i-1] 跳过：同一层不重复选相同的值，更深的层可以。
- 组合从 start 往后选，避免 {1,2} 和 {2,1} 同时出现；排列每次从头选，用 used 数组标记。
易错点
- 结果里直接存 path 的引用，回溯结束后所有结果都变成同一个空列表。
- 把 i > start 写成 i > 0，更深层里合法的重复值也会被跳过。
- 忘了先排序，相同的值不相邻，去重判断就失效了。
import "sort"
func subsetsWithDup(nums []int) [][]int {
nums = append([]int(nil), nums...)
sort.Ints(nums)
var res [][]int
var path []int
var dfs func(start int)
dfs = func(start int) {
res = append(res, append([]int(nil), path...))
for i := start; i < len(nums); i++ {
if i > start && nums[i] == nums[i-1] {
continue
}
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return res
}
20 字符串拆分与构造 String Partitioning and Construction
按切分点回溯 + 回文预处理 · O(n · 2^n)
要点
- 回溯的每一层决定「下一段切到哪里」，start 走到 n 就得到一种完整的切法。
- 先用 O(n²) 的区间 DP 算出每个子串是不是回文，回溯里的判断就是 O(1)。
- 复原 IP 地址、单词拆分也是同一个框架，只是「这一段是否合法」的判断不同。
易错点
- 在回溯里每次都重新用双指针判断回文，重复计算会让常数大很多。
- 只要求方案数或最少切几刀时，不要枚举，改用 DP。
- 子串下标是左闭右开还是左闭右闭要统一；s[start:end+1] 和 substring(start, end+1) 很容易差一位。
func partition(s string) [][]string {
n := len(s)
pal := make([][]bool, n)
for i := range pal {
pal[i] = make([]bool, n)
}
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
pal[i][j] = s[i] == s[j] && (j-i < 2 || pal[i+1][j-1])
}
}
var res [][]string
var path []string
var dfs func(start int)
dfs = func(start int) {
if start == n {
res = append(res, append([]string(nil), path...))
return
}
for end := start; end < n; end++ {
if pal[start][end] {
path = append(path, s[start:end+1])
dfs(end + 1)
path = path[:len(path)-1]
}
}
}
dfs(0)
return res
}
21 约束搜索与剪枝 Constraint Search and Pruning
N 皇后：按列和两条对角线剪枝 · 最坏 O(n!)
要点
- 每行只放一个皇后，搜索树只在列上分叉；列、主对角线 r-c、副对角线 r+c 各用一个数组标记。
- 剪枝越早越好：递归之前就判断冲突，而不是放满整个棋盘再检查。
- 数独、组合总和这类题先排序，在「剩下的值已经不可能满足」时用 break，比 continue 省得多。
易错点
- 主对角线下标 r-c 会是负数，要加上 n-1 的偏移。
- 回溯返回前忘了把标记改回去，后面的分支全被误剪。
- 需要输出棋盘时，用可变的字符数组逐格修改，最后再转字符串，不要每一步都复制整盘。
func totalQueens(n int) int {
cols, diag, anti := make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
var place func(r int) int
place = func(r int) int {
if r == n {
return 1
}
count := 0
for c := 0; c < n; c++ {
d := r - c + n - 1
if cols[c] || diag[d] || anti[r+c] {
continue
}
cols[c], diag[d], anti[r+c] = true, true, true
count += place(r + 1)
cols[c], diag[d], anti[r+c] = false, false, false
}
return count
}
return place(0)
}
动态规划
22 动态规划入门与状态设计 Dynamic Programming Fundamentals and State Design
一维 DP + 滚动变量 · 时间 O(n) · 空间 O(1)
要点
- 先用一句话定义状态，比如 dp[i] = 只看前 i 个元素时的最优值；状态说清楚了，转移通常就出来了。
- 转移只看「最后一步做了什么」：第 i 个选还是不选，最后一跳是 1 步还是 2 步。
- dp[i] 只依赖前一两项时，用两个变量滚动，空间从 O(n) 降到 O(1)。
易错点
- dp 和输入的下标错位：dp 多开一位时 dp[0] 表示「什么都没选」，答案在 dp[n]。
- 滚动更新时先覆盖了 prev1 再拿它算新值，用到的已经是新数据了。
- 方案数很快会超出 64 位；题目要求取模时，每一步都要取模。
func rob(nums []int) int {
prev2, prev1 := 0, 0
for _, x := range nums {
prev2, prev1 = prev1, max(prev1, prev2+x)
}
return prev1
}
23 网格路径与二维状态 Grid Paths and Two-Dimensional States
网格 DP 压成一行 · 时间 O(行数 × 列数) · 空间 O(列数)
要点
- dp[r][c] 只依赖上方和左方，按行从左到右填，一行数组就够：更新前 dp[c] 是上方，dp[c-1] 是左方。
- 第一行、第一列只有一个来源，要么单独处理，要么用无穷大哨兵统一写法。
- 路径计数就把 min 换成加法；有障碍的格子直接置 0。
易错点
- 哨兵用 INT_MAX 再加上格子值会溢出，要保证只在有限值上做加法。
- 允许往四个方向走时没有填表顺序，DP 不成立，要用 BFS 或 Dijkstra。
- 压成一行之后，如果转移还需要左上角的值，要在它被覆盖前先存到变量里。
import "math"
func minPathSum(grid [][]int) int {
cols := len(grid[0])
dp := make([]int, cols)
for c := 1; c < cols; c++ {
dp[c] = math.MaxInt
}
for _, row := range grid {
for c := range row {
best := dp[c]
if c > 0 {
best = min(best, dp[c-1])
}
dp[c] = best + row[c]
}
}
return dp[cols-1]
}
24 背包与组合计数 Knapsack and Combination Counting
0/1 背包倒序，完全背包正序 · O(n × target)
要点
- 0/1 背包倒序遍历容量，保证 dp[s-x] 还是「没用过 x」的旧值；完全背包正序遍历，允许同一件物品重复使用。
- 物品在外层、容量在内层，数的是组合（不计顺序）；容量在外层、物品在内层，数的是排列。
- 很多题要先转化成背包：「分成两个和相等的子集」= 能否凑出 sum/2；「目标和」= 凑出 (sum+target)/2。
易错点
- 0/1 背包写成正序，同一件物品会被用很多次。
- 计数问题 dp[0] = 1（什么都不选也是一种方案）；求最值问题 dp[0] = 0，其余初始化为无穷。
- 转化成 (sum+target)/2 之前没检查奇偶性和正负，会得到错误的下标。
func countSubsets(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for _, x := range nums {
for s := target; s >= x; s-- {
dp[s] += dp[s-x]
}
}
return dp[target]
}
func countCombinations(coins []int, amount int) int {
dp := make([]int, amount+1)
dp[0] = 1
for _, coin := range coins {
for s := coin; s <= amount; s++ {
dp[s] += dp[s-coin]
}
}
return dp[amount]
}
25 子序列与偏序关系 Subsequences and Partial Orders
LIS：tails 数组 + 二分 · O(n log n)
要点
- tails[k] 是长度为 k+1 的递增子序列可能的最小结尾；它本身是递增的，所以可以二分。
- 严格递增用 lower_bound（第一个 ≥ x），非递减用 upper_bound（第一个 > x）。
- 二维的「信封嵌套」先按宽升序、宽相同时按高降序排序，再对高做 LIS。
易错点
- tails 数组不是真实存在的最长子序列，只有长度是对的；要输出方案得另外记录前驱。
- 严格和非严格用错了二分函数，重复元素多的用例会差 1 甚至更多。
- 要求「最长子序列有几个」时，O(n log n) 写法不够，要回到 O(n²) 的 dp 加计数数组。
import "sort"
func lisLength(nums []int) int {
var tails []int
for _, x := range nums {
i := sort.SearchInts(tails, x)
if i == len(tails) {
tails = append(tails, x)
} else {
tails[i] = x
}
}
return len(tails)
}
26 字符串匹配与编辑 String Matching and Editing
双串 DP：dp[i][j] 看两个前缀 · O(m × n)
要点
- dp[i][j] 定义在前缀上：a 的前 i 个字符和 b 的前 j 个字符；多开一行一列表示空串。
- 末尾字符相等就继承 dp[i-1][j-1]；不相等时，替换、删除、插入分别对应左上、上、左三个格子。
- 最长公共子序列、不同的子序列、通配符匹配都是这张表，只是转移不同。
易错点
- dp 的下标是前缀长度，对应的字符是 a[i-1]；写成 a[i] 会错一位。
- 忘了初始化第 0 行和第 0 列（变成空串需要删 i 次，从空串变来需要插 j 次）。
- 压成一行时，左上角的值会被本行覆盖，需要额外一个变量保存。
func editDistance(a, b string) int {
m, n := len(a), len(b)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
dp[i][0] = i
}
for j := range dp[0] {
dp[0][j] = j
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if a[i-1] == b[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]
}
27 回文与区间状态 Palindromes and Interval States
区间 DP：左端点倒序枚举 · O(n²)
要点
- dp[i][j] 只依赖更短的区间 dp[i+1][*] 和 dp[*][j-1]，所以 i 倒序、j 正序填表。
- 两端字符相等就向内收缩并加 2，否则去掉一端，取两种情况的较大值。
- 只问回文子串（必须连续）时，中心扩展法 O(n²) 时间、O(1) 空间，更简单。
易错点
- i 正序枚举时 dp[i+1][*] 还没有算出来，结果全错。
- 子序列（可以不连续）和子串（必须连续）是两道题，转移不能混用。
- 中心扩展要同时试奇数中心 (i, i) 和偶数中心 (i, i+1)。
func longestPalSubseq(s string) int {
n := len(s)
if n == 0 {
return 0
}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
dp[i][i] = 1
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][n-1]
}
28 状态机与连续序列 State Machines and Contiguous Sequences
以 i 结尾的状态：同时记最大和最小 · 时间 O(n) · 空间 O(1)
要点
- 状态定义成「以 i 结尾」，连续子数组的转移就只有两种：接在前一段后面，或者从 i 重新开始。
- 乘法遇到负数时最大会变成最小，所以要同时维护最大和最小两个状态。
- 状态机 DP 就是给每个位置多设几个状态（持有 / 不持有、上一个选没选），把状态之间的每条转移都写出来。
易错点
- 先更新了 hi 再用新的 hi 去算 lo，用到的是同一轮已经改过的值。
- 答案初始化成 0，全是负数的数组就会出错。
- 最大子数组和（Kadane）的转移是 cur = max(x, cur + x)，不要漏掉「重新开始」这一项。
func maxProduct(nums []int) int {
hi, lo, best := nums[0], nums[0], nums[0]
for _, x := range nums[1:] {
a, b := hi*x, lo*x
hi, lo = max(x, a, b), min(x, a, b)
best = max(best, hi)
}
return best
}
29 股票交易状态机 Stock Trading State Machines
持有 / 冷却 / 空仓三状态 · 时间 O(n) · 空间 O(1)
要点
- 先写清楚每天结束时可能处于哪几种状态，再写「昨天的哪种状态 + 今天的什么动作」能到达它。
- 同一天的几个新值都要用前一天的旧值计算，所以要同时赋值或者先存临时变量。
- 最多 k 次交易就加一维 k；手续费在每次卖出（或买入）时扣一次；只交易一次就是「记录历史最低价」。
易错点
- 持有状态初始化成 0，相当于第 0 天白送了一股。
- 用负无穷做初值时，C++ / Java 里 hold + p 会溢出；取 MIN / 2 这样的值。
- 有冷却期时，买入只能从「空仓」状态转过来，不能从「刚卖出」状态直接买。
import "math"
func maxProfitCooldown(prices []int) int {
hold, cool, free := math.MinInt/2, 0, 0
for _, p := range prices {
hold, cool, free = max(hold, free-p), hold+p, max(free, cool)
}
return max(cool, free)
}
30 分段与调度优化 Partitioning and Scheduling Optimization
按结束时间排序 + 二分找上一个兼容任务 · O(n log n)
要点
- 按结束时间排序后，dp[i] = 前 i 个任务的最优值；第 i 个任务要么不选，要么接在最后一个不冲突的任务后面。
- 「最后一个不冲突的任务」在结束时间数组里二分查找，整体 O(n log n)。
- 「把数组分成 k 段」这类题，状态通常是 dp[段数][结尾位置]，转移时枚举最后一段从哪里开始。
易错点
- 首尾相接算不算冲突，决定了用 upper_bound 还是 lower_bound。
- 按开始时间排序、每次贪心选利润最高的，在带权的版本里不成立。
- 排序时只排了结束时间，开始时间和利润没有跟着一起动。
import "sort"
func maxProfit(start, end, profit []int) int {
n := len(start)
order := make([]int, n)
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return end[order[a]] < end[order[b]] })
dp := make([]int, n+1)
for i, job := range order {
k := sort.Search(i, func(m int) bool { return end[order[m]] > start[job] })
dp[i+1] = max(dp[i], dp[k]+profit[job])
}
return dp[n]
}
31 路径、树形与对抗状态 Path, Tree, and Game States
树形 DP：每个结点返回（选，不选） · O(n)
要点
- 树形 DP 用后序遍历：先拿到左右子树的结果，再算当前结点，每个结点返回一个小元组。
- 按「当前结点选不选」拆状态，比在父结点里往下看两层更简单，也不会重复计算。
- 两人博弈题常用「当前先手比对手多拿多少」作为状态：dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])。
易错点
- 不返回元组，而是用「祖父 + 孙子」的写法又不做记忆化，会指数级重复计算。
- 不选当前结点时，孩子也不一定要选，每个孩子都要取 max(选, 不选)。
- 博弈题如果按「我的得分」建状态，往往还得再记对手的得分；用差值更省事。
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func robTree(root *TreeNode) int {
var dfs func(*TreeNode) (take, skip int)
dfs = func(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
lt, ls := dfs(node.Left)
rt, rs := dfs(node.Right)
take := node.Val + ls + rs
skip := max(lt, ls) + max(rt, rs)
return take, skip
}
take, skip := dfs(root)
return max(take, skip)
}
设计与位运算
32 容器与迭代接口设计 Container and Iterator Design
惰性迭代器：hasNext 负责前进 · 每次调用均摊 O(1)
要点
- 把「跳过空行、走到下一个有效元素」放进 hasNext，next 只负责取值；这样连续调用多次 hasNext 也没有副作用。
- 只保存位置（行号、列号），不要在构造函数里把所有元素复制成一个大数组。
- 任意深度的嵌套列表用一个栈保存各层的位置；Python 里用生成器 yield from 最自然。
易错点
- 中间或末尾有空行时，hasNext 只看下一行就会返回错误的 true。
- next 里不先调用 hasNext，直接取值会越界。
- 迭代过程中修改了原容器：Java 会抛 ConcurrentModificationException，其他语言则是悄悄出错。
type Flatten2D struct {
rows [][]int
r, c int
}
func (it *Flatten2D) HasNext() bool {
for it.r < len(it.rows) && it.c == len(it.rows[it.r]) {
it.r, it.c = it.r+1, 0
}
return it.r < len(it.rows)
}
func (it *Flatten2D) Next() int {
if !it.HasNext() {
panic("no more elements")
}
it.c++
return it.rows[it.r][it.c-1]
}
33 缓存、随机访问与流式索引 Caches, Random Access, and Streaming Indexes
LRU：哈希表 + 双向链表 · get 与 put 均为 O(1)
要点
- 哈希表负责 O(1) 找到结点，双向链表负责 O(1) 把结点移到头部、删除尾部。
- get 也算一次「使用」，要把结点移到最新的一端；put 一个已存在的键要更新值并移动，而不是再插一份。
- 面试要求手写链表时，用头尾两个哨兵结点，插入删除就不用判断空指针。
易错点
- 淘汰尾结点时只删了链表、没删哈希表里的键（或者反过来）。
- 先插入再淘汰还是先淘汰再插入要统一，并想清楚容量为 0 这种边界。
- 链表结点里不存 key，淘汰时就不知道该删哈希表里的哪一项。
import "container/list"
type entry struct{ key, value int }
type LRUCache struct {
cap int
order *list.List
pos map[int]*list.Element
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{cap: capacity, order: list.New(), pos: map[int]*list.Element{}}
}
func (c *LRUCache) Get(key int) int {
el, ok := c.pos[key]
if !ok {
return -1
}
c.order.MoveToFront(el)
return el.Value.(*entry).value
}
func (c *LRUCache) Put(key, value int) {
if el, ok := c.pos[key]; ok {
el.Value.(*entry).value = value
c.order.MoveToFront(el)
return
}
c.pos[key] = c.order.PushFront(&entry{key, value})
if c.order.Len() > c.cap {
oldest := c.order.Back()
c.order.Remove(oldest)
delete(c.pos, oldest.Value.(*entry).key)
}
}
34 字典、文件系统与序列化 Dictionaries, File Systems, and Serialization
字典树：结点存孩子和计数 · 每次操作 O(单词长度)
要点
- 每个结点代表一个前缀；插入和查询都是顺着字符往下走，耗时只和单词长度有关。
- 结点上存计数（有多少单词经过、有多少单词在此结束），前缀计数和删除都能 O(L) 完成。
- 序列化二叉树用前序遍历加空结点标记（如 "#"），反序列化时按同样的顺序递归读回来。
易错点
- 把 search（完整单词）和 startsWith（前缀）混为一谈，忘了检查结束标记。
- 固定 26 叉数组默认只有小写字母；有大写、数字或 Unicode 时，孩子改用哈希表存。
- 序列化时值之间不加分隔符，多位数和负数就没法还原。
type Trie struct {
next [26]*Trie
prefix int
words int
}
func (t *Trie) Insert(word string) {
node := t
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.next[c] == nil {
node.next[c] = &Trie{}
}
node = node.next[c]
node.prefix++
}
node.words++
}
func (t *Trie) walk(s string) *Trie {
node := t
for i := 0; i < len(s) && node != nil; i++ {
node = node.next[s[i]-'a']
}
return node
}
func (t *Trie) CountWord(word string) int {
if node := t.walk(word); node != nil {
return node.words
}
return 0
}
func (t *Trie) CountPrefix(prefix string) int {
if node := t.walk(prefix); node != nil {
return node.prefix
}
return 0
}
35 实用位运算与数值边界 Practical Bit Operations and Numeric Boundaries
位运算小工具与快速幂 · O(log n)
要点
- x & (x-1) 去掉最低位的 1，x & -x 取出最低位的 1；异或满足 a ^ a = 0，可以找出只出现一次的数。
- 快速幂把指数按二进制拆开：每轮把底数平方，指数这一位是 1 就乘进结果，O(log exp)。
- 不超过 20 个元素的集合可以用一个整数当掩码，for (s = mask; s; s = (s-1) & mask) 枚举它的所有非空子集。
易错点
- 两个 10^9 量级的数相乘会超出 32 位，取模乘法之前先转成 long / long long。
- Java 的 >> 会保留符号位，处理负数用无符号右移 >>>；Python 整数无限长，负数要先 & 0xFFFFFFFF。
- C++ 里位运算优先级低于比较：x & 1 == 0 实际是 x & (1 == 0)，一定要加括号（Java 会直接编译报错）。
func popcount(x uint) int {
count := 0
for ; x != 0; x &= x - 1 {
count++
}
return count
}
func powMod(base, exp, mod int) int {
result := 1 % mod
for base %= mod; exp > 0; exp >>= 1 {
if exp&1 == 1 {
result = result * base % mod
}
base = base * base % mod
}
return result
}