【算法体系篇】持续更新

算法知识体系：从基础到竞赛

本文是算法学习的完整知识地图。按数据结构→基础算法→高级算法→竞赛专题四层递进，每个条目附核心模板和典型题目。

---

一、数据结构篇

1.1 线性结构

数组与矩阵

技术	核心思路	典型题
前缀和	pref[i] = Σarr[0..i-1]，区间和 O(1)	区域和检索
差分数组	diff[i] = arr[i]-arr[i-1]，区间增减 O(1)	航班预订统计
滑动窗口	双指针维护窗口，右扩左缩，满足条件时更新结果	无重复字符最长子串
双指针	对撞指针/快慢指针/分离双指针	三数之和、接雨水
原地哈希	将值映射到下标，标记为负	缺失的第一个正数

// 滑动窗口模板
int l = 0, r = 0;
while (r < n) {
    window.add(arr[r++]);     // 扩大窗口
    while (needShrink()) {
        window.remove(arr[l++]); // 缩小窗口
    }
    updateResult();             // 更新答案
}

链表

技术	核心思路	典型题
快慢指针	fast 走 2 步, slow 走 1 步；fast 到末尾时 slow 在中点	链表中点、环形链表
反转链表	prev/curr/next 三指针迭代；递归头插法	反转链表、K 个一组翻转
虚拟头节点	dummy node 简化边界处理	合并有序链表、删除节点
Floyd 判圈	快慢指针相遇后，slow 重置到头，同步走直到再次相遇	环形链表 II

栈与单调栈

单调栈的核心是维护栈内元素的单调性（递增或递减），用于快速找到元素左右两侧第一个比它大/小的元素——这是解决”下一个更大元素”类问题的统一框架。

// 单调递增栈：找下一个更小元素
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
        int top = stack.pop();
        // arr[top] 的下一个更小元素是 arr[i]
    }
    stack.push(i);
}

队列与单调队列

单调队列维护队列内元素的单调性，队首始终是当前窗口的最值。核心操作：入队时从队尾弹出破坏单调性的元素；队首元素过期（不在窗口内）时从队首弹出。

应用场景：滑动窗口最大值、带限制的最短子数组。

1.2 树形结构

二叉树遍历

遍历方式	递归	迭代（栈模拟）	Morris（O(1)空间）
前序	node→left→right	栈存右子	利用空闲指针
中序	left→node→right	一直往左走	利用前驱节点
后序	left→right→node	前序逆序或双栈	复杂

// 中序迭代模板
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
    while (curr != null) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    visit(curr);
    curr = curr.right;
}

平衡搜索树

结构	平衡策略	查找	插入	删除
AVL 树	旋转（LL/RR/LR/RL），高度差 ≤1	O(log n)	O(log n)	O(log n)
红黑树	颜色翻转 + 旋转，黑高相等	O(log n)	O(log n)	O(log n)
B 树	节点分裂/合并，m 叉	O(log n)	O(log n)	O(log n)
Treap	随机优先级 + 旋转	O(log n) 期望	O(log n)	O(log n)
Splay	访问时旋转至根（摊还）	O(log n) 摊还	O(log n)	O(log n)

红黑树 vs AVL：AVL 更严格平衡 → 查找更快；红黑树插入/删除更少旋转 → 修改更快。Java TreeMap 使用红黑树。Android 的 ArrayMap 在元素少（≤8）时使用数组二分查找代替红黑树（节省内存）。

线段树（Segment Tree）

// 区间查询、单点/区间更新 O(log n)
class SegmentTree {
    int[] tree, lazy;
    int n;

    void build(int node, int l, int r, int[] arr) {
        if (l == r) { tree[node] = arr[l]; return; }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, arr);
        build(node * 2 + 1, mid + 1, r, arr);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    // 懒标记下推（Lazy Propagation）
    void pushDown(int node, int l, int r) {
        if (lazy[node] == 0) return;
        int mid = (l + r) / 2;
        tree[node*2] += lazy[node] * (mid - l + 1);
        tree[node*2+1] += lazy[node] * (r - mid);
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
        lazy[node] = 0;
    }
}

树状数组（Fenwick Tree / BIT）

前缀和查询和单点更新都是 O(log n)，比线段树代码量小 3-4 倍，是竞赛中的首选。

class Fenwick {
    int[] tree;
    void add(int i, int delta) {
        for (; i < tree.length; i += i & -i) tree[i] += delta;
    }
    int sum(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += tree[i];
        return s;
    }
}

核心：i & -i 提取整数 i 的最低有效位（lowbit），树状数组利用 lowbit 将 n 的二进制表示分解为 O(log n) 个区间。

并查集（Disjoint Set Union）

class DSU {
    int[] parent, rank;
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }
    void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) parent[rx] = ry;   // 按秩合并
        else if (rank[rx] > rank[ry]) parent[ry] = rx;
        else { parent[rx] = ry; rank[ry]++; }
    }
}

1.3 字符串结构

Trie（前缀树/字典树）

每个节点存 26 个子节点指针和一个 isEnd 标记。用于字符串前缀匹配、自动补全。插入/查找时间复杂度 O(L)，L 为字符串长度。

后缀数组（Suffix Array）

sa[i] = 字典序第 i 小的后缀的起始位置。核心算法：倍增法 O(n log n)。配合 rank[] 和 height[]（LCP：Longest Common Prefix，用 Kasai 算法 O(n) 计算），可在 O(log n) 内完成字符串匹配和公共子串查询。

---

二、基础算法篇

2.1 排序算法

算法	平均时间	最坏时间	空间	稳定	适用场景
快速排序	O(n log n)	O(n²)	O(log n)	否	通用，工业界首选
归并排序	O(n log n)	O(n log n)	O(n)	是	外部排序、链表排序
堆排序	O(n log n)	O(n log n)	O(1)	否	内存受限场景
计数排序	O(n + k)	O(n + k)	O(k)	是	整数范围小 (k ≤ n)
基数排序	O(d(n + k))	O(d(n + k))	O(n + k)	是	字符串/大整数排序
TimSort	O(n log n)	O(n log n)	O(n)	是	Java/Android 默认排序

O(n log n) 下界的简要证明：基于比较的排序算法，决策树叶子数 ≥ n!。二叉树高度 h 满足 2^h ≥ n! → h ≥ log₂(n!)。由 Stirling 近似，log₂(n!) = n log₂ n - n log₂ e + O(log n) = Ω(n log n)。

2.2 搜索算法

二分查找模板

// 查找第一个 ≥ target 的位置（lower_bound）
int binarySearch(int[] arr, int target) {
    int l = 0, r = arr.length;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;  // l == r, 指向第一个 ≥ target 的位置
}

核心原则：维持循环不变量——l 左侧的元素一律 < target，r 及 r 右侧的元素一律 ≥ target。l 和 r 缩到相等时即分界点。

图搜索

算法	数据结构	空间	特点
BFS	队列	O(V+E)	无权图最短路径、层序遍历
DFS	栈/递归	O(V)	连通性、拓扑排序、回溯
双向 BFS	两个队列	O(b^(d/2))	大幅减少搜索空间
A*	优先队列 f=g+h	取决于启发	带启发式最短路径

2.3 动态规划

DP 五步法：

1. 定义状态（最难）
2. 定义状态转移方程
3. 初始化边界条件
4. 确定计算顺序
5. 空间优化（可选）

DP 类型	状态结构	代表问题
线性 DP	dp[i]	爬楼梯、打家劫舍、最长递增子序列
背包 DP	dp[i][w]	0-1 背包、完全背包、多重背包
区间 DP	dp[l][r]	石子合并、最长回文子序列
树形 DP	dp[node]	树的直径、最大独立集
状态压缩 DP	dp[mask]	旅行商 TSP、分配问题
数位 DP	dp[pos][tight]	1～N 中满足条件的数的个数
概率 DP	dp[i] = Σp·dp[j]	期望步数、游戏通关概率

背包问题模板

// 0-1 背包（逆序遍历，保证每件物品只用一次）
for (int item : items)
    for (int w = W; w >= weight[item]; w--)
        dp[w] = Math.max(dp[w], dp[w - weight[item]] + value[item]);

// 完全背包（正序遍历，物品可无限次使用）
for (int item : items)
    for (int w = weight[item]; w <= W; w++)
        dp[w] = Math.max(dp[w], dp[w - weight[item]] + value[item]);

DP 优化技术：单调队列优化（斜率优化，将 O(n²) 降到 O(n)）、四边形不等式优化（区间 DP 决策单调性）、CDQ 分治优化、矩阵快速幂优化（线性递推）。

---

三、高级算法篇

3.1 图论算法

最短路径

Bellman-Ford 的第 k 轮松弛保证所有 ≤ k 条边的最短路径被找到。该性质不仅用于负权检测，也衍生出”恰好经过 k 条边的最短路径”这类变体——这正是 Floyd-Warshall 思想从另一角度的特化。

最小生成树 MST

算法	思路	复杂度	特点
Kruskal	边排序 + 并查集	O(E log E)	稀疏图最优
Prim	顶点贪心扩展（类似 Dijkstra）	O((V+E)log V)	稠密图最优
Boruvka	每轮每个连通块选最小出边	O(E log V)	可并行化

MST 的正确性基于割性质和圈性质。割性质（Cut Property）：对于任意割 (S, V\S)，图中权值最小的跨割边一定属于某棵 MST。圈性质（Cycle Property）：对于任意圈，图中权值最大的边一定不属于某棵 MST。Kruskal 利用圈性质（跳过形成圈的边），Prim 利用割性质（每次选择跨割的最小边）。

流网络

算法	思路	复杂度
Ford-Fulkerson	DFS 找增广路	O(E·f_max)，f_max 为最大流值
Edmonds-Karp	BFS 找最短增广路	O(VE²)
Dinic	BFS 分层 + DFS 多路增广 + 当前弧优化	O(V²E) 一般，O(min(V²/³, E¹/²)·E) 单位容量
Push-Relabel	顶点高度标号 + 超额流推送	O(V²√E)

最大流-最小割定理是图论中最重要的对偶性定理之一：网络中最大流的值等于最小割的容量。该定理的本质等价于线性规划的对偶性——最大流问题与最小割问题构成一对原始-对偶线性规划。

二分图匹配

将二分图匹配转化为最大流：源点→左侧所有节点（容量 1），左侧→右侧（按原始边，容量 1），右侧所有节点→汇点（容量 1）。最大流值 = 最大匹配数。

匈牙利算法专门针对二分图最大匹配优化——本质上是 DFS 寻找增广路并反转路径上边的匹配状态，复杂度 O(VE)。

3.2 字符串算法

KMP（Knuth-Morris-Pratt）

核心是 LPS（Longest Prefix Suffix）数组——lps[i] 表示模式串 P[0..i] 中最长相等前后缀的长度。匹配失败时利用 lps 跳过已匹配部分。

int[] buildLPS(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    int len = 0, i = 1;
    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1];  // 递归回退
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

其他字符串算法：Z 算法（O(n) 计算每个位置与字符串前缀的最长公共前缀长度，用于模式匹配和边界检测）、Manacher 算法（O(n) 找字符串的最长回文子串，核心是用对称性减少重复计算）、Rabin-Karp 滚动哈希（使用滑动窗口哈希值 O(1) 更新，双模哈希防止碰撞）、Aho-Corasick 自动机（Trie + 失败指针 = 多模式匹配 O(n + m) 经典解法）、后缀自动机 SAM（有向无环图表示所有子串，解决最长公共子串等问题）。

3.3 数学算法

数论：埃式筛（O(n log log n)），线性筛（欧拉筛 O(n)，每个合数只被其最小质因子筛掉），快速幂（a^b mod m 用二进制拆分，O(log b)），扩展欧几里得（求 ax + by = gcd(a, b) 的一组整数解，用于求模逆元），中国剩余定理 CRT（合并多个同余方程）。

组合数学：预处理阶乘和逆元 O(n) 后 O(1) 求组合数 C(n, k)。卡特兰数（出栈序列、合法括号、二叉树计数）。

线性代数：高斯消元 O(n³) 解线性方程组和求矩阵的逆。快速傅里叶变换 FFT（多项式乘法 O(n log n)，需要复数运算）和 NTT（数论变换，用原根代替单位复根，避免浮点误差）。

---

四、学习路径与资源

4.1 三阶段学习

阶段一（基础期，3-6 月）：数组、链表、栈、队列、哈希表 → 排序（快排/归并/堆排）→ 二分查找 → BFS/DFS → 树的前中后序遍历。刷题量 150-200 道，以 LeetCode 简单和中等为主。核心目标是建立数据结构和算法的直觉。

阶段二（进阶期，6-12 月）：动态规划（线性/背包/区间）→ 图论（最短路径/MST/拓扑排序）→ 并查集 → 单调栈/单调队列 → 滑动窗口 → 前缀和/差分。刷题量 300-500 道，以 LeetCode 中等为主，适度 Hard。

阶段三（精通期，1-2 年）：线段树/树状数组 → 字符串匹配算法 → 流网络 → 状态压缩 DP → 数位 DP → 后缀数组 → 莫队算法 → 树链剖分 → 竞赛级专题。刷题 500-800 道，参加 Codeforces 和 AtCoder 比赛。

4.2 刷题策略

五遍刷题法：

1. 第一遍：独立思考不超过 30 分钟，做不出来看题解，理解思路后手写实现
2. 第二遍：第二天重新独立实现，不参考题解
3. 第三遍：一周后复习，写出最优解
4. 第四遍：一个月后限时完成（1.5x 速度）
5. 第五遍：面试前集中复习，能口述所有关键步骤

分类刷 vs 随机刷：初学阶段按分类刷（如集中练习滑动窗口），熟练后按随机刷（模拟面试）。分类刷建立模式识别，随机刷训练问题转换。

4.3 推荐资源

类别	资源
在线评测	LeetCode（面试导向）、Codeforces（竞赛风格）、AtCoder（日本，题目精美）、洛谷（国内竞赛社区）
教材	《算法导论》CLRS（理论圣经）、《算法》Sedgewick（Java 实现）、《挑战程序设计竞赛》（竞赛入门）、《算法竞赛进阶指南》（国内竞赛必读）
工具	USFCA 算法可视化、VisuAlgo、Algorithm Visualizer
社区	LeetCode 讨论区、Codeforces 博客、r/algorithms、ACWing

---

面试常考问题

Q1：排序算法的稳定性有什么实际意义？

稳定性保证等值元素的相对顺序不变。实际场景：先按姓名排序，再按成绩排序——如果排序稳定，相同成绩的记录仍保持姓名字典序。Java 的 Arrays.sort() 对基本类型使用双轴快排（不稳定，性能优先），对对象类型使用 TimSort（稳定）。Android 继承此行为。

Q2：什么时候用线段树，什么时候用树状数组？

树状数组代码极短（~10 行），能用树状数组的场景优先用它。但树状数组只能维护可减的运算（和、异或），区间最值不能用树状数组（因为 max/min 不可逆——不能通过 sum(r)-sum(l-1) 推导）。线段树可以维护任意结合律运算（和、最值、矩阵乘），且支持区间更新（懒标记）。

Q3：递归改迭代的通用方法？

三种方法：(1) 手动模拟栈——将递归调用的局部状态（参数、局部变量）压入显式栈中，循环弹出处理。(2) 尾递归优化——如果递归调用是函数的最后一个操作（返回递归调用的结果），编译器/解释器可以直接将递归栈帧复用，不增加调用栈深度。(3) 动态规划——DP 通常将递归的自顶向下记忆化搜索改为自底向上的迭代填表，消除递归开销。

Q4：并查集的时间复杂度为什么是接近 O(1) 的？

仅路径压缩给出 O(log n) 摊还。路径压缩 + 按秩合并给出 O(α(n)) 摊还，其中 α(n) 是阿克曼函数的反函数。α(n) 增长极慢——对任何可观测的 n（n < 2^2^2^65536），α(n) ≤ 5。实际使用中等价于常数时间。证明依赖 Ackermann 函数的层级结构——并查集操作的摊还代价可以按 Ackermann 函数的逆”分层”，每层仅有有限次操作。

Q5：如何系统地准备算法面试？

三步走：(1) 先过一遍知识体系（本文结构），确保每个专题的模板代码能盲写。(2) 按专题刷 LeetCode Top 100 + 剑指 Offer，培养问题→模板的映射直觉。(3) 模拟面试——随机抽取 Medium 题，30 分钟内完成。核心是培养”看一眼题就知道什么数据结构/算法”的直觉——这需要足够的题量积累（200+ 题是门槛）。