🚀 面试算法 (Coding Interview & CP Wiki)
欢迎查阅 面试算法！这是一个系统化、竞赛级的高频算法与数据结构知识库。
本项目专为国内外一线互联网大厂技术面试、LeetCode 周赛高分冲刺以及各类算法竞赛（ICPC / CCPC / Codeforces / AtCoder）量身打造，涵盖 65 个核心技术模块 与 300+ 道精选高频真题与系统设计实战。
💡 核心特色与设计哲学
为什么选择本知识库？
- 深入数学底层，拒绝死记硬背：不仅提供代码模板，更给出严谨的数学推导与正确性证明（如树状数组二进制划分定理、树的直径若尔当定理、卡特兰数反射原理、Fisher-Yates 洗牌望远消去证明等）；
- 现代化 C++ 工业级标准：全库代码采用现代 C++ 标准实现，注重内存局部性、Cache 友好性与位运算常数优化；
- 折叠题解，沉浸式实战思考：全站 290+ 道精选题均配有
??? tip "提示" 可折叠思路拆解，支持先自主思考再对照查阅，覆盖最优时间与空间复杂度。
🗺️ 全站知识图谱与核心模块索引
mindmap
root((面试算法知识库))
基础与通用工具
C++ 核心常识与底层陷阱
算法复杂度与主定理
计算复杂性理论 P/NP/NPC
二分与三分搜索
分治算法与平面最近点对
搜索算法与六大剪枝
排序与快速选择
MEX与摩尔投票
Two Sum 与 K-Sum
接雨水专题
括号序列专题
贪心算法专题
核心理论与证明范式
区间贪心与覆盖模型
排序不等式与全序比较
序列推进与双向贪心
反悔贪心与优先队列
核心数据结构
并查集与带权DSU
树状数组 BIT
线段树 Segment Tree
ST 表 RMQ
堆与对顶堆
平衡树 AVL/红黑树/FHQ-Treap
图论核心算法
最短路 Dijkstra/Floyd
差分约束系统
最小生成树 Kruskal/Prim
最近公共祖先 LCA
树的直径 Tree Diameter
树链剖分 HLD
拓扑排序与分层
强连通分量与缩点
2-SAT 可满足性
网络流与费用流
动态规划 DP
经典背包模型
序列与线性 DP
区间与环形 DP
树形与换根 DP
状态压缩 DP
数位记忆化 DP
数学与数论
快速幂与线性筛
组合数学与斯特林数
概率期望与随机化算法
线性代数与线性基
博弈论与SG函数
字符串算法
KMP 与 Border 树
Z 算法 ExKMP
AC 自动机多模式匹配
多项式双哈希
后缀数组 SA
计算几何专题
几何基础与向量代数
二维凸包与旋转卡壳
几何扫描线与矩形面积
极角排序与距离度量
系统设计专题
四步法与容量估算
L4与L7负载均衡
一致性哈希环
缓存穿透击穿雪崩
分库分表与LSM树
消息队列与削峰
雪花算法与分布式锁
短链系统设计
高并发限流器
Feed流与时间线
📚 快速导航 (Quick Navigation)
1. 基础与通用工具 (Basic & Foundations)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| 缺省源与常用宏 |
竞赛快速 I/O、现代 C++ 实用宏、本地调试器 |
— |
| 算法面试 C++ 核心常识 |
STL 容器扩容/失效、自定义 Hash 与 unordered_set、严格弱序、递归 Lambda、SSO与 string_view、UB防御 |
— |
| 算法复杂度与均摊分析 |
渐进记号、主定理 (Master Theorem)、均摊分析三大方法（聚合/记账/势能）、数据规模预期复杂度法则 |
— |
| 计算复杂性理论 (P / NP / NPC / NP-Hard) |
判定问题与最优化、P/NP定义（非确定机与多项式验证器）、Karp 多项式归约、Cook-Levin 定理、21个经典NPC、伪多项式时间与强弱NP-Hard、工程近似与启发式策略 |
— |
| 二分与三分查找 |
整数与浮点二分、单峰函数三分、二分答案单调判定 |
LC 33, LC 34, LC 162, LC 410, LC 719, LC 2040 |
| 分治算法与主定理 |
主定理三类情形推导、归并排序求逆序对、平面最近点对 \(\mathcal{O}(n \log n)\) 鸽巢原理证明 |
LC 23, LC 315, LC 4, LC 240, LC 932 |
| 搜索算法与剪枝策略 |
回溯 DFS、六大剪枝（可行/最优/记忆/顺序/对称/估价）、双向 BFS 较小端扩展、A* 启发式搜索 |
LC 127, LC 126, LC 773, LC 752, LC 51, LC 37 |
| 常用排序与快速选择 |
快速排序三向切分、快速选择期望 \(\mathcal{O}(n)\)、置换环最小交换次数 |
LC 215, LC 75, LC 912, LC 765 |
| MEX 理论与高阶维护 |
最小未出现值定义、值域桶统计、同余类贪心构造 |
LC 2598, LC 41, LC 2009 |
| 摩尔投票算法 |
绝对众数对消法、广义 \(k\) 候选人抵消、线段树结合 |
LC 169, LC 229, LC 1157, LC 961 |
| Two Sum 与 K-Sum 变种 |
双指针、哈希表、折半查找 (Meet-in-the-Middle) |
LC 1, LC 15, LC 18, LC 167, LC 454 |
| 接雨水专题 |
一维三大解法（前后缀/双指针/单调栈）、二维最小堆收缩 |
LC 42, LC 407 |
| 括号序列专题 |
前缀和 Dyck 路径、卡特兰数、三大最长有效解法、线段树合并 |
LC 20, LC 22, LC 32, LC 678, LC 856 |
2. 贪心算法专题 (Greedy Algorithms)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| 核心理论与证明范式 |
贪心选择性质、最优子结构、微扰法/邻项交换、保持前沿法、拟阵理论与自检四问 |
— |
| 区间贪心与覆盖模型 |
不相交区间最大化、最少点覆盖、区间合并、区间完全覆盖、划分字母区间、区间分组 |
LC 435, LC 452, LC 56, LC 57, LC 763, LC 1024, LC 1326, LC 2406, LC 646 |
| 排序不等式与全序比较 |
排序不等式数学证明、微扰推导自定义比较器、拼接最大数传递性实数映射证明、降序插入、最大交换、Smith's Rule |
LC 179, LC 406, LC 621, LC 670, LC 767, LC 1005, LC 1405, LC 3273, LC 2136, LC 1665 |
| 序列推进与双向贪心 |
动态最远覆盖边界推进、分层 BFS 双指针跳跃、折线最低点法、左右规则解耦双向扫描、单调栈字符去重 |
LC 55, LC 45, LC 134, LC 135, LC 316, LC 402, LC 376, LC 738, LC 860 |
| 反悔贪心专题 (优先队列) |
“先选再说，遇优则换”撤销机制、截止时间约束作业调度、路过暂存备选缺油反悔补油、买卖股票反悔交易 |
LC 630, LC 871, LC 1353, LC 1642, LC 2434, LC 2813 |
3. 核心数据结构 (Data Structures)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| 并查集 (DSU) |
路径压缩与按秩合并、带权并查集、置换环与连通块 |
LC 200, LC 547, LC 684, LC 990, LC 827 |
| 树状数组 (BIT) |
lowbit 划分数学证明、\(\mathcal{O}(\log n)\) 二进制倍增找第 \(K\) 小、二维树状数组 |
LC 307, LC 315, LC 493, LC 1649, LC 2179 |
| 线段树 (Segment Tree) |
延迟标记 (Lazy Tag)、动态开点、线段树上二分 |
LC 307, LC 218, LC 715, LC 2286 |
| ST 表 (Sparse Table) |
静态区间可重复贡献 RMQ 查询、\(\mathcal{O}(1)\) 区间最值、GCD 与按位与 |
LC 239, LC 3171, LC 2447, LC 1521 |
| 堆与优先队列 |
二叉堆实现、对顶堆动态中位数、反悔贪心、多路归并 |
LC 215, LC 295, LC 23, LC 1675, LC 632, LC 871 |
| 平衡二叉树 (AVL) |
四种基本旋转 (LL/RR/LR/RL)、严格高度平衡、排名与邻域查询 |
LC 1382, LC 327, LC 220 |
| 红黑树 (Red-Black Tree) |
黑色高度不变量、左倾红黑树 (LLRB)、GCC PBDS 库用法 |
— |
| 无旋 Treap (FHQ-Treap) |
基于分裂 (Split) 与合并 (Merge) 的区间翻转、名次树与中位数 |
LC 480, LC 218, LC 715 |
4. 图论核心算法 (Graph Theory)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| 最短路算法 |
Dijkstra 堆优化、SPFA/Bellman-Ford 判负环、Floyd-Warshall、分层图 |
LC 743, LC 787, LC 1334, LC 1514, LC 1976 |
| 差分约束系统 |
不等式三角不等式图论映射、SPFA 判负环、超级源点、前缀和区间选点模型、DAG 偏序 |
LC 2589, LC 2392, LC 2050, LC 785 |
| 最小生成树 (MST) |
Kruskal 贪心、Prim 算法、超级源点、双图并查集与关键边判定 |
LC 1584, LC 1168, LC 1489, LC 1579 |
| 最近公共祖先 (LCA) |
树上倍增法、树上点/边差分、LCA 路径分解 |
LC 236, LC 235, LC 1483, LC 1123, LC 2096 |
| 树的直径 (Tree Diameter) |
两次 BFS/DFS 贪心证明、树形 DP 最长次长链、树的中心与若尔当定理、两树合并最小直径 |
LC 543, LC 124, LC 1245, LC 310, LC 3203 |
| 树链剖分 (HLD) |
重链剖分将树上路径映射为 \(\mathcal{O}(\log n)\) 段 DFS 连续区间配合线段树 |
LC 236, LC 2421 |
| 拓扑排序 (Topological Sort) |
Kahn 算法入度队列、DAG 有向环判定、DAG 状态机路径 DP、双层分层拓扑 |
LC 207, LC 210, LC 269, LC 1857, LC 1203 |
| 欧拉路径与欧拉回路 |
Hierholzer 算法当前弧优化、有向/无向图度数守恒充要条件、De Bruijn 序列 |
LC 332, LC 753, LC 2097 |
| 哈密顿回路与旅行商问题 |
状压 DP 求解 TSP、集合位运算状态机、全遍历最短路 |
LC 847, LC 943, LC 980 |
| 割点与桥 (Tarjan) |
DFS 树回退边、dfn 与 low 数组判定定理、网格割点连通性 |
LC 1192, LC 1568, LC 924, LC 928 |
| 强连通分量 (Kosaraju) |
正反图两次 DFS、缩点构建有向无环图 (DAG)、基环树环长讨论 |
LC 2360, LC 2127, LC 802 |
| 2-SAT 问题 |
析取向蕴涵图建模、Tarjan SCC 缩点判自相矛盾、逆拓扑序构造合法解、二分图染色退化关系 |
LC 785, LC 886, LC 1601, 洛谷 P4782 |
| 网络流 (Dinic) |
残量网络、分层图 BFS + 阻塞流 DFS 当前弧优化、最大流最小割定理 |
LC 1349 |
| 费用流 (MCMF) |
连续最短路 SPFA 与 Primal-Dual (Johnson 势能 + Dijkstra) |
— |
| 二分图最大匹配 |
增广路定理、匈牙利算法、网格黑白染色骨牌覆盖与最大独立集 |
LC 1820, LCP 04, LC 1349 |
5. 动态规划专题 (Dynamic Programming)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| 经典背包问题 |
0-1、完全、多重（二进制拆分/单调队列）、分组背包、二维费用与收益下界 |
LC 416, LC 494, LC 322, LC 518, LC 879, LC 1449 |
| 线性 DP 与序列模型 |
LIS（贪心二分）、LCS、编辑距离、Kadane 最大子数组、公差哈希与单调队列优化 |
LC 300, LC 354, LC 1143, LC 72, LC 188, LC 446, LC 1425 |
| 区间动态规划 |
长度 \(len\) 阶段递推、环形破环成链、戳气球逆向分治、区间染色与消除（蹭打印/外部升维）、四边形不等式优化 |
LC 312, LC 664, LC 546, LC 730, LC 1000 |
| 树形 DP 与换根 DP |
树上最大独立集、树的直径、两次 DFS 换根 DP 范式、树上状态机与最小支配集 |
LC 337, LC 124, LC 834, LC 968, LC 310 |
| 状态压缩动态规划 |
集合位运算、子集遍历 sub = (sub - 1) & mask、两两匹配与子集背包划分 |
LC 847, LC 943, LC 698, LC 1655, LC 1799, LC 1986 |
| 数位记忆化 DP |
前缀差分化简、工业级通用记忆化搜索模板 (is_limit / is_num) |
LC 2719, LC 233, LC 600, LC 2376, LC 902 |
6. 数学与数论 (Mathematics)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| 数论基础 |
快速幂、扩展欧几里得 (exGCD)、线性求逆元、欧拉线性筛、LCM 二分与等差因数分解 |
LC 204, LC 372, LC 878, LC 829, LC 2523, LC 1015 |
| 组合数学 |
阶乘逆元组合数、卢卡斯定理 (Lucas)、第一类与第二类斯特林数、多重集合排列 |
LC 62, LC 1359, LC 920, LC 1866, LC 1643, LC 2514 |
| 概率论与期望 |
期望线性性、全概率公式、Fisher-Yates 原地洗牌、蓄水池抽样、概率期望与硬币背包 DP |
LC 688, LC 808, LC 837, LC 382, LC 1230, LC 398 |
| 线性代数与线性基 |
矩阵乘法、矩阵快速幂加速转移、高斯-约旦消元法求线性方程组、异或线性基维护 |
LC 509, LC 1137, LC 2851, LC 70 |
| 博弈论 (Game Theory) |
公平组合游戏 (ICG)、P/N 局势推导、巴什博弈、威佐夫博弈、斐波那契博弈、尼姆博弈与 SG 定理 |
LC 292, LC 877, LC 1140, LC 913, LC 1406 |
7. 字符串算法 (String Algorithms)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| KMP 与前缀函数 |
前缀函数 \(\pi\) 数组、Border 树链、最小周期性引理、KMP 自动机、差分趋势匹配 |
LC 28, LC 459, LC 1392, LC 214, LC 686, LC 3036 |
| Z 算法 (扩展 KMP) |
Z 函数线性匹配、前缀与后缀最长公共前缀 (LCP)、周期判定、最长回文前缀 |
LC 2223, LC 3031, LC 3045, LC 214 |
| AC 自动机 (Aho-Corasick) |
多模式串匹配、Trie 树、BFS Fail 指针失配跳转、Trie 图确定性转移优化、AC-DP 文本串安全匹配 |
LC 1032, LC 2781, LC 1408 |
| 字符串哈希 |
多项式滚动哈希、双哈希防 Hack 冲突设计、倒序滑动窗口模逆元规避、双哈希最长公共路径 |
LC 187, LC 1044, LC 1062, LC 2156, LC 1316, LC 1923 |
| 后缀数组 (SA) |
倍增法与基数排序、Kasai 算法求高度数组 \(lcp\)、RMQ 快速 LCP 查询、不同子串计数公式 |
LC 1163, LC 1044, LC 1754, LC 1698, LC 1062 |
8. 计算几何 (Computational Geometry)
| 模块 |
核心考点与理论 |
推荐代表真题 |
| 几何基础与向量代数 |
浮点数 eps 防抖、点积（投影/正交/夹角）、叉积（有向面积/左右侧CCW）、线段相交快速排斥+跨立实验、点在多边形内射线法 |
LC 1232, LC 469, LC 223 |
| 二维凸包与旋转卡壳 |
Andrew 算法水平序单调栈、边界共线点处理技巧（叉积 < 0 与 used 标记）、旋转卡壳对踵点求凸包直径 |
LC 587 |
| 几何扫描线与矩形面积 |
事件驱动模型、X坐标离散化+垂直扫描线、线段树维护Y轴覆盖长度、完美矩形面积守恒与顶点异或消除 |
LC 850, LC 391 |
| 极角排序与距离度量 |
atan2 浮点排序与叉积象限精确排序、斜率有理数 \(\gcd\) 约分防溢出、曼哈顿与切比雪夫距离等价旋转变换、矩形对角线哈希 |
LC 149, LC 1610, LC 963, LC 1266 |
9. 系统设计专题 (System Design)
| 模块 |
核心考点与理论 |
推荐代表场景 / 工业实践 |
| 系统设计方法论与容量估算 |
四步面试法、QPS/带宽/存储/内存容量估算、必须牢记的延迟数字、CAP 定理、PACELC 模型、BASE 理论与一致性模型阶梯 |
大厂系统设计第一道门、容量规划 |
| 核心基础设施与分布式组件 |
L4/L7 负载均衡、一致性哈希与虚拟节点、Cache-Aside/Write-Through/Write-Back、缓存三大灾难防御、数据库分库分表、B+ Tree vs LSM-Tree、消息队列解耦与削峰、雪花算法 Snowflake、Redis 分布式锁 Redlock |
分布式中间件选型、系统高可用改造 |
| 短链系统设计 (TinyURL) |
读写比 100:1 容量规划、Base62 进制转换 vs 哈希截断防碰撞、HTTP 301 vs 302 重定向权衡、short_code 分片与多级缓存 |
TinyURL, Bitly, 营销短链 |
| 高并发限流器 (Rate Limiter) |
五大限流算法（固定窗口/滑动日志/滑动计数器/令牌桶/漏桶）、Redis + Lua 脚本原子执行、HTTP 429 协议头标准、Fail-Open 容灾降级 |
API 网关防护、微服务防刷、开放平台 |
| Feed 流与时间线系统 |
推模式 (Fan-out on write) vs 拉模式 (Fan-out on read) vs 混合推拉模式、大 V 粉丝写放大应对、Redis ZSet 收件箱设计、游标分页 (Cursor-based) 杜绝重复与深分页 |
Twitter, 微博, 微信朋友圈, Instagram |
🎯 面试高效通关指引
为了帮助不同阶段的学习者快速定位重心，推荐按以下梯度进行专项攻坚：
- 第一阶段：基石掌握（面试必考）
- 熟练掌握双指针、二分查找、滑动窗口与哈希、栈与括号序列；
- 掌握单源最短路 Dijkstra 与 Kahn 拓扑排序；
- 掌握基础 0-1背包 与序列 线性 DP。
- 第二阶段：经典模型深化（周赛上分 / 中大厂高频）
- 并查集 的各种代数关系合并与置换环；
- 树形 DP 与全源换根 DP（如 LC 310, LC 834）；
- 前后缀分解与接雨水 及不可逆操作的聚合维护；
- 数位 DP 记忆化模板，做到一遍过。
- 第三阶段：拔高与进阶（竞赛与 Hard 绝杀）
- 树状数组倍增二分 与 线段树动态合并；
- 树链剖分 HLD 与 Tarjan 割点与桥；
- 概率与期望 DP 及 状态压缩 DP。