LeetCode Algorithm Patterns：算法模式完整教程与刷题路线

39 个算法模式 · 161 道精选 LeetCode 题 · Python 3 模板 · 12 周面试准备路线

一份面向中文开发者的 LeetCode、数据结构与算法面试教程。内容覆盖数组、哈希、双指针、滑动窗口、二分查找、单调栈、堆、链表、树、图、贪心、动态规划、Trie、并查集、最短路、线段树和字符串算法。

A comprehensive Chinese guide to LeetCode algorithm patterns, data structures, Python templates, coding interview preparation, and a structured 12-week study plan.

目标：从“会做单题”升级为“看见特征就能选择模型、写出模板、证明正确性”。
语言：Python 3。题目链接均指向 LeetCode 官方题面。
参考起点：Several Coding Patterns for Solving Data Structures and Algorithms Problems during Interviews

关键词：LeetCode、算法模式、数据结构、Python、刷题路线、代码面试、动态规划、图论、二分查找、滑动窗口、Algorithm Patterns、Coding Interview、Data Structures and Algorithms。

1. 完整性评估

1.1 结论

原仓库适合作为模式学习的起点，但不足以覆盖常见 LeetCode Medium/Hard 和完整面试范围。仓库明确收录 16 个模式，且笔记主要使用 JavaScript：

Sliding Window
Two Pointers
Fast & Slow Pointers
Merge Intervals
Cyclic Sort
In-place Reversal of a Linked List
Tree BFS
Tree DFS
Two Heaps
Subsets
Modified Binary Search
Bitwise XOR
Top K Elements
K-way Merge
0/1 Knapsack
Topological Sort

这些模式覆盖了重要骨架，但缺少数组哈希、前缀和、单调结构、回溯、并查集、最短路、Trie、贪心、更多动态规划状态设计、区间查询数据结构和字符串算法。本教程保留原 16 个模式，并扩展为 39 个模式。

1.2 完整模式地图

标记：✓ 为原仓库已有；+ 为本教程补充。

组别	模式	来源	建议优先级
数组	数组与哈希	+	必学
数组	前缀和	+	必学
数组	差分数组与扫描线	+	高频
数组	滑动窗口	✓	必学
数组	双指针	✓	必学
数组	排序与自定义比较	+	必学
数组	循环排序	✓	常见
区间	合并区间	✓	必学
搜索	二分查找	✓	必学
搜索	答案二分	+	高频
线性结构	栈与表达式解析	+	必学
线性结构	单调栈	+	必学
线性结构	单调队列	+	高频
堆	Top K / 优先队列	✓	必学
堆	双堆	✓	高频
堆	K 路归并	✓	高频
链表	原地反转	✓	必学
链表	快慢指针	✓	必学
树	树 DFS	✓	必学
树	树 BFS	✓	必学
树	二叉搜索树	+	必学
树	Trie	+	高频
枚举	回溯、子集与排列	✓ 扩展	必学
图	图 DFS/BFS	+	必学
图	拓扑排序	✓	必学
图	并查集	+	高频
图	最短路	+	高频
图	最小生成树	+	进阶
策略	贪心	+	必学
位	位运算	✓ 扩展	高频
DP	DP 通用状态设计	+	必学
DP	背包 DP	✓ 扩展	高频
DP	序列与字符串 DP	+	必学
DP	网格 DP	+	高频
DP	区间、树与状态压缩 DP	+	进阶
字符串	KMP、Rolling Hash、Manacher	+	进阶
查询	Fenwick Tree / Segment Tree	+	进阶
数学	数论与组合	+	高频
设计	缓存与随机化数据结构	+	高频

2. 使用方法

不要按题号背答案。每个模式按以下闭环学习：

识别：用一句话说出题目的输入结构、目标和限制。
选择：说明为什么该模式适用，并排除至少一种替代方案。
不变量：说清循环或递归过程中始终成立的条件。
实现：脱离答案写出最小模板。
验证：手算空输入、单元素、重复值、极值和无解情况。
复盘：24 小时后重写；7 天后做同模式变体。

题单难度标记：E Easy、M Medium、H Hard。建议先完成每节的前两题，再做剩余题目。

3. 复杂度与解题流程

3.1 用输入规模反推复杂度

最大规模 `n`	通常可接受的复杂度
`n <= 20`	`O(2^n)`、状态压缩、回溯
`n <= 100`	`O(n^3)` 可能可行
`n <= 1,000`	`O(n^2)` 通常可行
`n <= 100,000`	`O(n log n)` 或 `O(n)`
`n <= 1,000,000`	通常需要 `O(n)`
值域很大但答案单调	考虑答案二分

这只是经验规则。还要考虑常数、语言、内存和测试组数量。

3.2 五步解题框架

定义对象：元素、区间、节点、边、状态分别是什么。
写暴力法：明确重复计算发生在哪里。
找结构：连续性、有序性、单调性、重叠子问题或连通性。
写不变量：窗口合法、堆顶含义、dp[i] 含义、已访问集合含义。
证明与实现：先证明不会漏解和不会重复，再编码。

3.3 Python 常用工具

from collections import Counter, defaultdict, deque
from functools import cache
from heapq import heappop, heappush, heapify
from bisect import bisect_left, bisect_right
from math import gcd, inf

常见边界规则：

半开区间统一写成 [left, right)。
二分前先写清“第一个满足条件”还是“最后一个满足条件”。
DFS 前决定由 visited、父节点还是原地改值防止重复访问。
Python 最小堆模拟最大堆时存负数。
递归深度可能超过约 1,000 时，优先改为显式栈。

4. 数组、字符串与区间

4.1 数组与哈希

识别信号

需要快速判断“是否出现”“出现次数”“上次位置”。
需要把值映射到索引、频率或分组。
暴力法反复扫描已处理元素。

核心不变量：哈希表准确表示“已处理部分”的摘要。先查询还是先写入取决于当前元素能否与自身配对。

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

复杂度：平均 O(n) 时间，O(n) 空间。

常见陷阱

先写后查会让同一元素被使用两次。
Counter 记录频率；set 只记录存在性。
可变对象不能直接作为字典键；可转成元组或规范字符串。

题单

4.2 前缀和与前缀和 + 哈希

识别信号

多次查询连续区间和。
统计和为 k 的子数组数量。
将“区间问题”转换成“两个前缀状态之差”。

定义 prefix[i] = nums[:i] 的和，则半开区间 [l, r) 的和为 prefix[r] - prefix[l]。

对于和为 k 的子数组，若当前前缀和是 s，需要此前出现过 s-k。必须先放入空前缀 0: 1。

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count = defaultdict(int)
    count[0] = 1
    total = answer = 0
    for x in nums:
        total += x
        answer += count[total - k]
        count[total] += 1
    return answer

复杂度：O(n) 时间，O(n) 空间。

关键区别：含负数时，窗口和不再随指针移动保持单调，普通滑动窗口通常失效；前缀和 + 哈希仍然有效。

题单

E 724. Find Pivot Index
M 560. Subarray Sum Equals K
M 525. Contiguous Array
H 1074. Number of Submatrices That Sum to Target

4.3 差分数组与扫描线

识别信号

多次对整个区间加减一个值，最后一次性读取结果。
区间重叠数量、航班订位、拼车容量。
只关心事件发生点，不需要逐点处理巨大坐标范围。

对闭区间 [l, r] 加 delta：diff[l] += delta，diff[r+1] -= delta。最后做一次前缀和恢复每个位置的值。

def range_add(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    diff = [0] * (n + 1)
    for left, right, delta in updates:
        diff[left] += delta
        if right + 1 < n:
            diff[right + 1] -= delta
    for i in range(1, n):
        diff[i] += diff[i - 1]
    return diff[:n]

复杂度：O(n + q)，其中 q 是更新次数。

扫描线是稀疏差分：把起点记录为 +delta，终点记录为 -delta，按坐标排序累加。必须明确端点是否同时生效；半开区间 [start, end) 最少歧义。

题单

4.4 滑动窗口

识别信号

目标是连续子数组或子串。
找最长、最短、计数，且窗口合法性可增量维护。
当窗口不合法时，移动左端能恢复合法性。

可变窗口不变量：进入收缩循环前，右端已加入；离开收缩循环后，窗口满足约束。

def longest_unique(s: str) -> int:
    last = {}
    left = answer = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        answer = max(answer, right - left + 1)
    return answer

复杂度：两个指针各自最多移动 n 次，因此是 O(n)，不是 O(n^2)。

常见变体

固定长度：右端加入后，窗口超过 k 就移出左端。
最长合法：收缩到合法，再更新答案。
最短满足：满足条件时持续更新答案并收缩。
“恰好 K 个”计数：atMost(K) - atMost(K-1)。

题单

4.5 双指针

识别信号

有序数组中找配对、三元组或最接近目标的组合。
原地删除、分区、压缩。
从两端选择，移动一端能排除一批不可能答案。

def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

证明要点：若和太小，保留更小的左值不可能通过减小右值达到目标，因此可安全增加左指针；和太大时对称。

复杂度：通常 O(n)；若需先排序，总时间 O(n log n)。

题单

4.6 排序与自定义比较

识别信号

原顺序不重要，有序后局部决策变简单。
需要按多个字段稳定排序。
拼接顺序、区间端点、事件优先级决定答案。

Python 的 sort/sorted 是稳定排序。优先使用 key，仅在两元素相对顺序依赖拼接结果等情况使用 cmp_to_key。

from functools import cmp_to_key

def largest_number(nums: list[int]) -> str:
    parts = list(map(str, nums))

    def compare(a: str, b: str) -> int:
        return -1 if a + b > b + a else (1 if a + b < b + a else 0)

    answer = "".join(sorted(parts, key=cmp_to_key(compare)))
    return "0" if answer[0] == "0" else answer

复杂度：一般为 O(n log n) 次比较。

题单

4.7 循环排序

识别信号

长度为 n，值域是 1..n 或 0..n。
要找缺失、重复或错位数字。
允许原地修改数组。

核心思想：值 x 的目标索引是 x-1（或 x）。只要当前元素不在目标位置且不会造成重复，就交换到位。

def first_missing_positive(nums: list[int]) -> int:
    n = len(nums)
    i = 0
    while i < n:
        target = nums[i] - 1
        if 0 <= target < n and nums[target] != nums[i]:
            nums[i], nums[target] = nums[target], nums[i]
        else:
            i += 1
    for i, x in enumerate(nums):
        if x != i + 1:
            return i + 1
    return n + 1

每次交换至少把一个值放到正确位置，因此总交换次数为 O(n)。

题单

E 268. Missing Number
M 287. Find the Duplicate Number
M 442. Find All Duplicates in an Array
H 41. First Missing Positive

4.8 合并区间

识别信号

输入是区间，目标涉及重叠、插入、覆盖或空闲时间。
按起点排序后，只需比较当前区间与最后一个已合并区间。

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda it: it[0])
    merged = []
    for start, end in intervals:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

复杂度：排序 O(n log n)，扫描 O(n)。

边界：start == previous_end 是否重叠由题意决定。时间段常使用半开区间，数值闭区间常把接触视为重叠。

题单

E 228. Summary Ranges
M 56. Merge Intervals
M 57. Insert Interval
H 352. Data Stream as Disjoint Intervals

5. 有序性、栈、队列与堆

5.1 二分查找

识别信号

数组有序，或布尔条件随索引单调变化。
目标是精确值、左边界、右边界或插入位置。

推荐统一使用半开区间 [left, right)，寻找第一个满足 predicate(i) 的位置：

def first_true(n: int, predicate) -> int:
    left, right = 0, n
    while left < right:
        mid = left + (right - left) // 2
        if predicate(mid):
            right = mid
        else:
            left = mid + 1
    return left

不变量：答案始终位于 [left, right]；left 左侧全部不满足，right 及其右侧候选已知满足或是哨兵。

复杂度：O(log n)。

题单

5.2 答案二分

识别信号

问“最小的最大值”或“最大的最小值”。
给定候选答案 x，可以在 O(n) 或 O(n log n) 内判断是否可行。
可行性关于 x 单调。

def min_eating_speed(piles: list[int], hours: int) -> int:
    def feasible(speed: int) -> bool:
        return sum((pile + speed - 1) // speed for pile in piles) <= hours

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if feasible(mid):
            right = mid
        else:
            left = mid + 1
    return left

复杂度：O(check × log(answer_range))。

最难部分不是二分代码，而是：

确定答案上下界。
写出单调的可行性函数。
明确寻找第一个可行值还是最后一个可行值。

题单

M 875. Koko Eating Bananas
M 1011. Capacity To Ship Packages Within D Days
H 410. Split Array Largest Sum
H 778. Swim in Rising Water

5.3 栈与表达式解析

识别信号

最近打开的结构最先关闭：括号、标签、递归展开。
需要撤销、返回上一级、处理运算符优先级。
暴力法反复查找最近的未匹配项。

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

复杂度：O(n) 时间，最坏 O(n) 空间。

表达式解析要分别处理：数字读取、符号、括号、运算符优先级和整数除法规则。不要把它们混成一个不可验证的分支。

题单

E 20. Valid Parentheses
M 150. Evaluate Reverse Polish Notation
M 394. Decode String
H 224. Basic Calculator

5.4 单调栈

识别信号

对每个元素寻找左/右侧第一个更大或更小元素。
柱状图、每日温度、股票跨度、贡献法。

栈中保存尚未找到答案的索引，并保持对应值单调。

def daily_temperatures(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    stack = []  # temperatures[index] 单调递减
    for i, value in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < value:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

每个元素只进栈和出栈一次，总时间 O(n)。

陷阱：明确弹出条件是 < 还是 <=。处理重复值时，两侧边界通常一边严格、一边非严格，避免重复计数。

题单

5.5 单调队列

识别信号

固定窗口中的最大值或最小值。
需要队首给出当前最优值，同时旧元素会从左侧失效。

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    q = deque()  # 索引；对应值单调递减
    answer = []
    for right, x in enumerate(nums):
        while q and nums[q[-1]] <= x:
            q.pop()
        q.append(right)
        left = right - k + 1
        if q[0] < left:
            q.popleft()
        if left >= 0:
            answer.append(nums[q[0]])
    return answer

复杂度：摊还 O(n) 时间，O(k) 空间。

题单

5.6 堆与 Top K

识别信号

反复取当前最小值或最大值。
只需保留前 k 个元素，不需要完整排序。
多个候选持续加入，最优候选持续弹出。

保留最大的 k 个元素时，维护大小不超过 k 的最小堆；堆顶是这 k 个元素中最弱的一个。

from heapq import heappush, heapreplace

def kth_largest(nums: list[int], k: int) -> int:
    heap = []
    for x in nums:
        if len(heap) < k:
            heappush(heap, x)
        elif x > heap[0]:
            heapreplace(heap, x)
    return heap[0]

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

题单

E 1046. Last Stone Weight
M 215. Kth Largest Element in an Array
M 347. Top K Frequent Elements
H 295. Find Median from Data Stream

5.7 双堆

识别信号

数据流中持续查询中位数。
需要维护动态集合的较小一半和较大一半。

用最大堆 low 保存较小一半，用最小堆 high 保存较大一半。Python 中 low 存负数。

from heapq import heappop, heappush

class MedianFinder:
    def __init__(self):
        self.low = []   # max heap via negatives
        self.high = []  # min heap

    def addNum(self, num: int) -> None:
        heappush(self.low, -num)
        heappush(self.high, -heappop(self.low))
        if len(self.high) > len(self.low):
            heappush(self.low, -heappop(self.high))

    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

不变量：len(low) 等于 len(high) 或多 1；low 中所有值不大于 high 中所有值。

题单

5.8 K 路归并

识别信号

合并多个已排序数组或链表。
在多个有序序列中找第 k 小值或最小范围。

堆中只放每个序列当前的最小候选。弹出后，只推进该候选所属序列。

from heapq import heappop, heappush

def merge_sorted_arrays(arrays: list[list[int]]) -> list[int]:
    heap = []
    for row, values in enumerate(arrays):
        if values:
            heappush(heap, (values[0], row, 0))
    answer = []
    while heap:
        value, row, col = heappop(heap)
        answer.append(value)
        if col + 1 < len(arrays[row]):
            heappush(heap, (arrays[row][col + 1], row, col + 1))
    return answer

总元素数为 N、序列数为 k 时，复杂度为 O(N log k)。

题单

6. 链表

6.1 原地反转与指针重连

识别信号

反转整个链表、子链表或每 k 个节点。
合并、删除、交换节点时要求 O(1) 额外空间。

反转的关键是先保存 next，否则重连后会丢失剩余链表。

def reverse_list(head):
    previous = None
    current = head
    while current:
        following = current.next
        current.next = previous
        previous = current
        current = following
    return previous

复杂度：O(n) 时间，O(1) 额外空间。

哑节点 dummy：当头节点可能被删除或前面需要插入新节点时，增加一个固定前驱能统一边界处理。

题单

6.2 快慢指针

识别信号

判断链表是否有环、找环入口、中点或倒数第 k 个节点。
状态按确定规则不断转移，需要检测循环。

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

Floyd 判圈：若有环，快指针每轮相对慢指针前进一个位置，最终必相遇。相遇后，一个指针回到头部，两者每次走一步，再次相遇处就是环入口。

题单

7. 树与 Trie

7.1 树 DFS

识别信号

路径和、子树信息、祖先关系、树高、直径。
当前节点的答案依赖左右子树的返回值。

先决定递归函数的语义：它接收什么，返回什么。下面返回以节点为根的高度，同时用闭包变量维护全局直径。

def diameter_of_binary_tree(root) -> int:
    diameter = 0

    def height(node) -> int:
        nonlocal diameter
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)

    height(root)
    return diameter

复杂度：O(n) 时间，递归栈 O(h)；h 是树高。

三种位置

前序：进入节点时处理，适合路径状态和复制。
中序：BST 中得到有序序列。
后序：子树先返回，适合高度、直径和树 DP。

题单

7.2 树 BFS

识别信号

层序遍历、最浅深度、每层统计。
需要按距离从近到远访问节点。

from collections import deque

def level_order(root) -> list[list[int]]:
    if not root:
        return []
    queue = deque([root])
    answer = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        answer.append(level)
    return answer

每层开始时固定 len(queue)，否则本层新加入的节点会被错误地混入当前层。

题单

7.3 二叉搜索树

识别信号

对每个节点，左子树所有值更小，右子树所有值更大。
查找、插入、删除、排名、前驱和后继。

验证 BST 不能只比较父子节点，必须维护整个允许区间。

def is_valid_bst(root) -> bool:
    def valid(node, low, high) -> bool:
        if not node:
            return True
        if not low < node.val < high:
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)

    return valid(root, float('-inf'), float('inf'))

平均操作复杂度 O(log n)，但未平衡 BST 最坏退化为 O(n)。

题单

7.4 Trie 前缀树

识别信号

大量字符串的前缀查询。
字典中搜索单词，或在网格中同时匹配多个单词。
多个字符串共享前缀，需要复用状态。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_word

单次操作复杂度 O(L)，其中 L 是字符串长度。空间与所有不重复前缀的字符总数成正比。

题单

8. 搜索与图

8.1 回溯、子集与排列

识别信号

枚举所有可行组合、排列、切分或路径。
每一步有多个选择，选择会影响后续合法性。
输入规模较小，输出本身可能是指数级。

回溯框架是：选择 → 递归 → 撤销。path 表示当前决策路径，start 或 used 控制候选范围。

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

    def backtrack(start: int) -> None:
        answer.append(path.copy())
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return answer

去重原则：先排序；同一递归层跳过相同值 if i > start and nums[i] == nums[i-1]。不要跨层错误去重。

复杂度通常至少为输出规模。子集为 O(n·2^n)，排列为 O(n·n!)。

题单

8.2 图 DFS/BFS

识别信号

连通块、岛屿、可达性、最少步数。
状态可视为节点，合法转移可视为边。

图可能不连通，因此遍历所有节点并从每个未访问节点启动一次搜索。

from collections import deque

def shortest_unweighted(graph: list[list[int]], start: int) -> list[int]:
    distance = [-1] * len(graph)
    distance[start] = 0
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return distance

复杂度：邻接表下 O(V + E) 时间，O(V) 空间。

选择规则

只需可达性或连通块：DFS/BFS 均可。
无权图最短路：BFS。
深图可能触发递归上限：迭代 DFS 或 BFS。
网格访问后可原地改值时，可省去 visited。

题单

8.3 拓扑排序

识别信号

依赖关系、课程先修、任务调度、字母顺序。
需要判断有向图是否有环，或输出满足依赖的顺序。

Kahn 算法：统计入度，把所有入度为 0 的节点入队；删除它们的出边并产生新的入度 0 节点。

from collections import deque

def topological_sort(n: int, edges: list[tuple[int, int]]) -> list[int]:
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for source, target in edges:
        graph[source].append(target)
        indegree[target] += 1
    queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else []

若最终处理节点数小于 n，图中存在环。复杂度 O(V + E)。

题单

8.4 并查集（DSU）

识别信号

动态合并集合并查询两个元素是否连通。
无向图判环、连通分量、冗余边、等价关系。

class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

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

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

路径压缩 + 按大小合并后，每次操作的摊还复杂度接近 O(1)，严格写作 O(α(n))。

局限：普通并查集擅长合并，不擅长删除边，也不能直接恢复具体路径。

题单

8.5 最短路

先按边权选择算法：

条件	算法	复杂度
无权边或权重相同	BFS	`O(V+E)`
权重只有 0/1	0-1 BFS	`O(V+E)`
非负权	Dijkstra	`O((V+E) log V)`
有负权、需检测负环	Bellman-Ford	`O(VE)`
所有点对且 `V` 较小	Floyd-Warshall	`O(V^3)`

Dijkstra 每次确定当前距离最小的未完成节点。堆中可能存在旧记录，弹出时必须跳过。

from heapq import heappop, heappush
from math import inf

def dijkstra(graph: list[list[tuple[int, int]]], start: int) -> list[float]:
    distance = [inf] * len(graph)
    distance[start] = 0
    heap = [(0, start)]
    while heap:
        dist, node = heappop(heap)
        if dist != distance[node]:
            continue
        for neighbor, weight in graph[node]:
            candidate = dist + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heappush(heap, (candidate, neighbor))
    return distance

陷阱：Dijkstra 不适用于负边；“访问过”不能在入堆时确定，节点可能稍后得到更短距离。

题单

8.6 最小生成树（MST）

识别信号

用最小总代价连接所有节点。
最终需要 V-1 条边且不能有环。

Kruskal：按边权排序，依次加入不会形成环的边；用并查集判环。

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> int | None:
    dsu = DSU(n)
    cost = used = 0
    for weight, a, b in sorted(edges):
        if dsu.union(a, b):
            cost += weight
            used += 1
            if used == n - 1:
                return cost
    return 0 if n == 0 else None

复杂度主要来自排序：O(E log E)。

区分：最短路最小化某个起点到其他点的路径；MST 最小化连接所有点的总边权。两者目标不同。

题单

9. 贪心、位运算与数学

9.1 贪心

识别信号

每步做局部最优选择，并希望得到全局最优。
排序后，可通过最早结束、最大覆盖、最低成本等规则持续推进。
只需维护“到当前位置为止的最佳边界”。

贪心不是“凭直觉挑最好”。必须有证明。常用证明方式：

交换论证：任意最优解都可把首个选择替换成贪心选择且不变差。
领先性质：每一步贪心方案至少不落后于其他方案。
切分性质：一个安全选择后，剩余问题仍是同类子问题。

以跳跃游戏为例，farthest 始终是当前可达位置能扩展到的最远边界：

def can_jump(nums: list[int]) -> bool:
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True

题单

9.2 位运算

常用恒等式：

x & 1：最低位是否为 1。
x & (x - 1)：删除最低位的 1。
x & -x：提取最低位的 1。
x ^ x = 0，x ^ 0 = x。
mask & (1 << i)：检查第 i 位。
mask | (1 << i)：设置第 i 位。

def single_number(nums: list[int]) -> int:
    answer = 0
    for x in nums:
        answer ^= x
    return answer

位掩码适合表示规模较小的集合。第 i 位表示第 i 个对象是否存在，常用于状态压缩 DP。

Python 陷阱：整数没有固定字长。模拟 32 位有符号整数时需要掩码 0xFFFFFFFF 并手动还原符号。

题单

E 136. Single Number
E 338. Counting Bits
M 371. Sum of Two Integers
H 1178. Number of Valid Words for Each Puzzle

9.3 数论与组合

高频工具

最大公约数：欧几里得算法 gcd(a, b)。
最小公倍数：lcm(a, b) = a // gcd(a, b) * b。
素数筛：批量判断 0..n 中的素数。
快速幂：pow(base, exponent, mod)。
组合数：预计算阶乘与逆阶乘，或使用递推。
同余：加减乘每步取模；除法需使用模逆，不能直接整除。

def sieve(n: int) -> list[int]:
    is_prime = bytearray(b'\x01') * (n + 1)
    if n >= 0:
        is_prime[0] = 0
    if n >= 1:
        is_prime[1] = 0
    p = 2
    while p * p <= n:
        if is_prime[p]:
            is_prime[p * p:n + 1:p] = b'\x00' * (((n - p * p) // p) + 1)
        p += 1
    return [i for i, prime in enumerate(is_prime) if prime]

题单

10. 动态规划

10.1 DP 通用状态设计

识别信号

求最大值、最小值、方案数或可行性。
问题能分解为重叠子问题。
当前最优解依赖较小规模状态，且状态包含足够信息描述未来。

四个核心问题

状态：dp[...] 精确表示什么？
转移：最后一步做了什么选择？它从哪些旧状态来？
初始值：最小子问题的答案是什么？不可达状态用什么表示？
遍历顺序：计算当前状态前，依赖状态是否已经完成？

以打家劫舍为例，previous 表示处理到前一间房的最优答案，before_previous 表示处理到前两间房的最优答案：

def rob(nums: list[int]) -> int:
    before_previous = previous = 0
    for money in nums:
        before_previous, previous = previous, max(previous, before_previous + money)
    return previous

Top-down 与 Bottom-up

记忆化搜索：更贴近递归定义，只计算可达状态；要注意递归深度和缓存键。
递推：常数更小，易做空间压缩；必须正确确定遍历顺序。

空间压缩原则：只有当当前层仅依赖固定数量的前置层时才压缩。先写正确二维版本，再压缩。

题单

10.2 背包 DP

背包问题的核心状态通常是 dp[c]：容量或目标和为 c 时的最优值、方案数或可行性。

0/1 背包

每件物品最多用一次。容量必须倒序遍历，避免同一物品在本轮被重复使用。

def zero_one_knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]

完全背包

每件物品可重复使用。容量通常正序遍历，使当前物品可以在本轮再次贡献。

组合数与排列数

外层遍历物品、内层遍历容量：通常统计组合，顺序不重要。
外层遍历容量、内层遍历物品：通常统计排列，顺序重要。

题单

10.3 序列与字符串 DP

最长递增子序列（LIS）

dp[i] 可定义为以 nums[i] 结尾的最长递增子序列长度，得到 O(n^2)。更优方法维护 tails[length-1]：长度为 length 的递增子序列能取得的最小结尾。

from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

注意：tails 不一定是原数组中的实际 LIS，它是各长度最优结尾的摘要。

双序列 DP

最长公共子序列、编辑距离常使用 dp[i][j] 表示两个前缀的答案。转移取决于最后两个字符是否相同。

def longest_common_subsequence(a: str, b: str) -> int:
    previous = [0] * (len(b) + 1)
    for x in a:
        current = [0]
        for j, y in enumerate(b, 1):
            if x == y:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[-1]))
        previous = current
    return previous[-1]

题单

10.4 网格 DP

识别信号

在网格中从起点走到终点，移动方向受限。
统计路径数或求路径最大/最小代价。
当前格只依赖上方、左方或有限邻居。

def unique_paths_with_obstacles(grid: list[list[int]]) -> int:
    if not grid or not grid[0]:
        return 0
    cols = len(grid[0])
    dp = [0] * cols
    dp[0] = 1
    for row in grid:
        for col in range(cols):
            if row[col] == 1:
                dp[col] = 0
            elif col > 0:
                dp[col] += dp[col - 1]
    return dp[-1]

dp[col] 在更新前表示上方状态，更新后表示当前格状态；dp[col-1] 已表示左方状态。

若允许向四个方向移动且可能回到旧格，通常不是简单网格 DP，应考虑 BFS、Dijkstra 或记忆化搜索。

题单

M 62. Unique Paths
M 64. Minimum Path Sum
M 221. Maximal Square
H 329. Longest Increasing Path in a Matrix

10.5 区间 DP

识别信号

对连续区间进行合并、切分或删除。
最后一次操作把区间 [left, right] 分成更小区间。
状态自然包含左右边界。

区间 DP 通常按区间长度从小到大计算：

def matrix_chain_cost(dimensions: list[int]) -> int:
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            dp[left][right] = min(
                dp[left][mid]
                + dp[mid + 1][right]
                + dimensions[left] * dimensions[mid + 1] * dimensions[right + 1]
                for mid in range(left, right)
            )
    return dp[0][n - 1] if n else 0

典型复杂度为 O(n^3) 时间和 O(n^2) 空间。

题单

10.6 树 DP

识别信号

每个节点的选择影响子节点能否选择。
答案依赖子树的多个状态，而不是单个高度或和。

对每个节点返回一组状态。打家劫舍 III 中返回 (skip, take)：

def rob_tree(root) -> int:
    def dfs(node) -> tuple[int, int]:
        if not node:
            return 0, 0
        left_skip, left_take = dfs(node.left)
        right_skip, right_take = dfs(node.right)
        skip = max(left_skip, left_take) + max(right_skip, right_take)
        take = node.val + left_skip + right_skip
        return skip, take

    return max(dfs(root))

复杂度通常为 O(n)，因为每个节点只处理一次。

题单

10.7 状态压缩 DP

识别信号

对象数量通常不超过 15～20。
状态需要记录一个子集“哪些对象已经使用”。
排列、分配、访问所有节点等指数问题中存在大量重复子问题。

mask 的第 i 位表示对象 i 是否已使用。下面计算访问所有节点的最短路径，状态为 (node, mask)；本质是多源 BFS：

from collections import deque

def shortest_path_all_nodes(graph: list[list[int]]) -> int:
    n = len(graph)
    full = (1 << n) - 1
    queue = deque((i, 1 << i, 0) for i in range(n))
    seen = {(i, 1 << i) for i in range(n)}
    while queue:
        node, mask, distance = queue.popleft()
        if mask == full:
            return distance
        for neighbor in graph[node]:
            state = (neighbor, mask | (1 << neighbor))
            if state not in seen:
                seen.add(state)
                queue.append((neighbor, state[1], distance + 1))
    return 0

典型复杂度为 O(2^n · poly(n))。

题单

11. 高级数据结构与字符串算法

11.1 Fenwick Tree（树状数组）

用途：动态单点更新 + 前缀和查询。代码短、常数小，但不直接支持任意区间赋值或复杂聚合。

class Fenwick:
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)

    def add(self, index: int, delta: int) -> None:
        index += 1
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, end: int) -> int:
        total = 0
        while end > 0:
            total += self.tree[end]
            end -= end & -end
        return total

    def range_sum(self, left: int, right: int) -> int:
        return self.prefix_sum(right) - self.prefix_sum(left)

这里 range_sum(left, right) 查询半开区间 [left, right)。更新和查询均为 O(log n)。

题单

11.2 Segment Tree（线段树）

用途：动态区间查询；合并函数可为和、最小值、最大值、最大子段等。通过懒标记还能支持区间更新。

迭代线段树适合单点更新和区间聚合：

class SegmentTree:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        self.tree[self.n:] = nums
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index: int, value: int) -> None:
        index += self.n
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[2 * index] + self.tree[2 * index + 1]

    def query(self, left: int, right: int) -> int:
        left += self.n
        right += self.n
        total = 0
        while left < right:
            if left & 1:
                total += self.tree[left]
                left += 1
            if right & 1:
                right -= 1
                total += self.tree[right]
            left //= 2
            right //= 2
        return total

单点更新和区间查询均为 O(log n)，空间为 O(n)。

选择规则：只要前缀和且操作可逆，优先 Fenwick Tree；需要通用区间合并或懒更新时用 Segment Tree。

题单

11.3 字符串匹配：KMP

识别信号

在线性时间内寻找模式串在文本中的位置。
匹配失败后，希望复用已知相等的前后缀，而不是回退文本指针。

lps[i] 表示模式串 pattern[:i+1] 的最长真前缀与真后缀的公共长度。

def kmp_search(text: str, pattern: str) -> int:
    if not pattern:
        return 0
    lps = [0] * len(pattern)
    length = 0
    for i in range(1, len(pattern)):
        while length and pattern[i] != pattern[length]:
            length = lps[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length

    matched = 0
    for i, ch in enumerate(text):
        while matched and ch != pattern[matched]:
            matched = lps[matched - 1]
        if ch == pattern[matched]:
            matched += 1
            if matched == len(pattern):
                return i - len(pattern) + 1
    return -1

复杂度：O(n + m) 时间，O(m) 空间。

题单

11.4 Rolling Hash 与回文算法

Rolling Hash 把子串映射成数值，使等长子串比较接近 O(1)。哈希相等不严格保证字符串相等；高可靠性场景应使用双哈希或最终字符比较。

前缀哈希的一般形式：

def rolling_hashes(s: str, length: int, base: int = 911382323, mod: int = 972663749):
    if length == 0:
        return [0] * (len(s) + 1)
    result = []
    value = 0
    power = pow(base, length, mod)
    for i, ch in enumerate(s):
        code = ord(ch)
        value = (value * base + code) % mod
        if i >= length:
            value = (value - ord(s[i - length]) * power) % mod
        if i >= length - 1:
            result.append(value)
    return result

回文问题选择：

单次最长回文子串：中心扩展 O(n^2) 通常足够。
大量回文区间查询：DP 或哈希。
要求严格线性：Manacher，面试中通常属于进阶。

题单

12. 设计类数据结构

12.1 LRU Cache

要求：get 与 put 都是 O(1)。

组合结构：

哈希表：键到节点，O(1) 定位。
双向链表：按最近使用顺序排列，O(1) 删除和移动节点。

Python 标准库 OrderedDict 已提供所需操作；除非题目要求手写结构，直接复用它最清晰。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

12.2 O(1) 随机集合

要同时支持 O(1) 插入、删除和随机访问：

动态数组负责随机索引。
哈希表记录值在数组中的索引。
删除时把末尾元素交换到被删位置，再弹出末尾。

12.3 设计题通用检查表

列出每个操作的目标复杂度。
为每个复杂度选择对应基础结构。
写清多个结构之间必须同步的不变量。
先处理覆盖、删除最后元素、容量为 1 等边界。
若要求并发安全，必须额外定义锁粒度；LeetCode 通常不要求。

题单

13. 12 周学习路线

13.1 周计划

每周建议 5 天练习、1 天混合模拟、1 天复盘。每日 2～3 题即可；重点是重写与归纳。

周	主题	必做题
1	数组、哈希、前缀和	1, 49, 128, 560, 525
2	滑动窗口、双指针	3, 424, 76, 15, 42
3	排序、区间、二分	56, 57, 33, 34, 875
4	栈、单调结构	20, 394, 739, 84, 239
5	堆、Top K、K 路归并	215, 347, 295, 23, 632
6	链表与树基础	206, 92, 142, 102, 236
7	BST、Trie、回溯	98, 230, 208, 78, 39
8	图搜索、拓扑、并查集	200, 994, 207, 684, 721
9	最短路、MST、贪心	743, 1631, 1584, 55, 134
10	DP 基础与背包	198, 322, 416, 494, 518
11	序列、网格、区间、树 DP	300, 1143, 64, 312, 337
12	高级结构 + 综合模拟	307, 315, 28, 146，加 2 次 90 分钟模拟

13.2 单题时间盒

按目标难度设置时间盒：

Easy：15 分钟。
Medium：30 分钟。
Hard：45 分钟。

超时后的正确做法：

只看提示或算法标签，不先看完整代码。
再独立尝试 10 分钟。
仍不会时阅读解法，关闭解法后从空白重写。
记录“缺失的识别信号或不变量”，不要抄整段答案。

13.3 三轮掌握标准

轮次	目标	通过条件
第一轮	认识模式	能解释为什么选该模式
第二轮	独立实现	30 分钟内无提示通过 Medium
第三轮	迁移变体	能处理边界变化并说明复杂度

建议维护三类题目状态：

A：可独立写出并证明。
B：知道模式，但实现或边界不稳。
C：无法识别模式。

复习顺序永远是 C → B → A，而不是继续刷新题制造完成感。

14. 复盘模板与面试检查表

14.1 每题复盘模板

题目：
日期：
结果：独立完成 / 提示后完成 / 看解答完成

1. 输入结构与约束：
2. 识别信号：
3. 使用模式：
4. 核心不变量：
5. 时间 / 空间复杂度：
6. 我卡住的具体位置：
7. 错误原因：识别 / 状态 / 转移 / 边界 / 实现
8. 一个可迁移结论：
9. 下次复习：明天 / 7 天后 / 30 天后

14.2 编码前检查

是否明确空输入、单元素、重复值和无解时的返回值？
是否写清区间是闭区间还是半开区间？
是否能用一句话定义窗口、堆顶、递归返回值或 dp 状态？
是否能证明一次指针移动、一次贪心选择或一次状态转移不会漏解？
当前复杂度是否匹配输入规模？

14.3 编码后检查

手算最小输入与一个普通输入。
检查索引 0、n-1、right+1 和空堆/空栈。
检查重复值下的 < 与 <=。
检查可变对象是否被复制，特别是回溯的 path.copy()。
检查整数溢出；Python 整数不会溢出，但其他语言会。
明确时间与空间复杂度，包括排序、递归栈和输出空间。

14.4 模式选择速查

题目特征	首选模式
连续子数组/子串，合法性可维护	滑动窗口
连续区间和或子数组计数	前缀和 + 哈希
有序数组找配对	双指针
单调可行性，求临界答案	答案二分
左右第一个更大/更小	单调栈
窗口最大/最小	单调队列
持续取最优候选	堆
多个有序序列合并	K 路归并
所有组合或排列	回溯
无权最少步数	BFS
依赖顺序或有向环	拓扑排序
动态连通性	并查集
非负权最短路	Dijkstra
连接所有点的最小总代价	MST
重叠子问题 + 最优值/计数	DP
动态单点更新 + 区间查询	Fenwick / Segment Tree

最后建议

这套 39 模式足以覆盖大多数通用软件工程面试中的 LeetCode 题型，但“完整”不等于每个模式都同等重要。优先掌握标记为“必学”和“高频”的部分；高级字符串算法、线段树和状态压缩 DP 应在基础模式稳定后学习。

真正的掌握标准不是题量，而是：看到新题后能识别结构，写出不变量，独立实现，并解释正确性与复杂度。

Name		Name	Last commit message	Last commit date
README.md		README.md

Latest commit

History

Folders and files

Repository files navigation

LeetCode Algorithm Patterns：算法模式完整教程与刷题路线

目录

1. 完整性评估

1.1 结论

1.2 完整模式地图

2. 使用方法

3. 复杂度与解题流程

3.1 用输入规模反推复杂度

3.2 五步解题框架

3.3 Python 常用工具

4. 数组、字符串与区间

4.1 数组与哈希

4.2 前缀和与前缀和 + 哈希

4.3 差分数组与扫描线

4.4 滑动窗口

4.5 双指针

4.6 排序与自定义比较

4.7 循环排序

4.8 合并区间

5. 有序性、栈、队列与堆

5.1 二分查找

5.2 答案二分

5.3 栈与表达式解析

5.4 单调栈

5.5 单调队列

5.6 堆与 Top K

5.7 双堆

5.8 K 路归并

6. 链表

6.1 原地反转与指针重连

6.2 快慢指针

7. 树与 Trie

7.1 树 DFS

7.2 树 BFS

7.3 二叉搜索树

7.4 Trie 前缀树

8. 搜索与图

8.1 回溯、子集与排列

8.2 图 DFS/BFS

8.3 拓扑排序

8.4 并查集（DSU）

8.5 最短路

8.6 最小生成树（MST）

9. 贪心、位运算与数学

9.1 贪心

9.2 位运算

9.3 数论与组合

10. 动态规划

10.1 DP 通用状态设计

四个核心问题

10.2 背包 DP

0/1 背包

完全背包

组合数与排列数

10.3 序列与字符串 DP

最长递增子序列（LIS）

双序列 DP

10.4 网格 DP

10.5 区间 DP

10.6 树 DP

10.7 状态压缩 DP

11. 高级数据结构与字符串算法

11.1 Fenwick Tree（树状数组）

11.2 Segment Tree（线段树）

11.3 字符串匹配：KMP

11.4 Rolling Hash 与回文算法

12. 设计类数据结构

12.1 LRU Cache

12.2 O(1) 随机集合

12.3 设计题通用检查表

13. 12 周学习路线

13.1 周计划

13.2 单题时间盒

13.3 三轮掌握标准

14. 复盘模板与面试检查表

14.1 每题复盘模板