Python 标准库: 被"遗忘"的编程基本功

刷算法题有一条被反复验证的经验：“数据结构”用库，”算法思维”手撕。 标准库不是算法题的”作弊器”，而是 “答题卡”：容器、排序、查找、缓存这些工程性能力，Python 已经替你优化到了极致；而二分、快排、归并、递归、 回溯这些”方法论”，才是面试真正想考察的东西，必须能脱离库写出来。这篇文章的目的，就是把这两件事的边界 划清楚，并用 LeetCode 中低难度高频题逐个演示：什么时候一行库调用就能搞定，什么时候必须老老实实手撕。 每一道例题都给出完整题目描述与时间/空间复杂度，方便你在不看原题的情况下也能独立推演。

一张”该手撕还是该用库”的决策地图

先给出全文的纲领，之后每一章都是在为这张表补充证据：

问题类型	策略	首选工具
栈	直接用库	list（append / pop）
队列 / 双端队列	直接用库	collections.deque
堆 / Top-K / 中位数	直接用库	heapq
哈希计数、分组、去重	直接用库	dict / set / Counter / defaultdict
业务排序（稳定、带 key）	直接用库	sorted / list.sort
快速排序（partition 思想）	必须手撕	自己实现
归并排序（分治与逆序对）	必须手撕	自己实现
有序数组定位（a[i] >= x 这类）	直接用库	bisect
二分（自定义单调判定）	必须手撕	自己实现
递归	必须手撕	自己实现
回溯 / 组合枚举（需要剪枝）	必须手撕	自己实现
组合枚举（无剪枝、结果量小）	直接用库	itertools
树 DFS / BFS	半手撕	递归 + deque
图 BFS / 拓扑排序	模板 + 库	defaultdict + deque
动态规划记忆化	直接用库	functools.lru_cache
动态规划表格	手写数组	list

判断标准只有一句话：标准库提供的是”容器”和”原语”，二分、快排、归并、递归、回溯是”方法论”。容器可以买现成的， 方法论必须内化。 面试官让你手撕二分，不是不知道 bisect 存在，而是想确认你真的理解”减半搜索”这个思维模型。

第一章 内建容器：你的第一层轮子库

四种内建容器覆盖了算法题 80% 的”装数据”需求。先记住它们的代价，选错容器往往是超时的根源：

容器	特性	关键复杂度
list	有序、可重复、可切片	尾部 append/pop O(1)；索引 O(1)；中部插入/删除 O(n)；in O(n)
dict	键值映射	增、删、查平均 O(1)
set	无序、去重、成员判断	增、删、查平均 O(1)
tuple	只读 list、可哈希	同 list（不可变）

选择指南：

• 需要按顺序存放 → list；
• 需要按键取值、给每个元素配”状态” → dict；
• 需要去重或判断是否存在 → set；
• 需要放进 set/dict 作为键、或作为不可变参数 → tuple。

常用小技巧（都属于内建能力，不需要任何 import）。切片反转、zip 转置、enumerate 带下标遍历均为 O(n)；dict.get 为 O(1)：

nums = [1, 2, 3, 4, 5]
nums[::-1]                        # 反转：[5, 4, 3, 2, 1]（时间 O(n)，空间 O(n)）
max(nums, key=lambda x: -x)       # max(iterable, key=None)：按 key 找最值；iterable 为数据源，时间 O(n)。
sorted(nums, reverse=True)        # sorted(iterable, key=None, reverse=False)：返回新列表；reverse=True 表示降序，O(n log n)。
list(zip([1, 2], ['a', 'b']))     # zip(*iterables)：按位置配对多个可迭代对象，默认到最短者结束，O(n)。
[(i, v) for i, v in enumerate(nums)]      # enumerate(iterable, start=0)：同时提供下标和值；start 为起始下标，O(n)。
words = ['a', 'bb', 'c']
sorted(words, key=len)            # key=len：把每个元素映射为长度后排序，返回新列表，O(n log n)。

进阶技巧：zip(*matrix) 可以转置二维矩阵；set(nums) 可以一行去重；dict.get(k, default) 可以在 键不存在时返回默认值而不是抛 KeyError，是算法题里最常用的”防呆”写法。

例题 1：LeetCode 242 有效的字母异位词（简单）

题目：给定两个字符串 s 和 t，判断 t 是否为 s 的字母异位词（组成字符相同、每个字符出现次数相同， 只是排列顺序不同）。例如 s = "anagram"、t = "nagaram" 时返回 true。

异位词 = 两个字符串的字符出现次数完全一致。用 Counter 直接比较计数即可：

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)  # Counter(iterable)：统计元素频次；s/t 为字符序列，时间 O(n)、空间 O(k)。

备选方案是 sorted(s) == sorted(t)（O(n log n)），而 Counter 是 O(n)。字符串不长时两种都行，但 Counter 传递了一个更重要的信号：“统计每个元素出现次数”这件事，官方已经替你做好了。

复杂度：时间 O(n)（n 为字符串长度）；空间 O(1)（本题字符集固定为 26 个小写字母，可视为常数）。 若字符集不受限，空间为 O(k)，k 为字符种类数。

例题 2：LeetCode 1 两数之和（简单）

题目：给定整数数组 nums 和目标值 target，返回和为 target 的两个元素的下标。每个输入恰好只有一个 答案，且同一元素不能重复使用。例如 nums = [2,7,11,15]、target = 9，返回 [0, 1]。

暴力是 O(n²)，用 dict 把”见过的值”记下来，把查找降为 O(1)：

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

这就是”空间换时间”的第一次亮相：dict 不是用来”存”，而是用来”回忆”。

复杂度：时间 O(n)（单次遍历，dict 查增均摊 O(1)）；空间 O(n)（哈希表最多存 n 个键值对）。

第二章 内置函数与 math：把数学题的脏活交给官方

一组高频内置函数，它们让很多“手写几行”变成“一行调用”。下面的复杂度按算法题中固定整数范围近似；Python 任意精度大整数还会受位数影响：

abs(-3)                        # abs(x)：返回 x 的绝对值；x 为数值，时间 O(1)。
divmod(17, 5)                  # divmod(a, b)：同时返回 a 除以 b 的商和余数，时间 O(1)。
pow(2, 10, 1000)               # pow(base, exp, mod)：计算 base**exp % mod；mod 可省略，快速幂约 O(log exp)。
all([True, 1, 'x'])            # all(iterable)：判断是否全部为真；iterable 为可迭代对象，最坏 O(n)。
any([0, '', None])             # any(iterable)：判断是否至少一个为真；遇到真值会提前结束，最坏 O(n)。
sum([1, 2, 3])                 # sum(iterable, start=0)：从 start 开始累加 iterable，时间 O(n)。
bin(5); oct(8); hex(255)       # 分别把整数 x 转为二/八/十六进制字符串，输出长度决定复杂度。
int('ff', 16)                  # int(x, base=10)：按 base 进制解析 x；x 为数字字符串，时间 O(len(x))。

math 模块是数值题的官方军火库（Python 3.8+ 起有 comb/perm/isqrt，3.9+ 起有 lcm）。 以下复杂度以常见固定整数范围近似；处理超大整数时还要考虑整数位数：

import math

math.gcd(12, 18)               # gcd(*integers)：求多个整数的最大公约数，约 O(log min(|a|, |b|))。
math.lcm(4, 6)                 # lcm(*integers)：求多个整数的最小公倍数，复杂度与 gcd 同量级。
math.factorial(10)             # factorial(n)：计算非负整数 n 的阶乘；n 为非负整数，约 O(n) 次乘法。
math.comb(10, 3)               # comb(n, k)：计算 n 选 k；n 为总数、k 为选取数，约 O(min(k, n-k))。
math.perm(10, 3)               # perm(n, k)：计算 n 排列 k；n 为总数、k 为选取数，约 O(k)。
math.isqrt(17)                 # isqrt(n)：返回 n 的整数平方根；n 为非负整数，固定范围可近似 O(1)。
math.ceil(3.2)                 # ceil(x)：向上取整；x 为实数，时间 O(1)。
math.floor(3.8)                # floor(x)：向下取整；x 为实数，时间 O(1)。
math.inf                       # 正无穷常量，常用于初始化 min/max；读取时间 O(1)。
math.prod([2, 3, 5])           # prod(iterable, start=1)：从 start 开始连乘，时间 O(n)。

例题 3：LeetCode 268 缺失数字（简单）

题目：给定一个包含 n 个互不相同数字的数组，元素取值来自 0, 1, ..., n，找出缺失的那一个。 例如 nums = [3, 0, 1] 时缺失 2。

0..n 的和减去数组和，差就是缺失值：

def missing_number(nums: list[int]) -> int:
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

复杂度：时间 O(n)（一次求和）；空间 O(1)（只用常数个变量）。

例题 4：LeetCode 367 有效的完全平方数（简单）

题目：给定正整数 num，判断它是否是完全平方数（即存在整数 x 使 x * x == num）， 且不能直接使用内置的 sqrt 库函数。例如 16 返回 true，14 返回 false。

用 isqrt 取整数平方根再平方回验，天然规避浮点误差：

import math

def is_perfect_square(num: int) -> bool:
    r = math.isqrt(num)
    return r * r == num

复杂度：时间 O(1)（isqrt 为固定位宽的整数运算）；空间 O(1)。

例题 5：LeetCode 1492 n 的第 k 个因子（中等）

题目：给定正整数 n 和整数 k，按升序返回 n 的第 k 个因子（能整除 n 的正整数）；若因子不足 k 个则返回 -1。例如 n = 12、k = 3 时，因子为 [1, 2, 3, 4, 6, 12]，答案是 3。

因子成对出现，只需要扫到 sqrt(n)：

import math

def kth_factor(n: int, k: int) -> int:
    factors = []
    for i in range(1, math.isqrt(n) + 1):
        if n % i == 0:
            factors.append(i)
            if i != n // i:
                factors.append(n // i)
    factors.sort()
    return factors[k - 1] if k <= len(factors) else -1

复杂度：时间 O(√n)（只遍历到 √n，排序因子数 2√n 级别为 O(√n log √n)，可合并表述为 O(√n log n)）； 空间 O(√n)（因子列表）。

第三章 栈：list 就是你要的栈

很多语言需要手写 Stack 类，Python 不需要：list.append 和 list.pop 都在尾部操作，均摊 O(1)， 这就是栈的全部语义。不要再手写一个 Stack 类，直接 stack = [] 即可。

stack = []
stack.append(1)     # 压栈（均摊 O(1)）
stack.append(2)
stack[-1]           # 看栈顶：2（O(1)）
stack.pop()         # 出栈：2（均摊 O(1)）
len(stack) == 0     # 判空（O(1)）

栈的经典场景：括号匹配、表达式求值、单调栈、迭代式 DFS。

例题 6：LeetCode 20 有效的括号（简单）

题目：给定一个只包含 (、)、[、]、{、} 的字符串 s，判断括号是否有效匹配（左括号必须用 相同类型的右括号闭合，且按正确顺序闭合）。例如 s = "()[]{}" 返回 true，s = "([)]" 返回 false。

左括号入栈，右括号与栈顶配对：

def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

复杂度：时间 O(n)（每个字符入栈/出栈恰好一次）；空间 O(n)（栈最深可达 n）。

例题 7：LeetCode 232 用栈实现队列（中等）

题目：使用两个栈实现一个先入先出（FIFO）队列，支持 push（入队）、pop（出队并返回队首）、 peek（查看队首）、empty（判空）四个操作。

两个栈倒手，就能把”后进先出”变成”先进先出”：只在 out 栈为空时批量倒腾。

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self._pour()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._pour()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def _pour(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

复杂度：时间 均摊 O(1)（每个元素最多被 push/pop 各两次，整体线性）；空间 O(n)（两个栈合计存所有元素）。

例题 8：LeetCode 739 每日温度（中等）——单调栈

题目：给定每日温度数组 temperatures，返回一个等长数组，其中每个位置表示”要等多少天才会出现更高的 温度”；若之后没有更高温度则为 0。例如 [73,74,75,71,69,72,76,73] 返回 [1,1,4,2,1,1,0,0]。

“下一个更大元素”一类问题，暴力是 O(n²)，单调栈能压到 O(n)：栈里维护还没找到答案的下标， 且栈中温度单调递减。当前温度比栈顶大时，栈顶的答案就是”今天”：

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    res = [0] * n
    stack = []                       # 存下标
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

注意这里的”轮子”是 list，但单调栈本身是算法思想：栈是容器，用单调性维护栈是思维，这个边界要分清。

复杂度：时间 O(n)（每个下标至多入栈、出栈各一次）；空间 O(n)（单调栈与结果数组）。

第四章 队列与 deque：BFS 与滑动窗口的引擎

list 能当栈，但当队列是灾难：list.pop(0) 要把后面所有元素往前挪，是 O(n)。所以队列要用 collections.deque（双端队列），两端的 append/popleft 都是 O(1)：

from collections import deque

dq = deque([1, 2, 3])    # deque(iterable=(), maxlen=None)：从 iterable 初始化，可选 maxlen 限制长度。
dq.append(4)             # append(x)：把 x 放到队尾，时间 O(1)。
dq.appendleft(0)         # appendleft(x)：把 x 放到队首，时间 O(1)。
dq.popleft()             # popleft()：移除并返回队首元素，非空时 O(1)。
dq.pop()                 # pop()：移除并返回队尾元素，非空时 O(1)。
dq[0]; dq[-1]            # 两端索引读取 O(1)；中间位置索引可能是 O(n)。
dq.rotate(1)             # rotate(n=1)：右旋 n 步；n 为步数，约 O(min(|n|, len(dq)))。

BFS 标准模板

广度优先搜索的本质是”一层一层扩展”，天然用队列实现。模板只有四行核心逻辑：

def bfs(start):
    dq = deque([start])
    seen = {start}
    step = 0
    while dq:
        for _ in range(len(dq)):        # 按层处理
            node = dq.popleft()
            # 访问 node；若到达目标，返回 step
            for nxt in neighbors(node): # 扩展下一层
                if nxt not in seen:
                    seen.add(nxt)
                    dq.append(nxt)
        step += 1

for _ in range(len(dq)) 这一行是”分层的灵魂”：它保证一次循环处理完整的一层，从而能统计步数。

复杂度：时间 O(V + E)（V 为节点数、E 为边数，每个节点入队出队一次、每条边检查一次）；空间 O(V) （队列与 seen 集合）。

例题 9：LeetCode 933 最近的请求次数（简单）

题目：实现 RecentCounter 类。调用 ping(t) 时传入单调递增的时间戳 t，返回过去 3000 毫秒内 （闭区间 [t-3000, t]）的 ping 调用次数。例如依次调用 ping(1)、ping(100)、ping(3001)、 ping(3002) 返回 1, 2, 3, 3。

deque 天然就是”滑动时间窗”：

from collections import deque

class RecentCounter:
    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        self.q.append(t)
        while self.q[0] < t - 3000:     # 弹出过期请求
            self.q.popleft()
        return len(self.q)

复杂度：时间 均摊 O(1)（每个时间戳入队、出队各一次，整体线性）；空间 O(n)（窗口内的请求数）。

例题 10：LeetCode 643 子数组最大平均数 I（简单）——滑动窗口入门

题目：给定整数数组 nums 和整数 k，找出长度为 k 的连续子数组的最大平均值，以浮点数返回。 例如 nums = [1,12,-5,-6,50,3]、k = 4，最大平均值为 12.75。

定长窗口：先进一个，再”滑”着更新和。滑动窗口 = 维护窗口的增删，而不是每步重新求和。

def find_max_average(nums: list[int], k: int) -> float:
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # 进一个出一个
        best = max(best, window)
    return best / k

复杂度：时间 O(n)（每个元素进窗口、出窗口各一次）；空间 O(1)。

例题 11：LeetCode 3 无重复字符的最长子串（中等）——可变长滑动窗口

题目：给定字符串 s，找出其中不含重复字符的最长子串的长度。例如 s = "abcabcbb"，答案为 3 （子串 "abc"）。

left/right 两个下标维护窗口，set 记录窗口内字符。右指针遇到重复字符时，左指针收缩到不重复为止：

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:               # 收缩左边界
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

复杂度：时间 O(n)（左右指针各至多移动 n 次）；空间 O(k)（k 为字符集大小，也可表述为 O(min(n, k))）。

进阶延伸（困难，非主打）：LeetCode 239 滑动窗口最大值。用”单调递减双端队列”维护窗口内候选最大值的下标， 队首永远是当前窗口最大值。它是滑动窗口题的集大成者，建议先掌握上面两个中档题再攻它。 该题最优解时间 O(n)、空间 O(k)。

第五章 堆 heapq：最小堆哲学与 Top-K 问题

heapq 提供最小堆：heap[0] 永远是堆里最小的元素。API 不多，全部 O(log n) 或 O(1)：

import heapq

heap = [5, 3, 8, 1]
heapq.heapify(heap)        # heapify(x)：原地把列表 x 建成堆；不返回新列表，时间 O(n)。
heapq.heappush(heap, 0)    # heappush(heap, item)：加入 item 并保持堆序，时间 O(log n)。
heapq.heappop(heap)        # heappop(heap)：移除并返回最小元素；堆不能为空，时间 O(log n)。
heapq.heapreplace(heap, 2) # heapreplace(heap, item)：先弹最小值再放 item，堆不能为空，O(log n)。
heapq.heappushpop(heap, 9) # heappushpop(heap, item)：先放 item 再弹最小值，时间 O(log n)。
heapq.nlargest(3, heap)    # nlargest(n, iterable, key=None)：返回最大的 n 项；约 O(N log n)。
heapq.nsmallest(3, heap)   # nsmallest(n, iterable, key=None)：返回最小的 n 项；约 O(N log n)。
heapq.merge([1, 4], [2, 3])  # merge(*iterables, key=None, reverse=False)：合并有序输入，惰性输出，每项约 O(log K)。

三个必须内化的点：

1. Python 没有”最大堆”，用取负造一个：push(-x)、取回时 -heappop()。
2. 堆里放元组时，元组会按第一个元素、再第二个元素依次比较。当第一个元素相等时，Python 会去比较第二个 元素；如果第二个元素是链表节点这类不可比较对象，就会抛 TypeError——解决方法是塞一个递增计数器占位。
3. heapq 只能高效删除堆顶。要”删掉堆里任意元素”，用惰性删除：把删除标记记在 set/dict 里， 弹出时发现已删除就继续弹。

例题 12：LeetCode 215 数组中的第 K 个最大元素（中等）

题目：给定整数数组 nums 和整数 k，返回数组中第 k 大的元素（按降序排序后的第 k 个）。 例如 nums = [3,2,1,5,6,4]、k = 2，答案为 5。

一行库调用，nlargest 内部就是堆：

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]

复杂度：时间 O(n log k)（nlargest 内部维护大小为 k 的堆）；空间 O(k)（堆 + 结果）。

手写等价版（维护一个大小为 k 的最小堆，堆顶就是第 k 大）：

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    heap = nums[:k]
    heapq.heapify(heap)
    for x in nums[k:]:
        if x > heap[0]:                 # 只保留最大的 k 个
            heapq.heapreplace(heap, x)
    return heap[0]

复杂度：时间 O(n log k)（建堆 O(k)，对剩余 n-k 个元素各做一次 O(log k) 的替换）；空间 O(k)。

例题 13：LeetCode 347 前 K 个高频元素（中等）

题目：给定整数数组 nums 和整数 k，返回出现频率最高的 k 个元素，顺序不限。 例如 nums = [1,1,1,2,2,3]、k = 2，答案可以是 [1, 2]。

Counter 计数 + most_common(k)（内部就是 nlargest）：

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    return [x for x, _ in Counter(nums).most_common(k)]  # most_common(n)：返回频次最高的 n 项；约 O(N log n)。

复杂度：时间 O(n log k)（计数 O(n)，most_common(k) 内部为 O(n log k) 的堆操作）；空间 O(n) （计数器 + 结果）。

例题 14：LeetCode 1046 最后一块石头的重量（简单）

题目：有一堆石头，每块重量为正整数。每次选出最重的两块 x 和 y（x <= y）碰撞：若 x == y 两块 都消失，否则剩下重量为 y - x 的石头继续参与。返回最终剩下的石头重量；若没有石头剩下则返回 0。 例如 [2,7,4,1,8,1]，答案是 1。

最大堆 = 最小堆取负：

import heapq

def last_stone_weight(stones: list[int]) -> int:
    heap = [-x for x in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = -heapq.heappop(heap)
        b = -heapq.heappop(heap)
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

复杂度：时间 O(n log n)（最多 n 次碰撞，每次两次 pop 一次 push，均 O(log n)）；空间 O(n)。

例题 15：LeetCode 23 合并 K 个升序链表（困难，进阶延伸）

题目：给定 k 个升序链表，把它们合并为一个升序链表并返回。例如输入 [[1,4,5],[1,3,4],[2,6]]， 输出 [1,1,2,3,4,4,5,6]。

思路：把所有链表的”当前头节点”放进堆，每次弹出最小的，再把它所在链表的下一个节点补进堆。 因为堆里要放链表节点，必须用计数器避免比较不可比较的节点对象：

import heapq
from itertools import count

def merge_k_lists(lists):
    heap = []
    counter = count()                       # count(start=0, step=1)：生成无限等差整数迭代器，next(counter) 均摊 O(1)。
    for head in lists:
        if head:
            heapq.heappush(heap, (head.val, next(counter), head))
    dummy = ListNode()
    cur = dummy
    while heap:
        val, _, node = heapq.heappop(heap)
        cur.next = ListNode(val)
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, next(counter), node.next))
    return dummy.next

复杂度：时间 O(N log K)（N 为总节点数，每个节点进出堆一次，堆大小为 K）；空间 O(K)（堆） 外加输出链表 O(N)。

第六章 排序：官方排序 + 必须手撕的两套

6.1 先学会用官方排序

• sorted(iterable, key=..., reverse=...) 返回新列表；
• list.sort(...) 原地排序，返回 None；
• 两者都是稳定排序（Timsort，平均 O(n log n)，几乎有序时接近 O(n)）。

多关键字排序用元组做 key：sorted(people, key=lambda p: (-p[0], p[1])) 表示”先按第一维降序，再按第二维升序”。

nums = [3, 1, 2]
nums.sort()                              # list.sort(key=None, reverse=False)：原地排序，返回 None，平均 O(n log n)。
sorted(nums, reverse=True)               # sorted(iterable, key=None, reverse=False)：返回新列表，reverse=True 降序。
words = ['banana', 'apple', 'pear']
sorted(words, key=len)                   # key=len：按元素长度排序；返回新列表，时间 O(n log n)。
pairs = [(1, 2), (2, 1), (1, 1)]
sorted(pairs, key=lambda p: (-p[0], p[1]))   # key 返回排序元组：第一维降序、第二维升序，稳定排序。

例题 16：LeetCode 56 合并区间（中等）

题目：以数组 intervals 表示若干个闭区间，合并所有重叠的区间并返回互不重叠的区间数组。 例如 [[1,3],[2,6],[8,10],[15,18]]，合并后为 [[1,6],[8,10],[15,18]]。

排序 + 贪心：按起点排序后，能合并就合并，不能合并就开新区间。

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    res = []
    for s, e in intervals:
        if not res or s > res[-1][1]:
            res.append([s, e])
        else:
            res[-1][1] = max(res[-1][1], e)
    return res

复杂度：时间 O(n log n)（排序主导，合并阶段 O(n)）；空间 O(n)（结果数组；不计结果时为 O(log n) 排序栈）。

例题 17：LeetCode 169 多数元素（简单）

题目：给定大小为 n 的数组 nums，返回其中出现次数大于 ⌊n/2⌋ 的元素（题目保证存在）。 例如 [2,2,1,1,1,2,2] 返回 2。

排序后取中位数即可（多数元素必然落在正中间）：

def majority_element(nums: list[int]) -> int:
    nums.sort()
    return nums[len(nums) // 2]

复杂度：时间 O(n log n)（排序主导）；空间 O(n)（Timsort 最坏需要的辅助空间；若只统计比较次数则为 O(1) 原地交换）。也可用 Counter（O(n)/O(n)）或摩尔投票（O(n)/O(1)）做到线性时间。

6.2 手撕快速排序（必须）

为什么 sorted 这么好还要手撕快排？因为 partition（分区）思想是快选、荷兰国旗、按奇偶分组等一堆题的基础。 给你两种写法，先背简洁版理解思想，再练原地版应对”额外空间受限”的要求。

简洁版（读起来最直观，空间 O(n)）：

def quick_sort(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

复杂度：时间平均 O(n log n)、最坏 O(n²)（pivot 总选到极值时）；空间 O(n)（每层分区列表 + 递归栈）。

原地版（双指针分区，额外空间 O(log n) 栈深）：

def quick_sort_inplace(arr: list, lo: int, hi: int) -> None:
    if lo >= hi:
        return
    pivot = arr[(lo + hi) // 2]
    i, j = lo, hi
    while i <= j:
        while arr[i] < pivot:
            i += 1
        while arr[j] > pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    quick_sort_inplace(arr, lo, j)      # 左半
    quick_sort_inplace(arr, i, hi)      # 右半

复杂度：时间平均 O(n log n)、最坏 O(n²)；空间 O(log n)（递归栈，原地交换无额外数组）。

复杂度与局限：平均 O(n log n)，最坏 O(n²)（pivot 总选到极值）。这正是”为什么我们日常用 sorted“的最好答案： Timsort 通过自适应与归并保证最坏也是 O(n log n)。

6.3 手撕归并排序（必须）

归并排序 = 分治 + 合并。它是最能体现”递归”价值的排序：先拆到只剩一个，再两两有序合并。

def merge_sort(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    i = j = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

复杂度：时间 O(n log n)（每层 O(n)，共 log n 层，且任何输入都是这个界）；空间 O(n)（合并数组）。

归并排序是稳定排序，O(n log n)，空间 O(n)。它最大的算法价值是：合并过程可以顺带统计信息。

进阶必练：逆序对（剑指 Offer 51 / LeetCode 493）。在合并时，若右半元素先被取走，说明它比左半剩下的 所有元素都小，这些就是逆序对：

def count_inversions(nums: list) -> int:
    def merge_and_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, a = merge_and_count(arr[:mid])
        right, b = merge_and_count(arr[mid:])
        i = j = inv = 0
        merged = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                inv += len(left) - i      # 右半当前元素比左半剩下全部都小
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, a + b + inv
    return merge_and_count(nums)[1]

复杂度：时间 O(n log n)；空间 O(n)（合并过程与归并排序一致）。

另一个”为什么必须会归并”的答案：LeetCode 148 排序链表（中等）要求 O(n log n) 对链表排序，快排对链表 不友好，归并却非常自然——先找中点拆两半，再原地合并。

第七章 二分搜索：bisect 与必须会的手撕模板

7.1 bisect：官方二分定位

bisect 只做一件事：在有序列表里找插入位置。两个函数必须记牢区别：

• bisect_left(a, x)：第一个 >= x 的位置（等于 x 时插左边）；
• bisect_right(a, x)：第一个 > x 的位置（等于 x 时插右边）；
• bisect.insort(a, x)：插入并保持有序（O(n)，因为 list 插入要挪元素）。

from bisect import bisect_left, bisect_right, insort

a = [1, 3, 5, 5, 7, 9]
bisect_left(a, 5)      # bisect_left(a, x, lo=0, hi=len(a), key=None)：找第一个 >= x 的位置，O(log n)。
bisect_right(a, 5)     # bisect_right(a, x, lo=0, hi=len(a), key=None)：找第一个 > x 的位置，O(log n)。
bisect_left(a, 6)      # x=6 的插入位置为 4；lo/hi 默认覆盖整个列表，O(log n)。
bisect_right(a, 6)     # x=6 的右侧插入位置也是 4，时间 O(log n)。
insort(a, 6)            # insort(a, x, lo=0, hi=len(a), key=None)：插入并保持有序；列表移动使总时间 O(n)。

找第一个 >= x / 第一个 > x / 某个值出现次数是二分最常考的形态，bisect 一行搞定：

from bisect import bisect_left, bisect_right

# 某个值在有序数组中的出现次数
def count_occurrences(a, x):
    return bisect_right(a, x) - bisect_left(a, x)

复杂度：bisect_left/bisect_right 时间 O(log n)（比较次数）、空间 O(1)；insort 额外 O(n) （列表移动）。count_occurrences 为 O(log n)。

例题 18：LeetCode 35 搜索插入位置（简单）

题目：给定升序数组 nums 和目标值 target，返回 target 应被插入的位置下标，使得数组仍然有序 （若 target 已存在则返回其下标）。例如 nums = [1,3,5,6]、target = 5，返回 2。

bisect_left 直接就是答案：

from bisect import bisect_left

def search_insert(nums: list[int], target: int) -> int:
    return bisect_left(nums, target)

复杂度：时间 O(log n)；空间 O(1)。

7.2 手撕二分模板（必须）

bisect 帮不了你的场景：判定条件不是”数组值本身”而是某个单调性质。比如”第一个坏的版本”、 “满足条件的最大/最小答案”。这类题必须手撕，模板如下：

def lower_bound(arr, target):
    lo, hi = 0, len(arr)          # [lo, hi) 左闭右开
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:     # 条件不满足：往右
            lo = mid + 1
        else:                     # 条件满足：保留 mid
            hi = mid
    return lo

这个模板的奥义是：hi = mid 而不是 hi = mid - 1——当 mid 已经是”第一个满足条件”的候选时， 不能把它排除掉。这是二分最容易写错的地方。

复杂度：时间 O(log n)（每轮区间减半）；空间 O(1)（迭代，无递归栈）。

例题 19：LeetCode 704 二分查找（简单）

题目：给定升序整数数组 nums 和目标值 target，返回 target 的下标；不存在则返回 -1。 例如 nums = [-1,0,3,5,9,12]、target = 9，返回 4。

经典闭区间写法，找到返回下标，否则 -1：

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

复杂度：时间 O(log n)；空间 O(1)。

例题 20：LeetCode 278 第一个错误的版本（简单）

题目：有 n 个版本 1..n，接口 isBadVersion(version) 判断版本是否出错。已知从某个版本开始后续 全部出错（性质单调），找出第一个出错的版本。例如 n = 5 且坏版本从 4 开始，返回 4。

isBadVersion(mid) 是一个单调性质：一旦坏，后面全坏。套”左闭右开模板”：

def first_bad_version(n: int) -> int:
    lo, hi = 1, n + 1               # [1, n+1)
    while lo < hi:
        mid = (lo + hi) // 2
        if isBadVersion(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

复杂度：时间 O(log n)（调用 isBadVersion 的次数）；空间 O(1)。

例题 21：LeetCode 33 搜索旋转排序数组（中等，进阶）

题目：升序数组在某个未知点旋转（如 [4,5,6,7,0,1,2]），数组元素互不相同。给定目标值 target， 返回其下标，不存在返回 -1。例如 target = 0 返回 4，target = 3 返回 -1。

有序数组旋转后，任意 mid 都会把数组切成”一半有序、一半无序”。利用有序那半边决定往哪走：

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:               # 左半有序
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                   # 右半有序
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

复杂度：时间 O(log n)；空间 O(1)。

判断”什么时候必须手撕二分”：当 bisect 的”值比较”不适用于你的判定条件时（如找峰值 LeetCode 162， 条件是与邻居的大小关系），就回到手撕模板。

第八章 双指针：把 O(n²) 降成 O(n) 的三个姿势

双指针不是标准库功能，但它与”排序 + 索引”天生一对，而且代码极短。三种姿势：

1. 相向双指针：一个在左、一个在右，往中间收（有序数组、缩减搜索空间）；
2. 同向双指针（快慢）：一个快、一个慢，慢的负责”写”，快的负责”扫”（原地删除、移动零）；
3. 快慢指针判环：快指针每次两步、慢指针一步（链表环、找中间节点）。

例题 22：LeetCode 167 两数之和 II（中等，相向）

题目：给定已按升序排列的整数数组 numbers 和目标值 target，找出和为 target 的两个数，返回它们的 下标（从 1 开始计数），恰好存在一个解。例如 numbers = [2,7,11,15]、target = 9，返回 [1, 2]。

数组已有序，left + right 太大就右指针左移，太小就左指针右移：

def two_sum(numbers: list[int], target: int) -> list[int]:
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

复杂度：时间 O(n)（指针最多各移动 n 次）；空间 O(1)。

例题 23：LeetCode 11 盛最多水的容器（中等，相向）

题目：给定长度为 n 的整数数组 height，其中 height[i] 表示第 i 条垂直线的高度。任选两条线与 x 轴构成容器，求容器能盛水的最大面积（两条线距离 × 较矮线高度）。例如 [1,8,6,2,5,4,8,3,7] 答案为 49。

面积 = 底 × 短板。移动长板面积只减不增，所以每次移动较矮的那一端：

def max_area(height: list[int]) -> int:
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(height[lo], height[hi]))
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    return best

复杂度：时间 O(n)（指针各移动至多 n 次）；空间 O(1)。

例题 24：LeetCode 15 三数之和（中等，排序 + 相向）

题目：给定整数数组 nums，找出所有和为 0 且不重复的三元组 [nums[i], nums[j], nums[k]] （i < j < k），答案中不能包含重复三元组。例如 [-1,0,1,2,-1,-4] 返回 [[-1,-1,2],[-1,0,1]]。

固定一个数，剩下两个用双指针。注意跳过重复值：

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s == 0:
                res.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1
                lo += 1
                hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return res

复杂度：时间 O(n²)（排序 O(n log n)，双指针部分 O(n²)）；空间 O(1)（不计排序栈与结果数组）。

例题 25：LeetCode 283 移动零（简单，同向快慢）

题目：给定数组 nums，原地把所有 0 移动到末尾，同时保持非零元素的相对顺序。例如 [0,1,0,3,12] 变为 [1,3,12,0,0]。

慢指针指向”下一个非零元素该放的位置”，快指针扫描：

def move_zeroes(nums: list[int]) -> None:
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

复杂度：时间 O(n)（单次遍历）；空间 O(1)（原地交换）。

例题 26：LeetCode 141 环形链表（简单，快慢判环）

题目：给定链表头节点 head，判断链表中是否存在环（某个节点的 next 指向链表更早的节点）。 例如 head = [3,2,0,-4]，环从下标 1 开始，返回 true。

def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

复杂度：时间 O(n)（快慢指针相遇前走的步数与 n 同阶）；空间 O(1)（只用了两个指针）。

第九章 哈希表与集合：空间换时间的地基

哈希是”回忆”能力：把访问过的信息存进 dict/set，让查找从 O(n) 变 O(1)。前面两数之和已演示过 dict， 这里再补三个高频场景。

例题 27：LeetCode 217 存在重复元素（简单）

题目：给定整数数组 nums，若存在元素出现至少两次返回 true，否则返回 false。 例如 [1,2,3,1] 返回 true。

一行去重比较：

def contains_duplicate(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))

复杂度：时间 O(n)（建集合）；空间 O(n)（集合）。

例题 28：LeetCode 49 字母异位词分组（中等）

题目：给定字符串数组 strs，把互为字母异位词的字符串分到同一组（任意顺序）。例如 ["eat","tea","tan","ate","nat","bat"] 分组为 [["eat","tea","ate"],["tan","nat"],["bat"]]。

defaultdict(list) + “排序后的字符串”作为分组键：

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)  # defaultdict(default_factory)：缺失键自动调用 default_factory；list 表示新建空列表。
    for s in strs:
        groups[''.join(sorted(s))].append(s)  # sorted(s) 返回排序后的新列表，按字符数 O(K log K)。
    return list(groups.values())

defaultdict 的威力：访问不存在的键时自动创建默认值，省掉”if key not in d: d[key] = []”三行样板。

复杂度：时间 O(N × K log K)（N 为字符串个数，K 为最长字符串长度，每组排序 O(K log K)）； 空间 O(N × K)（分组结果 + 键）。

例题 29：LeetCode 128 最长连续序列（中等）

题目：给定未排序的整数数组 nums，找出数字连续的最长序列的长度，要求算法时间复杂度为 O(n)。 例如 [100,4,200,1,3,2]，最长连续序列为 [1,2,3,4]，答案是 4。

把数组放进 set，只从”连续段的起点”（x - 1 不在集合里）开始往后数：

def longest_consecutive(nums: list[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:          # 只从起点开始
            cur = x
            length = 1
            while cur + 1 in s:
                cur += 1
                length += 1
            best = max(best, length)
    return best

整体 O(n)：每个元素最多被”起点判断 + 向后延伸”访问常数次。

复杂度：时间 O(n)（每个元素至多被访问常数次）；空间 O(n)（集合）。

第十章 递归：必须手撕的调用栈

递归是所有树/图/回溯/DP 的地基。三要素缺一不可：

1. 终止条件：什么时候直接返回；
2. 递推关系：把问题拆成更小的同类问题；
3. 返回值设计：递归函数向上层”报告”什么。

例题 30：LeetCode 104 二叉树的最大深度（简单）

题目：给定二叉树根节点 root，返回其最大深度（根节点到最远叶子节点的路径上节点数）。 例如 root = [3,9,20,null,null,15,7]，深度为 3。

最干净的递归示范：

def max_depth(root) -> int:
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

复杂度：时间 O(n)（每个节点访问一次）；空间 O(h)（递归栈，h 为树高，最坏为链式树时 O(n)）。

例题 31：LeetCode 206 反转链表（简单，递归 + 迭代）

题目：给定单链表头节点 head，反转链表并返回新的头节点。例如 1 -> 2 -> 3 变为 3 -> 2 -> 1。

递归版（先把后面的都反转好，再回头处理当前节点）：

def reverse_list_rec(head) -> ListNode:
    if not head or not head.next:
        return head
    new_head = reverse_list_rec(head.next)
    head.next.next = head       # 让下一个节点指向自己
    head.next = None            # 断开旧指针
    return new_head

复杂度：时间 O(n)；空间 O(n)（递归栈深度 n）。

迭代版（三个指针滚动，面试更常要求）：

def reverse_list(head) -> ListNode:
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

复杂度：时间 O(n)；空间 O(1)（只用了三个指针）。

递归的两个”去向”

递归写多了会发现两条固定的升级路径：

• 重复子问题太多 → 记忆化（变 DP）：见第十四章 lru_cache；
• 怕爆栈 → 转迭代（显式栈）：把系统调用栈换成自己维护的 list 栈，见第十二章迭代版 DFS。

Python 默认递归深度上限约 1000，深递归题要显式放宽：

import sys
sys.setrecursionlimit(10000)  # setrecursionlimit(limit)：把进程递归上限设为 limit；修改全局设置，时间 O(1)。

第十一章 回溯法：树搜索暴力通解（必须手撕）

回溯是”带撤销的 DFS”，是排列、组合、子集、棋盘、数独等一切”枚举所有方案”问题的最基础通解。 它的地位怎么强调都不过分：当你想不出更优解时，回溯是保底方案；当你想出更优解时，回溯是你验证正确性的基准。

回溯四步模板

def backtrack(路径, 选择列表):
    if 满足终止条件:
        记录结果
        return
    for 选择 in 选择列表:
        做选择                       # 加入路径
        backtrack(新路径, 新选择列表)
        撤销选择                     # 从路径移除，回到上一步

四个关键点：路径（已做的选择）、选择列表（还能选什么）、终止条件（何时收工）、撤销（状态回滚）。

复杂度：时间取决于方案总数 S 与构造每个方案的开销 L，一般记为 O(S × L)（如全排列 S = n!、 每个方案拷贝 L = n）；空间 O(递归深度)，即搜索树深度。

例题 32：LeetCode 46 全排列（中等）

题目：给定不含重复数字的数组 nums，返回其所有可能的全排列（任意顺序）。例如 nums = [1,2,3]， 返回 6 个排列，如 [1,2,3]、[1,3,2] 等。

用 used 数组标记哪些元素已选：

def permute(nums: list[int]) -> list[list[int]]:
    res = []

    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path[:])          # 拷贝！不能直接 append(path)
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            backtrack(path, used)
            path.pop()                   # 撤销选择
            used[i] = False

    backtrack([], [False] * len(nums))
    return res

复杂度：时间 O(n × n!)（n! 个排列，每个拷贝 O(n)）；空间 O(n)（路径与 used，不计结果数组）。

例题 33：LeetCode 78 子集（中等）

题目：给定不含重复元素的整数数组 nums，返回其所有子集（幂集），不能包含重复子集。 例如 nums = [1,2,3]，返回 8 个子集，包括空集与全集。

每个元素”选或不选”，用 start 控制不回头：

def subsets(nums: list[int]) -> list[list[int]]:
    res = []

    def backtrack(start, path):
        res.append(path[:])              # 每个中间状态都是一个合法子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return res

复杂度：时间 O(n × 2ⁿ)（2ⁿ 个子集，每个拷贝 O(n)）；空间 O(n)（递归栈，不计结果数组）。

例题 34：LeetCode 77 组合（中等）

题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合（任意顺序）。 例如 n = 4、k = 2，返回 6 个组合，如 [1,2]、[1,3] 等。

子集 + 限制长度 k：

def combine(n: int, k: int) -> list[list[int]]:
    res = []

    def backtrack(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return res

复杂度：时间 O(C(n,k) × k)（C(n,k) 个组合，每个拷贝 O(k)）；空间 O(k)（递归栈与路径）。

例题 35：LeetCode 39 组合总和（中等）

题目：给定一个不含重复元素的候选数组 candidates 和目标值 target，找出所有和为 target 的组合。 每个数字可以被无限次重复使用，组合间不能重复。例如 candidates = [2,3,6,7]、target = 7， 返回 [[2,2,3],[7]]。

允许重复选同一个数，所以递归时 start 不前进；超过目标值直接剪枝：

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
    res = []

    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remain:               # 剪枝：当前候选太大
                continue
            path.append(c)
            backtrack(i, path, remain - c)   # 注意：仍传 i，允许重复取
            path.pop()

    backtrack(0, [], target)
    return res

复杂度：时间最坏指数级 O(T)（T 与 target 和候选大小相关，剪枝后远小于上界，通常记为 O(2^T) 级别的上界）；空间 O(T)（递归深度受 target 限制）。

例题 36：LeetCode 40 组合总和 II（中等）——排序去重剪枝

题目：候选数组 candidates 中含重复数字，且每个数字在每个组合中只能用一次，找出所有和为 target 且不重复的组合。例如 candidates = [10,1,2,7,6,1,5]、target = 8，返回 [[1,1,6],[1,2,5],[1,7],[2,6]]。

候选有重复，先排序，同一层跳过相同值，避免重复组合：

def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    res = []

    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue                # 同一层去重
            c = candidates[i]
            if c > remain:
                break                   # 已排序，后续更大，直接停
            path.append(c)
            backtrack(i + 1, path, remain - c)
            path.pop()

    backtrack(0, [], target)
    return res

复杂度：时间最坏 O(2ⁿ)（n 为候选个数，剪枝后通常远小）；空间 O(n)（递归栈 + 路径）。

什么时候可以用 itertools 替代回溯？

如果题目只要求输出方案、不要求剪枝、数据量小，itertools.permutations / combinations 可以直接用 （见第十五章）。但需要去重、需要”重复选取”、需要提前剪枝时，必须回到回溯。先会手撕回溯， 再用 itertools 偷懒，顺序不能反。

第十二章 树：DFS 与 BFS 全家桶

LeetCode 的树都是 TreeNode：

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

12.1 DFS：递归三序 + 迭代前序

def inorder(root, res):
    if not root:
        return
    inorder(root.left, res)     # 左
    res.append(root.val)        # 中（换位置就是前序/后序）
    inorder(root.right, res)    # 右

复杂度：时间 O(n)（每个节点访问一次）；空间 O(h)（递归栈，h 为树高）。

前序迭代版（显式栈）——把系统调用栈换成自己的栈：

def preorder_iter(root):
    if not root:
        return []
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.right:          # 先压右，后弹右 -> 左先被访问
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

复杂度：时间 O(n)；空间 O(h)（显式栈，最坏 O(n)）。

例题 37：LeetCode 226 翻转二叉树（简单）

题目：给定二叉树根节点 root，翻转这棵二叉树（左右子树全部互换），返回新的根节点。 例如 [4,2,7,1,3,6,9] 翻转为 [4,7,2,9,6,3,1]。

递归翻转左右子树：

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

复杂度：时间 O(n)；空间 O(h)（递归栈）。

例题 38：LeetCode 98 验证二叉搜索树（中等）

题目：给定二叉树根节点 root，判断其是否为一棵有效的二叉搜索树：左子树所有节点值 < 根 < 右子树所有 节点值，且左右子树自身也满足（整棵树满足”中序遍历严格递增”）。例如 [2,1,3] 返回 true， [5,1,4,null,null,3,6] 返回 false。

BST 的中序遍历严格递增。用”前一个值”做校验：

def is_valid_bst(root) -> bool:
    prev = [float('-inf')]

    def dfs(node):
        if not node:
            return True
        if not dfs(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return dfs(node.right)

    return dfs(root)

复杂度：时间 O(n)（中序遍历一遍）；空间 O(h)（递归栈）。

例题 39：LeetCode 102 二叉树的层序遍历（中等）

题目：给定二叉树根节点 root，返回其节点值的层序遍历结果（逐层从左到右）。 例如 root = [3,9,20,null,null,15,7]，返回 [[3],[9,20],[15,7]]。

BFS + 分层，deque 是标配：

from collections import deque

def level_order(root):
    if not root:
        return []
    res = []
    dq = deque([root])
    while dq:
        level = []
        for _ in range(len(dq)):        # 只处理当前层
            node = dq.popleft()
            level.append(node.val)
            if node.left:
                dq.append(node.left)
            if node.right:
                dq.append(node.right)
        res.append(level)
    return res

复杂度：时间 O(n)；空间 O(n)（队列最多容纳一层节点，最坏接近 n）。

例题 40：LeetCode 199 二叉树的右视图（中等）

题目：给定二叉树根节点 root，想象自己站在树右侧，返回从右往左看能看到的节点值（每层最右边那个）。 例如 root = [1,2,3,null,5,null,4]，返回 [1,3,4]。

BFS 每层最后一个节点：

from collections import deque

def right_side_view(root):
    if not root:
        return []
    res = []
    dq = deque([root])
    while dq:
        res.append(dq[-1].val)          # 当前层最右
        for _ in range(len(dq)):
            node = dq.popleft()
            if node.left:
                dq.append(node.left)
            if node.right:
                dq.append(node.right)
    return res

复杂度：时间 O(n)；空间 O(n)（队列最坏容纳一层节点）。

第十三章 图：邻接表、BFS、DFS 与拓扑排序

13.1 图的表示：邻接表

算法题 90% 的图用邻接表存：defaultdict(list)，键是节点，值是邻居列表。构建邻接表的时间为 O(E) （E 为边数），空间为 O(V + E)：

from collections import defaultdict, deque

edges = [(0, 1), (1, 2), (2, 0)]   # 示例边：构成环 0 -> 1 -> 2 -> 0
graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)      # 有向边 a -> b

“网格”本身就是隐式图：每个格子的上下左右就是邻居，不需要显式建边。

例题 41：LeetCode 200 岛屿数量（中等，网格 DFS）

题目：给定 m × n 的二维网格 grid，'1' 表示陆地、'0' 表示水。陆地按上下左右四个方向连通成 “岛屿”，返回岛屿数量。例如示例网格中 1 被分成 3 个连通块，答案为 3。

遇到 '1' 就计数并把整座岛”淹没”（改成 '0'），DFS 四个方向：

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])

    def dfs(i, j):
        if not (0 <= i < m and 0 <= j < n) or grid[i][j] != '1':
            return
        grid[i][j] = '0'            # 标记访问，防止重复
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            dfs(i + di, j + dj)

    cnt = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                cnt += 1
                dfs(i, j)
    return cnt

复杂度：时间 O(m × n)（每个格子至多访问一次）；空间 O(m × n) 最坏（递归栈在全是陆地时可达 m × n）。

例题 42：LeetCode 994 腐烂的橘子（中等，多源 BFS）

题目：给定 m × n 网格，2 表示腐烂的橘子、1 表示新鲜橘子、0 表示空格。每分钟腐烂橘子会感染 上下左右相邻的新鲜橘子。返回让所有新鲜橘子腐烂所需的最少分钟数；若不可能全部腐烂返回 -1。 示例网格答案为 4。

“多源 BFS”：把所有烂橘子同时作为起点，BFS 的步数就是分钟数。

from collections import deque

def oranges_rotting(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dq = deque()
    fresh = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                dq.append((i, j, 0))
            elif grid[i][j] == 1:
                fresh += 1
    minutes = 0
    while dq:
        i, j, t = dq.popleft()
        minutes = max(minutes, t)
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                grid[ni][nj] = 2
                fresh -= 1
                dq.append((ni, nj, t + 1))
    return -1 if fresh else minutes

复杂度：时间 O(m × n)；空间 O(m × n)（队列最多容纳所有橘子）。

例题 43：LeetCode 207 课程表（中等，拓扑排序）

题目：给定课程数 numCourses（编号 0..numCourses-1）和先修关系 prerequisites（[a, b] 表示 修 a 之前必须先修 b），判断能否完成所有课程（即先修关系构成的有向图是否无环）。 例如 numCourses = 2、prerequisites = [[1,0]] 返回 true；[[1,0],[0,1]] 返回 false。

有向图判环 = Kahn 拓扑排序：入度为 0 的节点先入队，逐个”删点”，最后看有没有节点没被删。

from collections import defaultdict, deque

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    indegree = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1
    dq = deque([i for i in range(num_courses) if indegree[i] == 0])
    count = 0
    while dq:
        cur = dq.popleft()
        count += 1
        for nxt in graph[cur]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                dq.append(nxt)
    return count == num_courses

复杂度：时间 O(V + E)（V 为课程数、E 为先修边数，每个节点与每条边各处理一次）；空间 O(V + E) （邻接表 + 入度表 + 队列）。

例题 44：LeetCode 785 判断二分图（中等，BFS 染色）

题目：给定无向图（用邻接表 graph 表示，graph[i] 是与节点 i 相连的节点列表），判断是否能将节点 分成两个集合，使每条边的两个端点分属不同集合（即用两种颜色染色且相邻节点不同色）。 示例 1 返回 true，示例 2 返回 false。

两种颜色交替染色，邻居撞色就不是二分图：

from collections import deque

def is_bipartite(graph: list[list[int]]) -> bool:
    n = len(graph)
    color = [-1] * n
    for start in range(n):              # 图可能不连通，逐个分量染色
        if color[start] != -1:
            continue
        color[start] = 0
        dq = deque([start])
        while dq:
            u = dq.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    dq.append(v)
                elif color[v] == color[u]:
                    return False
    return True

复杂度：时间 O(V + E)；空间 O(V)（颜色数组 + 队列）。

第十四章 动态规划：一维、二维与 lru_cache

DP 的标准五步：

1. 定义状态：dp[i] 代表什么；
2. 写转移方程：dp[i] 怎么由前面的状态推出；
3. 初始化：边界值；
4. 确定遍历顺序；
5. 定位答案。

两条路线二选一：

• 自顶向下（记忆化递归）：先写朴素递归，再用 @lru_cache 缓存，几乎零成本拿到指数→多项式；
• 自底向上（表格法）：直接开数组迭代，空间可控、无递归栈风险。

例题 45：LeetCode 70 爬楼梯（简单，一维）

题目：假设你正在爬楼梯，需要 n 阶才能到顶。每次可以爬 1 或 2 个台阶，问有多少种不同的方法爬到顶。 例如 n = 3，有 3 种方法（1+1+1、1+2、2+1）。

斐波那契的翻版。记忆化递归：

from functools import lru_cache

@lru_cache(None)  # lru_cache(maxsize=None, typed=False)：按参数缓存结果；typed=True 时区分参数类型。
def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)

复杂度：时间 O(n)（每个 n 只算一次，其余直接查缓存）；空间 O(n)（缓存 + 递归栈）。

自底向上 + 滚动数组（空间 O(1)）：

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

复杂度：时间 O(n)；空间 O(1)（只保留两个变量）。

例题 46：LeetCode 198 打家劫舍（中等，一维）

题目：沿街房屋的金额存在数组 nums 中，不能偷相邻两家的房子，求今晚能偷到的最大金额。 例如 nums = [2,7,9,3,1]，最优为偷 2 + 9 + 1 = 12。

dp[i] = max(不偷这家, 偷这家)：

def rob(nums: list[int]) -> int:
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

复杂度：时间 O(n)（单次遍历）；空间 O(1)（滚动两个变量）。

例题 47：LeetCode 62 不同路径（中等，二维）

题目：一个 m × n 的网格，机器人从左上角出发，每次只能向下或向右移动一步，到达右下角共有多少条 不同路径？例如 m = 3、n = 7，答案是 28。

dp[i][j] = dp[i-1][j] + dp[i][j-1]。记忆化递归版：

from functools import lru_cache

@lru_cache(None)  # lru_cache(maxsize=None, typed=False)：按参数缓存结果；typed=True 时区分参数类型。
def unique_paths(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1
    return unique_paths(m - 1, n) + unique_paths(m, n - 1)

复杂度：时间 O(m × n)（每个状态只计算一次）；空间 O(m × n)（缓存）。

表格版：

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

复杂度：时间 O(m × n)；空间 O(m × n)（可优化为两行滚动，O(n)）。

例题 48：LeetCode 1143 最长公共子序列（中等，二维）

题目：给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度（子序列不要求连续，但要保持 相对顺序）；不存在则为 0。例如 text1 = "abcde"、text2 = "ace"，答案是 3。

状态：lcs(i, j) = text1[i:] 与 text2[j:] 的最长公共子序列长度：

from functools import lru_cache

def longest_common_subsequence(text1: str, text2: str) -> int:
    @lru_cache(None)  # lru_cache(maxsize=None, typed=False)：按参数缓存结果；typed=True 时区分参数类型。
    def lcs(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

复杂度：时间 O(m × n)（m、n 为两字符串长度，状态数 (m+1)(n+1)）；空间 O(m × n)（缓存）。

lru_cache 的三个使用铁律

1. 多测试用例时记得 cache_clear()：不同用例状态不同，缓存会”串味”。

from functools import lru_cache

@lru_cache(None)  # lru_cache(maxsize=None, typed=False)：按参数缓存结果；typed=True 时区分参数类型。
def solve(n):
    return n * n

solve(10)                  # 第一次调用，真实计算并缓存
solve.cache_clear()        # 无参数清空缓存；时间约 O(缓存状态数)，避免不同用例互相污染。

1. 参数必须可哈希：不能把 list 直接传进被缓存的函数，要传 tuple。
2. 缓存的本质是”状态 → 结果”映射：状态越少、缓存命中越高。二维 DP 里把两个下标作为参数是标准做法。

反直觉但重要：@lru_cache 解决的”重复子问题”，恰恰暴露了朴素递归为什么慢——没有缓存时，爬楼梯递归是 指数级。这也是”先理解递归，再用库优化”的活教材。

第十五章 itertools：组合爆炸问题的官方弹药库

itertools 是”生成各种序列”的官方库；这些函数默认返回惰性迭代器，只有 list(...) 才会一次性物化结果：

from itertools import (product, permutations, combinations, combinations_with_replacement,
                       chain, accumulate, groupby, islice)

list(product([0, 1], repeat=2))              # product(*iterables, repeat=1)：笛卡尔积；repeat 为重复次数，结果量决定复杂度。
list(permutations([1, 2, 3], 2))             # permutations(iterable, r=None)：有序排列；r 为每组长度，结果数 P(n,r)。
list(combinations([1, 2, 3], 2))             # combinations(iterable, r)：无序且不重复组合；r 为每组长度，结果数 C(n,r)。
list(combinations_with_replacement([1, 2], 2))  # 允许重复选择的无序组合；r 为每组长度，结果数 C(n+r-1,r)。
list(chain([1, 2], [3]))                     # chain(*iterables)：依次展平多个可迭代对象，总元素数为 N 时遍历 O(N)。
list(accumulate([1, 2, 3, 4]))               # accumulate(iterable, func=add, initial=None)：生成前缀累计值，遍历 O(n)。
[(k, list(g)) for k, g in groupby('AABBB')]  # groupby(iterable, key=None)：按 key 连续分组，遍历 O(n)，不会跨段合并。
list(islice(range(10), 2, 8, 2))             # islice(iterable, start, stop, step)：惰性切片，示例扫描至 stop 约 O(stop)。

例题 49：LeetCode 78 子集（用库版）

题目：同例题 33（返回数组 nums 的所有子集）。

from itertools import combinations

def subsets(nums: list[int]) -> list[list[int]]:
    return [list(c) for r in range(len(nums) + 1) for c in combinations(nums, r)]

复杂度：时间 O(n × 2ⁿ)（枚举并拷贝全部子集）；空间 O(n × 2ⁿ)（结果数组）。

例题 50：LeetCode 46 全排列（用库版）

题目：同例题 32（返回数组 nums 的所有全排列）。

from itertools import permutations

def permute(nums: list[int]) -> list[list[int]]:
    return [list(p) for p in permutations(nums)]

复杂度：时间 O(n × n!)；空间 O(n × n!)（结果数组）。

例题 51：LeetCode 17 电话号码的字母组合（中等，product）

题目：给定一个仅包含数字 2-9 的字符串 digits，返回它能表示的所有字母组合。每个数字映射一组字母 （如 2 -> abc、3 -> def）。例如 digits = "23"，返回 ["ad","ae","af","bd","be","bf","cd","ce","cf"] 共 9 个组合。

from itertools import product

def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []
    mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
               '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    return [''.join(p) for p in product(*(mapping[d] for d in digits))]

复杂度：时间 O(4ⁿ × n)（n 为数字个数，每位最多 4 个字母，拼接每个组合 O(n)）；空间 O(4ⁿ × n) （结果数组，不含输出时递归/迭代辅助为 O(n)）。

使用边界：groupby 只对连续相同的元素分组（'AABBA' 会分成三组而不是两组）；permutations 会把 重复元素当作不同元素。需要去重或剪枝时，别用 itertools，回到手撕回溯。

第十六章 functools：高阶函数与缓存

16.1 cmp_to_key：把”比较器”变成排序 key

当排序规则无法写成单个 key 表达式时，写比较器再转成 key。经典题：LeetCode 179 最大数（中等）。

题目：给定非负整数数组 nums，把它们拼接成一个最大的数并以字符串返回（拼接后不能有前导零，除非结果 本身就是 0）。例如 [3,30,34,5,9]，答案是 "9534330"。

from functools import cmp_to_key

def largest_number(nums: list[int]) -> str:
    strs = [str(x) for x in nums]

    def cmp(a, b):
        if a + b > b + a:       # a 应排在 b 前面
            return -1
        if a + b < b + a:
            return 1
        return 0

    strs.sort(key=cmp_to_key(cmp))  # cmp_to_key(mycmp)：把双参数比较器转成排序 key，排序仍为 O(n log n)。
    res = ''.join(strs)
    return '0' if res[0] == '0' else res

复杂度：时间 O(n log n × L)（n 为数字个数，L 为字符串平均长度，比较成本来自拼接）；空间 O(n)。

16.2 多关键字排序：LeetCode 451 根据字符出现频率排序（中等）

题目：给定字符串 s，按字符出现频率降序重新排列它（频率相同字符顺序不限）。 例如 s = "tree"，答案可以是 "eert" 或 "eetr"。

from collections import Counter

def frequency_sort(s: str) -> str:
    cnt = Counter(s)  # Counter(iterable)：统计 s 中每个字符的次数，时间 O(n)、空间 O(k)。
    return ''.join(sorted(s, key=lambda ch: (-cnt[ch], ch)))

(-cnt[ch], ch) 就是”先频率降序、再字符升序”。

复杂度：时间 O(n log n)（计数 O(n)，排序 O(n log n)）；空间 O(n)（计数器 + 结果）。

16.3 其他常用

from functools import lru_cache, reduce, partial

reduce(lambda acc, x: acc + x, [1, 2, 3], 0)   # reduce(function, iterable, initializer)：从 initializer 逐项归约，O(n)。
add_one = partial(lambda x, y: x + y, 1)       # partial(func, *args, **kwargs)：固定部分参数，创建可调用对象约 O(1)。

第十七章 综合实战：一道中档题的完整思维链

以 LeetCode 347 前 K 个高频元素（题目见例题 13）为例，展示”识别问题 → 选择工具”的完整过程。

第 1 步：暴力（先保证正确）

def top_k_frequent_brute(nums, k):
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    return sorted(freq, key=lambda x: freq[x], reverse=True)[:k]

复杂度：时间 O(n log n)（排序主导）；空间 O(n)（计数器）。

第 2 步：识别问题类型

• 需要统计频率 → 计数问题 → Counter；
• 需要”最大的 k 个” → Top-K → 堆 → heapq.nlargest 或 most_common(k)。

第 3 步：一行库调用

from collections import Counter

def top_k_frequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]

复杂度：时间 O(n log k)；空间 O(n)。

第 4 步：知道库在背后做了什么（面试追问）

most_common(k) 内部就是 heapq.nlargest(k, counter.items(), key=lambda p: p[1])。手写等价版：

import heapq
from collections import Counter

def top_k_frequent_heap(nums, k):
    cnt = Counter(nums)
    heap = [(-freq, num) for num, freq in cnt.items()]
    heapq.heapify(heap)
    return [heapq.heappop(heap)[1] for _ in range(k)]

复杂度：时间 O(n + k log n)（计数 O(n)、建堆 O(n)、弹出 k 次各 O(log n)）；空间 O(n)。

这一条思维链就是全文的缩影：暴力保底 → 识别模式 → 用库提速 → 能讲清库的原理。

附录 A：高频题 → 标准库工具速查表

LeetCode	题目	难度	核心工具	复杂度
1	两数之和	简单	dict 记忆	O(n) / O(n)
20	有效的括号	简单	list 当栈	O(n) / O(n)
35	搜索插入位置	简单	bisect_left	O(log n) / O(1)
70	爬楼梯	简单	functools.lru_cache / 滚动数组	O(n) / O(1)
104	二叉树的最大深度	简单	递归	O(n) / O(h)
141	环形链表	简单	快慢指针	O(n) / O(1)
169	多数元素	简单	sort / Counter	O(n log n) / O(n)
206	反转链表	简单	递归 / 迭代	O(n) / O(1)
217	存在重复元素	简单	set	O(n) / O(n)
226	翻转二叉树	简单	递归	O(n) / O(h)
242	有效的字母异位词	简单	Counter	O(n) / O(1)
268	缺失数字	简单	sum 数学	O(n) / O(1)
278	第一个错误的版本	简单	手撕二分	O(log n) / O(1)
283	移动零	简单	同向双指针	O(n) / O(1)
367	有效的完全平方数	简单	math.isqrt	O(1) / O(1)
643	子数组最大平均数 I	简单	定长滑动窗口	O(n) / O(1)
933	最近的请求次数	简单	deque	均摊 O(1) / O(n)
1046	最后一块石头的重量	简单	heapq（取负造最大堆）	O(n log n) / O(n)
3	无重复字符的最长子串	中等	滑动窗口 + set	O(n) / O(k)
11	盛最多水的容器	中等	相向双指针	O(n) / O(1)
15	三数之和	中等	排序 + 双指针	O(n²) / O(1)
17	电话号码的字母组合	中等	itertools.product	O(4ⁿ·n) / O(n)
33	搜索旋转排序数组	中等	手撕二分	O(log n) / O(1)
39	组合总和	中等	回溯	指数级 / O(T)
40	组合总和 II	中等	回溯 + 剪枝	O(2ⁿ) / O(n)
46	全排列	中等	回溯 / itertools.permutations	O(n·n!) / O(n)
49	字母异位词分组	中等	defaultdict + sorted	O(N·K log K) / O(N·K)
56	合并区间	中等	sort + 贪心	O(n log n) / O(n)
62	不同路径	中等	二维 DP	O(m·n) / O(m·n)
77	组合	中等	回溯 / itertools.combinations	O(C(n,k)·k) / O(k)
78	子集	中等	回溯 / itertools.combinations	O(n·2ⁿ) / O(n)
98	验证二叉搜索树	中等	中序遍历	O(n) / O(h)
102	二叉树的层序遍历	中等	deque BFS	O(n) / O(n)
128	最长连续序列	中等	set	O(n) / O(n)
167	两数之和 II	中等	相向双指针	O(n) / O(1)
179	最大数	中等	cmp_to_key	O(n log n·L) / O(n)
198	打家劫舍	中等	一维 DP	O(n) / O(1)
199	二叉树的右视图	中等	deque BFS	O(n) / O(n)
207	课程表	中等	拓扑排序（defaultdict + deque）	O(V+E) / O(V+E)
215	数组中的第 K 个最大元素	中等	heapq.nlargest	O(n log k) / O(k)
232	用栈实现队列	中等	双栈	均摊 O(1) / O(n)
347	前 K 个高频元素	中等	Counter + heapq	O(n log k) / O(n)
451	根据字符出现频率排序	中等	Counter + 多关键字 key	O(n log n) / O(n)
739	每日温度	中等	单调栈	O(n) / O(n)
785	判断二分图	中等	BFS 染色	O(V+E) / O(V)
994	腐烂的橘子	中等	多源 BFS	O(m·n) / O(m·n)
1143	最长公共子序列	中等	二维 DP	O(m·n) / O(m·n)
23	合并 K 个升序链表	困难（进阶）	heapq + 计数器占位	O(N log K) / O(K)
239	滑动窗口最大值	困难（进阶）	单调队列 / 惰性删除	O(n) / O(k)

注：表中复杂度格式为”时间 / 空间”；h 为树高，k 为字符集或窗口大小，T 与 target 相关， 详见正文各例题的完整标注。

附录 B：建议学习路线

1. 地基（第 1-3 章）：内建容器、内置函数、math、栈——把”选对容器”练成肌肉记忆，同时背下每类操作的复杂度。
2. 三板斧（第 4-7 章）：deque、heapq、排序 API、bisect——同时把快排、归并、二分手撕到闭眼能写， 并记住各自的时间/空间界。
3. 四大模板（第 8-11 章）：双指针、哈希、递归、回溯——开始接触”思想型”题，回溯务必先暴力后优化。
4. 图与 DP（第 12-14 章）：树的 DFS/BFS、图的 BFS/拓扑、一维二维 DP——用 lru_cache 降低记忆化门槛。
5. 效率工具（第 15-16 章）：itertools、functools——把”结果量小、无需剪枝”的枚举题压缩成一行。
6. 检验：按附录 A 的清单从简单刷到中等，每题先想”该手撕还是该用库”，再写代码，最后对着复杂度表自检。

参考资料

1. Python 官方文档 - 标准库参考：collections、heapq、bisect、itertools、functools 各模块页。
2. 牛客网：告别手写冗余代码！Python 算法刷题懒人神器：整理了 Counter、bisect、heapq、deque 等常用组合。
3. Python Standard Library for DSA：按问题类型映射标准库工具，含惰性删除等进阶技巧。
4. LeetCode 题库：本文所有题号、题目描述与难度标注均来自该平台，复杂度以各题官方题解为准。
5. GitHub 上的开源题解仓库（搜索 leetcode python solutions）：可用于交叉验证多种写法，例如直接暴力 vs 标准库一行。