cswork / 模板打开 500 路题单

500 路 · 35 站 · Python

代码模板手册：Python

每站一节：模式、复杂度、3 条要点、3 个易错点和 Python 模板。每份模板都编译运行过，并用测试数据核对了输出。打印时每组从新的一页开始；在打印对话框里选「存储为 PDF」就能存成文件。

cswork.org/topics

读写双指针原地压缩 · 时间 O(n) · 空间 O(1)

要点

  1. 写指针 w 左边是已经确定保留的结果；读指针只往前扫，两个指针都只走一遍。
  2. 判断能不能保留时和 nums[w-k] 比，也就是和「结果」比，而不是和上一个读到的原始元素比。
  3. 原地合并两个有序数组时从尾部往前写，就不会覆盖还没读到的数据。

易错点

  • 题目要的是新长度，判题只看前 k 个位置；返回数组本身或者去比较 k 之后的内容都会出错。
  • 边遍历边删除（Python 的 list.remove、Java 的 ArrayList.remove）是 O(n²)，还会跳过元素。
  • 排序比较器写成 a - b，值接近 ±2^31 时会溢出；用 Integer.compare 或直接比较大小。
def keep_at_most(nums: list[int], k: int) -> int:
    """Sorted nums: keep each value at most k times, in place. Returns the new length."""
    w = 0  # nums[:w] is the kept prefix
    for x in nums:
        if w < k or nums[w - k] != x:
            nums[w] = x
            w += 1
    return w

边扫边查的哈希表 · 时间 O(n) · 空间 O(n)

要点

  1. 先查补数、再存自己：一遍扫描就能找到「之前出现过」的配对，也不会把同一个元素用两次。
  2. 存什么取决于问什么：要位置就存下标，要个数就存次数，要最早出现的位置就只在第一次出现时存。
  3. 键可以组合出来：排序后的字符串、计数元组、(行, 值) 对，都能把「同一类」放进同一个桶。

易错点

  • 先插入再查询，target 恰好等于 2x 时会把同一个元素和自己配成一对。
  • C++ 的 map[key] 读一个不存在的键会插入默认值；只想判断存在时用 find 或 count。
  • Java 里两个 Integer 用 == 比较，超过 127 时可能不相等；用 equals 或先拆箱成 int。
def two_sum(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}  # value -> index of an earlier element
    for i, x in enumerate(nums):
        if target - x in seen:  # look up before inserting: no self-pairing
            return seen[target - x], i
        seen[x] = i
    return -1, -1

KMP 前缀函数匹配 · 时间 O(n + m) · 空间 O(m)

要点

  1. pi[i] 是 pat[0..i] 中「既是真前缀又是真后缀」的最长长度；失配时 j 退回 pi[j-1]，文本指针从不回头。
  2. 建 pi 表和在文本里匹配是同一段循环：建表就是模式串和自己匹配。
  3. 解析类题目用一个下标手动往前读数字、符号和括号，边界比 split 好处理。

易错点

  • 匹配成功后要令 j = pi[j-1] 继续，否则会漏掉重叠出现（"aaaa" 里的 "aa" 出现 3 次）。
  • 在循环里用 + 拼字符串是 O(n²)；Python 先收集到列表再 join，Java 用 StringBuilder。
  • Go 里 s[i] 是字节、len(s) 是字节数；处理中文等多字节字符要先转成 []rune。
def find_all(text: str, pat: str) -> list[int]:
    """Start index of every occurrence of a non-empty pat in text."""
    m = len(pat)
    pi = [0] * m  # pi[i]: longest proper prefix of pat[:i+1] that is also its suffix
    j = 0
    for i in range(1, m):
        while j and pat[i] != pat[j]:
            j = pi[j - 1]
        if pat[i] == pat[j]:
            j += 1
        pi[i] = j
    res, j = [], 0
    for i, c in enumerate(text):
        while j and c != pat[j]:
            j = pi[j - 1]
        if c == pat[j]:
            j += 1
        if j == m:
            res.append(i - m + 1)
            j = pi[j - 1]  # keep going: matches may overlap
    return res

可变长度滑动窗口 · 时间 O(n) · 空间 O(Σ)

要点

  1. 右端每步前进一格，左端只在窗口不合法时收缩；两个指针都只前进，总共 O(n)。
  2. 求最长窗口：收缩完再更新答案；求最短窗口：在「仍然合法」的收缩循环里更新答案。
  3. 有序数组上求两数之和、去重、反转用相向双指针；判环、找中点用快慢指针。

易错点

  • 收缩时忘了把移出窗口的元素计数减一，窗口状态就和实际内容对不上。
  • 数组里有负数时，「和超过 k 就收缩」不再单调，滑动窗口失效，要改用前缀和。
  • 「恰好 k 个」很难直接滑，用「至多 k 个」减去「至多 k-1 个」。
from collections import defaultdict


def longest_unique(s: str) -> int:
    """Length of the longest substring without repeated characters."""
    cnt = defaultdict(int)  # counts inside the window s[left:right+1]
    left = best = 0
    for right, c in enumerate(s):
        cnt[c] += 1
        while cnt[c] > 1:  # shrink until the window is valid again
            cnt[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

前缀和 + 哈希计数 · 时间 O(n) · 空间 O(n)

要点

  1. 区间和等于两个前缀和之差：sum(l..r) = pre[r+1] - pre[l]；前缀数组多开一位，pre[0] = 0。
  2. 统计「和为 k 的子数组」时，哈希表先放 {0: 1}，代表从下标 0 开始的子数组。
  3. 多次区间加值用差分数组：diff[l] += v，diff[r+1] -= v，最后求一遍前缀和；合并区间先按左端点排序。

易错点

  • 忘了放 {0: 1}，会漏掉所有从下标 0 开始的子数组。
  • 前缀和很容易超过 32 位整数，C++ 用 long long，Java 用 long。
  • 先把当前前缀和存进表再查询，k = 0 时会把空子数组也算进去。
def count_subarrays(nums: list[int], k: int) -> int:
    """Number of non-empty subarrays whose sum is k (negatives allowed)."""
    seen = {0: 1}  # prefix sum -> occurrences; the empty prefix counts once
    pre = ans = 0
    for x in nums:
        pre += x
        ans += seen.get(pre - k, 0)  # sum(j..i) = pre_i - pre_j
        seen[pre] = seen.get(pre, 0) + 1
    return ans

单调栈：下一个更大元素 · 时间 O(n) · 空间 O(n)

要点

  1. 栈里存下标而不是值：既能取到值，也能算距离（比如「还要等几天才升温」）。
  2. 每个元素只进栈、出栈各一次，所以虽然套了 while，总复杂度仍是 O(n)。
  3. 求前 k 大用大小为 k 的小根堆；滑动窗口最值用单调双端队列，队头过期就弹出。

易错点

  • 有重复值时 < 和 <= 结果不同，先想清楚要「严格更大」还是「大于等于」。
  • Python 的 heapq 只有小根堆，要大根堆就存相反数。
  • Java 的 Stack 类又慢又是同步的，栈和队列都用 ArrayDeque；比较器不要写成 a - b。
def next_greater(nums: list[int]) -> list[int]:
    """For each i, the first value to the right that is strictly greater, or -1."""
    ans = [-1] * len(nums)
    stack = []  # indexes still waiting; their values decrease from bottom to top
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans

按结束时间排序选区间 · 时间 O(n log n)

要点

  1. 总是选结束最早的区间，给后面留的空间最多。交换论证：任何最优解的第一个区间都能换成它而不变差。
  2. 最少删除数 = 总数 - 最多保留数；「最少几支箭」也是同一个循环，只是端点相接也算重叠。
  3. 写贪心之前先说清楚「为什么局部最优不吃亏」；说不清楚时，多半要换成动态规划。

易错点

  • 按开始时间排序再贪心，会被一个开始很早、持续很长的区间卡住。
  • 端点相接算不算重叠由题意决定：>= 和 > 只差一个字符，答案就不一样。
  • 比较器写成 a[1] - b[1]，端点接近 ±2^31 时会溢出。
def max_non_overlapping(intervals: list[list[int]]) -> int:
    """Most intervals you can keep with no overlap; [a, b] and [b, c] may touch."""
    count, end = 0, float("-inf")
    for start, finish in sorted(intervals, key=lambda iv: iv[1]):
        if start >= end:  # fits after the last kept interval
            count += 1
            end = finish
    return count

反转链表 + 快慢指针 · 时间 O(n) · 空间 O(1)

要点

  1. 改指针之前先存下 next。反转只有三步：存 next、指回前驱、整体前移。
  2. 头结点可能被删除或替换时，先建一个哑结点 dummy 指向 head，最后返回 dummy.next。
  3. 快指针一次两步、慢指针一次一步，用来找中点和判环；找倒数第 k 个结点则让前指针先走 k 步，再和后指针同速前进。

易错点

  • 先改了 head.next 再去取 next，后面的链表就丢了。
  • 访问 fast.next.next 之前要确认 fast 和 fast.next 都不为空。
  • 把链表拆成两段后忘了把前半段的尾部置空，合并或遍历时会成环。
class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next


def reverse(head):
    prev = None
    while head:
        nxt = head.next  # save it before rewiring
        head.next = prev
        prev, head = head, nxt
    return prev


def middle(head):
    """Middle node; the second of the two middles for even lengths."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

按层 BFS · 时间 O(n) · 空间 O(最大层宽)

要点

  1. 每一轮先记下队列长度，正好处理这么多个结点，层与层就分开了。
  2. 写递归 DFS 前先想清楚「子树返回什么」：深度、是否平衡、结点数，都是把左右两边的结果合并。
  3. 前序、中序、后序的区别只在于「处理当前结点」放在两次递归的前面、中间还是后面。

易错点

  • 用一直在变化的队列长度当循环上界，会把下一层的结点也算进这一层。
  • Python 用 list.pop(0) 当队列是 O(n) 的，要用 collections.deque。
  • 树退化成链时递归深度能到 10^5，Python 会爆栈；改成迭代或调高 recursionlimit。
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def level_order(root) -> list[list[int]]:
    if not root:
        return []
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):  # exactly the nodes of this level
            node = q.popleft()
            level.append(node.val)
            for child in (node.left, node.right):
                if child:
                    q.append(child)
        levels.append(level)
    return levels

后序返回单边贡献，全局记录拐弯路径 · 时间 O(n) · 递归栈 O(h)

要点

  1. 递归函数返回「从当前结点往下走的最好单边路径」，因为要继续往上接的路径只能选一边。
  2. 在当前结点拐弯的路径（左 + 根 + 右）只用来更新全局答案，不返回给父结点。
  3. 根到叶的路径题用「进入时加、离开时减」维护当前路径；任意起点的路径和用前缀和 + 哈希表。

易错点

  • 全局答案初始化成 0，所有值都是负数的树会得到错误的 0。
  • 子树贡献为负时要截成 0（这一边不接），否则会把答案拖低。
  • 把拐弯路径也返回给父结点，等于让一条路径分叉，结果会偏大。
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def max_path_sum(root) -> int:
    """Largest sum of any non-empty path between two nodes."""
    best = float("-inf")

    def gain(node) -> int:  # best downward path sum that starts at node
        nonlocal best
        if not node:
            return 0
        left, right = max(gain(node.left), 0), max(gain(node.right), 0)
        best = max(best, node.val + left + right)  # the path that bends at node
        return node.val + max(left, right)  # only one side can continue upward

    gain(root)
    return best

前序定根，中序分左右 · 时间 O(n) · 空间 O(n)

要点

  1. 前序的第一个值是根；在中序里找到它，左边是左子树，右边是右子树。
  2. 用哈希表存「值 → 中序下标」，每次切分 O(1)，整体 O(n)。
  3. 按「先左后右」递归时，前序指针顺序往后取就是下一个根，不用计算子数组长度；后序 + 中序则从后往前取、先右后左。

易错点

  • 值有重复时中序位置不唯一，这个方法就不成立了。
  • 每层递归都切片复制数组（Python 切片、Java copyOfRange），会退化成 O(n²)。
  • 后序 + 中序时如果仍然先建左子树，取到的根的顺序就错了。
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def build_tree(preorder: list[int], inorder: list[int]):
    """Rebuild a tree with distinct values from its preorder and inorder walks."""
    pos = {v: i for i, v in enumerate(inorder)}  # value -> inorder index: O(1) splits
    roots = iter(preorder)  # preorder yields roots in exactly the order we build them

    def build(lo: int, hi: int):  # the subtree whose inorder range is [lo, hi)
        if lo == hi:
            return None
        root = TreeNode(next(roots))
        mid = pos[root.val]
        root.left = build(lo, mid)  # left before right, matching preorder
        root.right = build(mid + 1, hi)
        return root

    return build(0, len(inorder))

迭代中序：按顺序走 BST · 时间 O(h + k) · 空间 O(h)

要点

  1. BST 的中序遍历是升序的：第 k 小、验证 BST、找前驱后继，都能转成中序问题。
  2. 验证 BST 要把上下界 (lo, hi) 往下传，每个结点都必须落在祖先给出的开区间里。
  3. 查找和插入只走一条路径，复杂度是 O(h)：平衡时 O(log n)，退化成链时 O(n)。

易错点

  • 只拿结点和它的左右孩子比较，发现不了「右子树深处有比根还小的值」。
  • 用 INT_MIN / INT_MAX 当边界，结点值恰好是极值时会误判；用 long 或空值表示「无界」。
  • 迭代中序里忘了转向 node.right，会重复弹出同一批结点或者提前结束。
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def kth_smallest(root, k: int) -> int:
    """1-indexed; assumes 1 <= k <= number of nodes."""
    stack, node = [], root
    while True:
        while node:  # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()  # the next value in sorted order
        k -= 1
        if k == 0:
            return node.val
        node = node.right

多源 BFS，一步扩一圈 · O(行数 × 列数)

要点

  1. 所有起点一开始就一起入队，相当于从一个虚拟的超级源点出发；BFS 的层数就是最短距离。
  2. 入队时就标记已访问，同一个格子不会被重复加入。
  3. 只问连通块（岛屿个数、面积）时 DFS、BFS 都可以；问最少步数必须用 BFS。

易错点

  • 出队时才标记，同一个格子会被多个邻居重复入队，大网格上会超时。
  • 一开始就没有新鲜橘子时答案是 0，既不是 -1，也不是层数。
  • 递归 DFS 在 1000×1000 的网格上会爆栈；大网格用 BFS 或显式栈。
from collections import deque


def minutes_to_rot(grid: list[list[int]]) -> int:
    """0 empty, 1 fresh, 2 rotten. Minutes until nothing is fresh, or -1."""
    rows, cols = len(grid), len(grid[0])
    q = deque((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2)
    fresh = sum(row.count(1) for row in grid)
    minutes = 0
    while q and fresh:
        minutes += 1
        for _ in range(len(q)):  # every rotten cell spreads one step this minute
            r, c = q.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2  # mark when enqueued, not when popped
                    fresh -= 1
                    q.append((nr, nc))
    return -1 if fresh else minutes

并查集：路径压缩 + 按大小合并 · 每次操作约 O(α(n))

要点

  1. find 时做路径压缩，union 时把小树挂到大树下；两者一起用，单次操作几乎是常数时间。
  2. union 返回 false 说明两点本来就连通：无向图判环、找冗余连接都靠它。
  3. 连通块个数、块的大小这类信息只记在根上，合并时累加。

易错点

  • 用 parent[a] == parent[b] 判断连通是错的，必须比较 find(a) == find(b)。
  • 合并时写成 parent[a] = b，而不是把两个根连起来，会破坏树的结构。
  • 结点是字符串或坐标时，先映射成 0..n-1 的编号，或者用哈希表存 parent。
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n  # number of components

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        a, b = self.find(a), self.find(b)
        if a == b:
            return False  # already connected: this edge would close a cycle
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a  # hang the smaller tree under the larger
        self.size[a] += self.size[b]
        self.count -= 1
        return True

Kahn 算法：入度为 0 的先出队 · O(V + E)

要点

  1. 入度为 0 的点没有未完成的前置依赖，可以先放；放下之后把它指向的点入度减一。
  2. 输出的点数少于 n，说明剩下的点都在环上：「能不能修完所有课」就是这样判断的。
  3. 要求字典序最小的拓扑序时，把队列换成小根堆。

易错点

  • 边的方向读反（「a 依赖 b」应该建 b → a），整个顺序就倒过来了。
  • 只把一开始入度为 0 的点入队，后面减到 0 的点忘了入队。
  • DFS 写拓扑排序时只有「访问过 / 没访问」两种状态是判不出环的，还需要「访问中」这第三种状态。
from collections import deque


def topo_order(n: int, edges: list[tuple[int, int]]) -> list[int]:
    """Edge (u, v) means u comes before v. Returns [] if there is a cycle."""
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:  # every prerequisite of v is placed
                q.append(v)
    return order if len(order) == n else []

Dijkstra：堆 + 懒删除 · O((V + E) log V)

要点

  1. 每次从堆里取出当前距离最小的点，它的距离就确定了；前提是所有边权非负。
  2. 不做 decrease-key：直接把新距离压进堆，弹出时发现比 dist 大就跳过（懒删除）。
  3. 边权只有 0 和 1 时用双端队列 BFS；有负权用 Bellman-Ford；状态里带「已用次数」时，把 (点, 次数) 当成一个新结点。

易错点

  • 不跳过过期的堆元素，同一个点会被反复松弛，稠密图上会超时。
  • 距离累加超出 32 位整数；用 INT_MAX 当无穷大时，d + w 还会溢出成负数。
  • 有向图当成无向图建边（或者反过来），所有距离都会错。
import heapq


def dijkstra(n: int, edges: list[tuple[int, int, int]], src: int) -> list[int]:
    """Directed edges (u, v, w) with w >= 0. Unreachable nodes get -1."""
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
    dist = [float("inf")] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale entry: u was settled with a shorter distance
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return [d if d != float("inf") else -1 for d in dist]

Kruskal：按边权排序 + 并查集 · O(E log E)

要点

  1. 按边权从小到大看每条边：能连起两个不同连通块就选，否则跳过（选了会成环）。
  2. 选够 n-1 条边就是一棵生成树；最后不够 n-1 条，说明图不连通。
  3. 点少边多的稠密图（比如坐标点两两相连）用 O(n²) 的 Prim，往往比给所有边排序更快。

易错点

  • 没检查是否连通，直接返回累加的边权。
  • 坐标点两两连边有 n²/2 条，内存和排序时间都可能超限。
  • 点的编号从 1 开始，并查集却只开了 n 个位置。
def mst_weight(n: int, edges: list[tuple[int, int, int]]) -> int:
    """Undirected edges (u, v, w). Weight of a minimum spanning tree, or -1 if disconnected."""
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = used = 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru != rv:  # the lightest edge joining two different components
            parent[ru] = rv
            total += w
            used += 1
    return total if used == n - 1 else -1

选择、递归、撤销；同层跳过重复 · O(n · 2^n)

要点

  1. 模板只有三步：做选择、递归、撤销选择；path 是整个搜索共用的一份。
  2. 先排序，再用 i > start && nums[i] == nums[i-1] 跳过：同一层不重复选相同的值，更深的层可以。
  3. 组合从 start 往后选，避免 {1,2} 和 {2,1} 同时出现；排列每次从头选，用 used 数组标记。

易错点

  • 结果里直接存 path 的引用，回溯结束后所有结果都变成同一个空列表。
  • 把 i > start 写成 i > 0，更深层里合法的重复值也会被跳过。
  • 忘了先排序，相同的值不相邻，去重判断就失效了。
def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)  # equal values become neighbours
    res, path = [], []

    def dfs(start: int) -> None:
        res.append(path[:])  # copy: path keeps changing
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue  # this value was already tried at this level
            path.append(nums[i])
            dfs(i + 1)
            path.pop()  # undo the choice

    dfs(0)
    return res

按切分点回溯 + 回文预处理 · O(n · 2^n)

要点

  1. 回溯的每一层决定「下一段切到哪里」，start 走到 n 就得到一种完整的切法。
  2. 先用 O(n²) 的区间 DP 算出每个子串是不是回文，回溯里的判断就是 O(1)。
  3. 复原 IP 地址、单词拆分也是同一个框架，只是「这一段是否合法」的判断不同。

易错点

  • 在回溯里每次都重新用双指针判断回文，重复计算会让常数大很多。
  • 只要求方案数或最少切几刀时，不要枚举，改用 DP。
  • 子串下标是左闭右开还是左闭右闭要统一；s[start:end+1] 和 substring(start, end+1) 很容易差一位。
def partition(s: str) -> list[list[str]]:
    """Every way to cut s into palindromes."""
    n = len(s)
    pal = [[False] * n for _ in range(n)]  # pal[i][j]: s[i..j] is a palindrome
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    res, path = [], []

    def dfs(start: int) -> None:
        if start == n:
            res.append(path[:])
            return
        for end in range(start, n):  # the next piece is s[start..end]
            if pal[start][end]:
                path.append(s[start : end + 1])
                dfs(end + 1)
                path.pop()

    dfs(0)
    return res

N 皇后：按列和两条对角线剪枝 · 最坏 O(n!)

要点

  1. 每行只放一个皇后，搜索树只在列上分叉；列、主对角线 r-c、副对角线 r+c 各用一个数组标记。
  2. 剪枝越早越好：递归之前就判断冲突，而不是放满整个棋盘再检查。
  3. 数独、组合总和这类题先排序，在「剩下的值已经不可能满足」时用 break，比 continue 省得多。

易错点

  • 主对角线下标 r-c 会是负数，要加上 n-1 的偏移。
  • 回溯返回前忘了把标记改回去，后面的分支全被误剪。
  • 需要输出棋盘时，用可变的字符数组逐格修改，最后再转字符串，不要每一步都复制整盘。
def total_queens(n: int) -> int:
    """Number of ways to place n non-attacking queens on an n x n board."""
    cols, diag, anti = [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1)

    def place(r: int) -> int:
        if r == n:
            return 1
        count = 0
        for c in range(n):
            d = r - c + n - 1  # shift r - c into 0..2n-2
            if cols[c] or diag[d] or anti[r + c]:
                continue  # attacked: prune this branch
            cols[c] = diag[d] = anti[r + c] = True
            count += place(r + 1)
            cols[c] = diag[d] = anti[r + c] = False  # undo
        return count

    return place(0)

一维 DP + 滚动变量 · 时间 O(n) · 空间 O(1)

要点

  1. 先用一句话定义状态，比如 dp[i] = 只看前 i 个元素时的最优值；状态说清楚了，转移通常就出来了。
  2. 转移只看「最后一步做了什么」：第 i 个选还是不选，最后一跳是 1 步还是 2 步。
  3. dp[i] 只依赖前一两项时，用两个变量滚动，空间从 O(n) 降到 O(1)。

易错点

  • dp 和输入的下标错位：dp 多开一位时 dp[0] 表示「什么都没选」，答案在 dp[n]。
  • 滚动更新时先覆盖了 prev1 再拿它算新值，用到的已经是新数据了。
  • 方案数很快会超出 64 位；题目要求取模时，每一步都要取模。
def rob(nums: list[int]) -> int:
    """Largest sum of elements with no two adjacent."""
    prev2 = prev1 = 0  # best totals up to i-2 and up to i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)  # skip x, or take it after i-2
    return prev1

网格 DP 压成一行 · 时间 O(行数 × 列数) · 空间 O(列数)

要点

  1. dp[r][c] 只依赖上方和左方，按行从左到右填，一行数组就够：更新前 dp[c] 是上方，dp[c-1] 是左方。
  2. 第一行、第一列只有一个来源，要么单独处理，要么用无穷大哨兵统一写法。
  3. 路径计数就把 min 换成加法；有障碍的格子直接置 0。

易错点

  • 哨兵用 INT_MAX 再加上格子值会溢出，要保证只在有限值上做加法。
  • 允许往四个方向走时没有填表顺序，DP 不成立，要用 BFS 或 Dijkstra。
  • 压成一行之后，如果转移还需要左上角的值，要在它被覆盖前先存到变量里。
def min_path_sum(grid: list[list[int]]) -> int:
    """Cheapest path from top-left to bottom-right moving only right or down."""
    cols = len(grid[0])
    dp = [float("inf")] * cols  # before row r is filled, dp[c] holds row r-1
    dp[0] = 0
    for row in grid:
        for c in range(cols):
            left = dp[c - 1] if c else float("inf")
            dp[c] = min(dp[c], left) + row[c]  # from above (old dp[c]) or the left (new dp[c-1])
    return dp[-1]

0/1 背包倒序，完全背包正序 · O(n × target)

要点

  1. 0/1 背包倒序遍历容量，保证 dp[s-x] 还是「没用过 x」的旧值；完全背包正序遍历，允许同一件物品重复使用。
  2. 物品在外层、容量在内层，数的是组合（不计顺序）；容量在外层、物品在内层，数的是排列。
  3. 很多题要先转化成背包：「分成两个和相等的子集」= 能否凑出 sum/2；「目标和」= 凑出 (sum+target)/2。

易错点

  • 0/1 背包写成正序，同一件物品会被用很多次。
  • 计数问题 dp[0] = 1（什么都不选也是一种方案）；求最值问题 dp[0] = 0，其余初始化为无穷。
  • 转化成 (sum+target)/2 之前没检查奇偶性和正负，会得到错误的下标。
def count_subsets(nums: list[int], target: int) -> int:
    """Ways to pick a subset (each item at most once) that sums to target."""
    dp = [1] + [0] * target  # dp[s]: ways to reach sum s
    for x in nums:
        for s in range(target, x - 1, -1):  # backwards: x is used at most once
            dp[s] += dp[s - x]
    return dp[target]


def count_combinations(coins: list[int], amount: int) -> int:
    """Ways to make amount with unlimited coins, order ignored."""
    dp = [1] + [0] * amount
    for coin in coins:  # coins outside: each multiset is counted once
        for s in range(coin, amount + 1):  # forwards: a coin may be reused
            dp[s] += dp[s - coin]
    return dp[amount]

LIS：tails 数组 + 二分 · O(n log n)

要点

  1. tails[k] 是长度为 k+1 的递增子序列可能的最小结尾；它本身是递增的，所以可以二分。
  2. 严格递增用 lower_bound（第一个 ≥ x），非递减用 upper_bound（第一个 > x）。
  3. 二维的「信封嵌套」先按宽升序、宽相同时按高降序排序，再对高做 LIS。

易错点

  • tails 数组不是真实存在的最长子序列，只有长度是对的；要输出方案得另外记录前驱。
  • 严格和非严格用错了二分函数，重复元素多的用例会差 1 甚至更多。
  • 要求「最长子序列有几个」时，O(n log n) 写法不够，要回到 O(n²) 的 dp 加计数数组。
from bisect import bisect_left


def lis_length(nums: list[int]) -> int:
    """Length of the longest strictly increasing subsequence."""
    tails = []  # tails[k]: smallest tail of an increasing subsequence of length k+1
    for x in nums:
        i = bisect_left(tails, x)  # bisect_right for non-decreasing
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

双串 DP：dp[i][j] 看两个前缀 · O(m × n)

要点

  1. dp[i][j] 定义在前缀上：a 的前 i 个字符和 b 的前 j 个字符；多开一行一列表示空串。
  2. 末尾字符相等就继承 dp[i-1][j-1]；不相等时，替换、删除、插入分别对应左上、上、左三个格子。
  3. 最长公共子序列、不同的子序列、通配符匹配都是这张表，只是转移不同。

易错点

  • dp 的下标是前缀长度，对应的字符是 a[i-1]；写成 a[i] 会错一位。
  • 忘了初始化第 0 行和第 0 列（变成空串需要删 i 次，从空串变来需要插 j 次）。
  • 压成一行时，左上角的值会被本行覆盖，需要额外一个变量保存。
def edit_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    # dp[i][j]: edits to turn a[:i] into b[:j]; row 0 and column 0 are the empty prefixes
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:  # replace, delete from a, insert into a
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

区间 DP：左端点倒序枚举 · O(n²)

要点

  1. dp[i][j] 只依赖更短的区间 dp[i+1][*] 和 dp[*][j-1]，所以 i 倒序、j 正序填表。
  2. 两端字符相等就向内收缩并加 2，否则去掉一端，取两种情况的较大值。
  3. 只问回文子串（必须连续）时，中心扩展法 O(n²) 时间、O(1) 空间，更简单。

易错点

  • i 正序枚举时 dp[i+1][*] 还没有算出来，结果全错。
  • 子序列（可以不连续）和子串（必须连续）是两道题，转移不能混用。
  • 中心扩展要同时试奇数中心 (i, i) 和偶数中心 (i, i+1)。
def longest_pal_subseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]  # dp[i][j]: answer for s[i..j]
    for i in range(n - 1, -1, -1):  # i backwards so dp[i+1][*] is ready
        dp[i][i] = 1
        for j in range(i + 1, n):
            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] if n else 0

以 i 结尾的状态：同时记最大和最小 · 时间 O(n) · 空间 O(1)

要点

  1. 状态定义成「以 i 结尾」，连续子数组的转移就只有两种：接在前一段后面，或者从 i 重新开始。
  2. 乘法遇到负数时最大会变成最小，所以要同时维护最大和最小两个状态。
  3. 状态机 DP 就是给每个位置多设几个状态（持有 / 不持有、上一个选没选），把状态之间的每条转移都写出来。

易错点

  • 先更新了 hi 再用新的 hi 去算 lo，用到的是同一轮已经改过的值。
  • 答案初始化成 0，全是负数的数组就会出错。
  • 最大子数组和（Kadane）的转移是 cur = max(x, cur + x)，不要漏掉「重新开始」这一项。
def max_product(nums: list[int]) -> int:
    """Largest product of a non-empty contiguous subarray."""
    hi = lo = best = nums[0]  # max and min product of a subarray ending here
    for x in nums[1:]:
        cand = (x, hi * x, lo * x)  # restart, or extend; a negative x swaps max and min
        hi, lo = max(cand), min(cand)
        best = max(best, hi)
    return best

持有 / 冷却 / 空仓三状态 · 时间 O(n) · 空间 O(1)

要点

  1. 先写清楚每天结束时可能处于哪几种状态，再写「昨天的哪种状态 + 今天的什么动作」能到达它。
  2. 同一天的几个新值都要用前一天的旧值计算，所以要同时赋值或者先存临时变量。
  3. 最多 k 次交易就加一维 k；手续费在每次卖出（或买入）时扣一次；只交易一次就是「记录历史最低价」。

易错点

  • 持有状态初始化成 0，相当于第 0 天白送了一股。
  • 用负无穷做初值时，C++ / Java 里 hold + p 会溢出；取 MIN / 2 这样的值。
  • 有冷却期时，买入只能从「空仓」状态转过来，不能从「刚卖出」状态直接买。
def max_profit_cooldown(prices: list[int]) -> int:
    """Unlimited trades, but after selling you must wait one day before buying."""
    hold, cool, free = float("-inf"), 0, 0  # profit at the end of a day in each state
    for p in prices:
        hold, cool, free = (
            max(hold, free - p),  # keep holding, or buy today (only from free)
            hold + p,  # sell today
            max(free, cool),  # rest
        )
    return max(cool, free)

按结束时间排序 + 二分找上一个兼容任务 · O(n log n)

要点

  1. 按结束时间排序后，dp[i] = 前 i 个任务的最优值；第 i 个任务要么不选，要么接在最后一个不冲突的任务后面。
  2. 「最后一个不冲突的任务」在结束时间数组里二分查找，整体 O(n log n)。
  3. 「把数组分成 k 段」这类题，状态通常是 dp[段数][结尾位置]，转移时枚举最后一段从哪里开始。

易错点

  • 首尾相接算不算冲突，决定了用 upper_bound 还是 lower_bound。
  • 按开始时间排序、每次贪心选利润最高的，在带权的版本里不成立。
  • 排序时只排了结束时间，开始时间和利润没有跟着一起动。
from bisect import bisect_right


def max_profit(start: list[int], end: list[int], profit: list[int]) -> int:
    """Best total profit of non-overlapping jobs; a job may start when another ends."""
    jobs = sorted(zip(end, start, profit))
    ends = [e for e, _, _ in jobs]
    dp = [0] * (len(jobs) + 1)  # dp[i]: best using the first i jobs by end time
    for i, (_, s, p) in enumerate(jobs):
        k = bisect_right(ends, s, 0, i)  # jobs[:k] all end by time s
        dp[i + 1] = max(dp[i], dp[k] + p)  # skip job i, or take it after jobs[:k]
    return dp[-1]

树形 DP：每个结点返回（选，不选） · O(n)

要点

  1. 树形 DP 用后序遍历：先拿到左右子树的结果，再算当前结点，每个结点返回一个小元组。
  2. 按「当前结点选不选」拆状态，比在父结点里往下看两层更简单，也不会重复计算。
  3. 两人博弈题常用「当前先手比对手多拿多少」作为状态：dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])。

易错点

  • 不返回元组，而是用「祖父 + 孙子」的写法又不做记忆化，会指数级重复计算。
  • 不选当前结点时，孩子也不一定要选，每个孩子都要取 max(选, 不选)。
  • 博弈题如果按「我的得分」建状态，往往还得再记对手的得分；用差值更省事。
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def rob_tree(root) -> int:
    """Largest sum of node values with no parent-child pair both taken."""

    def dfs(node) -> tuple[int, int]:  # (best if node is taken, best if it is not)
        if not node:
            return 0, 0
        lt, ls = dfs(node.left)
        rt, rs = dfs(node.right)
        take = node.val + ls + rs  # children must be skipped
        skip = max(lt, ls) + max(rt, rs)  # children are free to choose
        return take, skip

    return max(dfs(root))

惰性迭代器：hasNext 负责前进 · 每次调用均摊 O(1)

要点

  1. 把「跳过空行、走到下一个有效元素」放进 hasNext，next 只负责取值；这样连续调用多次 hasNext 也没有副作用。
  2. 只保存位置（行号、列号），不要在构造函数里把所有元素复制成一个大数组。
  3. 任意深度的嵌套列表用一个栈保存各层的位置；Python 里用生成器 yield from 最自然。

易错点

  • 中间或末尾有空行时，hasNext 只看下一行就会返回错误的 true。
  • next 里不先调用 hasNext，直接取值会越界。
  • 迭代过程中修改了原容器：Java 会抛 ConcurrentModificationException，其他语言则是悄悄出错。
class Flatten2D:
    """Iterates a list of lists in order, skipping empty rows."""

    def __init__(self, rows: list[list[int]]):
        self.rows, self.r, self.c = rows, 0, 0

    def has_next(self) -> bool:
        while self.r < len(self.rows) and self.c == len(self.rows[self.r]):
            self.r, self.c = self.r + 1, 0  # skip finished and empty rows
        return self.r < len(self.rows)

    def next(self) -> int:
        if not self.has_next():
            raise StopIteration
        self.c += 1
        return self.rows[self.r][self.c - 1]

LRU：哈希表 + 双向链表 · get 与 put 均为 O(1)

要点

  1. 哈希表负责 O(1) 找到结点，双向链表负责 O(1) 把结点移到头部、删除尾部。
  2. get 也算一次「使用」，要把结点移到最新的一端；put 一个已存在的键要更新值并移动，而不是再插一份。
  3. 面试要求手写链表时，用头尾两个哨兵结点，插入删除就不用判断空指针。

易错点

  • 淘汰尾结点时只删了链表、没删哈希表里的键（或者反过来）。
  • 先插入再淘汰还是先淘汰再插入要统一，并想清楚容量为 0 这种边界。
  • 链表结点里不存 key，淘汰时就不知道该删哈希表里的哪一项。
from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.data = OrderedDict()  # a hash map over a doubly linked list; the end is most recent

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)  # mark as most recently used
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)  # evict the least recently used

字典树：结点存孩子和计数 · 每次操作 O(单词长度)

要点

  1. 每个结点代表一个前缀；插入和查询都是顺着字符往下走，耗时只和单词长度有关。
  2. 结点上存计数（有多少单词经过、有多少单词在此结束），前缀计数和删除都能 O(L) 完成。
  3. 序列化二叉树用前序遍历加空结点标记（如 "#"），反序列化时按同样的顺序递归读回来。

易错点

  • 把 search（完整单词）和 startsWith（前缀）混为一谈，忘了检查结束标记。
  • 固定 26 叉数组默认只有小写字母；有大写、数字或 Unicode 时，孩子改用哈希表存。
  • 序列化时值之间不加分隔符，多位数和负数就没法还原。
class Trie:
    def __init__(self):
        self.children: dict[str, Trie] = {}
        self.prefix = 0  # words passing through this node
        self.words = 0  # words ending exactly here

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
            node.prefix += 1
        node.words += 1

    def _walk(self, s: str):
        node = self
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def count_word(self, word: str) -> int:
        node = self._walk(word)
        return node.words if node else 0

    def count_prefix(self, prefix: str) -> int:
        node = self._walk(prefix)
        return node.prefix if node else 0

位运算小工具与快速幂 · O(log n)

要点

  1. x & (x-1) 去掉最低位的 1，x & -x 取出最低位的 1；异或满足 a ^ a = 0，可以找出只出现一次的数。
  2. 快速幂把指数按二进制拆开：每轮把底数平方，指数这一位是 1 就乘进结果，O(log exp)。
  3. 不超过 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 会直接编译报错）。
def popcount(x: int) -> int:
    """Set bits in a non-negative x (int.bit_count() in Python 3.10+)."""
    count = 0
    while x:
        x &= x - 1  # clear the lowest set bit
        count += 1
    return count


def pow_mod(base: int, exp: int, mod: int) -> int:
    """base ** exp % mod by repeated squaring (the built-in pow(base, exp, mod) does the same)."""
    result, base = 1 % mod, base % mod
    while exp:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result