跳转至

🚀 面试算法 (Coding Interview & CP Wiki)

欢迎查阅 面试算法！这是一个系统化、竞赛级的高频算法与数据结构知识库。

本项目专为国内外一线互联网大厂技术面试、LeetCode 周赛高分冲刺以及各类算法竞赛（ICPC / CCPC / Codeforces / AtCoder）量身打造，涵盖 44 个核心技术模块 与 178+ 道精选高频真题详解。

💡 核心特色与设计哲学

为什么选择本知识库？

  • 深入数学底层，拒绝死记硬背：不仅提供代码模板，更给出严谨的数学推导与正确性证明（如树状数组二进制划分定理、树的直径若尔当定理、卡特兰数反射原理、Fisher-Yates 洗牌望远消去证明等）；
  • 现代化 C++ 工业级标准：全库代码采用现代 C++ 标准实现，注重内存局部性、Cache 友好性与位运算常数优化；
  • 折叠题解，沉浸式实战思考：全站 178+ 道精选题均配有 ??? tip "提示" 可折叠思路拆解，支持先自主思考再对照查阅，覆盖最优时间与空间复杂度。

🗺️ 全站知识图谱与核心模块索引

mindmap
  root((面试算法知识库))
    基础与通用工具
      二分与三分搜索
      排序与快速选择
      MEX与摩尔投票
      Two Sum 与 K-Sum
      接雨水专题
      括号序列专题
    核心数据结构
      并查集与带权DSU
      树状数组 BIT
      线段树 Segment Tree
      ST 表 RMQ
      堆与对顶堆
      平衡树 AVL/红黑树/FHQ-Treap
    图论核心算法
      最短路 Dijkstra/Floyd
      最小生成树 Kruskal/Prim
      最近公共祖先 LCA
      树的直径 Tree Diameter
      树链剖分 HLD
      拓扑排序与分层
      强连通分量与缩点
      网络流与费用流
    动态规划 DP
      经典背包模型
      序列与线性 DP
      区间与环形 DP
      树形与换根 DP
      状态压缩 DP
      数位记忆化 DP
    数学与数论
      快速幂与线性筛
      组合数学与斯特林数
      概率期望与随机化算法
    字符串算法
      KMP 与 Border 树
      Z 算法 ExKMP
      多项式双哈希
      后缀数组 SA

📚 快速导航 (Quick Navigation)

1. 基础与通用工具 (Basic & Foundations)

模块 核心考点与理论 推荐代表真题
缺省源与常用宏 竞赛快速 I/O、现代 C++ 实用宏、本地调试器 —
二分与三分查找 整数与浮点二分、单峰函数三分、二分答案单调判定 LC 33, LC 34, LC 162, LC 410, LC 875
常用排序与快速选择 快速排序三向切分、快速选择期望 \(\mathcal{O}(n)\)、置换环最小交换次数 LC 215, LC 75, LC 912, LC 765
MEX 理论与高阶维护 最小未出现值定义、值域桶统计、同余类贪心构造 LC 2598, LC 41, LC 2009
摩尔投票算法 绝对众数对消法、广义 \(k\) 候选人抵消、线段树结合 LC 169, LC 229
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. 核心数据结构 (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 215, LC 295, LC 23, LC 1675
平衡二叉树 (AVL) 四种基本旋转 (LL/RR/LR/RL)、严格高度平衡、排名与前驱后继 LC 1382
红黑树 (Red-Black Tree) 黑色高度不变量、左倾红黑树 (LLRB)、GCC PBDS 库用法 —
无旋 Treap (FHQ-Treap) 基于分裂 (Split) 与合并 (Merge) 的区间翻转与可持久化 LC 715

3. 图论核心算法 (Graph Theory)

模块 核心考点与理论 推荐代表真题
最短路算法 Dijkstra 堆优化、SPFA/Bellman-Ford 判负环、Floyd-Warshall、分层图 LC 743, LC 787, LC 1334, LC 1514, LC 1976
最小生成树 (MST) Kruskal 贪心与加权并查集、Prim 算法、超级虚拟源点建图 LC 1584, LC 1168, LC 1489
最近公共祖先 (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 算法当前弧优化、有向/无向图度数守恒充要条件 LC 332, LC 753
哈密顿回路与旅行商问题 状压 DP 求解 TSP、集合位运算状态机 LC 847, LC 943
割点与桥 (Tarjan) DFS 树回退边、dfn 与 low 数组判定定理、网格割点连通性 LC 1192, LC 1568, LC 924
强连通分量 (Kosaraju) 正反图两次 DFS、缩点构建有向无环图 (DAG) LC 1489
网络流 (Dinic) 残量网络、分层图 BFS + 阻塞流 DFS 当前弧优化、最大流最小割定理 LC 1349
费用流 (MCMF) 连续最短路 SPFA 与 Primal-Dual (Johnson 势能 + Dijkstra) —
二分图最大匹配 增广路定理、匈牙利算法与最大流转化建模 LC 1820

4. 动态规划专题 (Dynamic Programming)

模块 核心考点与理论 推荐代表真题
经典背包问题 0-1、完全、多重（二进制拆分/单调队列）、分组背包、空间滚动压缩 LC 416, LC 494, LC 322, LC 518, LC 474
线性 DP 与序列模型 LIS 最长上升子序列（贪心二分）、LCS、编辑距离、Kadane 最大子数组、股票多状态机 LC 300, LC 1143, LC 72, LC 53, LC 123
区间动态规划 长度 \(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、\(\mathcal{O}(3^n)\) 复杂度证明 LC 847, LC 943, LC 698, LC 1655, LC 1349
数位记忆化 DP 前缀差分化简、工业级通用记忆化搜索模板 (is_limit / is_num) LC 2719, LC 233, LC 600, LC 2376, LC 902

5. 数学与数论 (Mathematics)

模块 核心考点与理论 推荐代表真题
数论基础 快速幂、扩展欧几里得 (exGCD)、线性求逆元、欧拉函数与欧拉线性筛 LC 204, LC 372, LC 878, LC 829
组合数学 阶乘逆元组合数、卢卡斯定理 (Lucas)、第一类与第二类斯特林数 LC 62, LC 1359, LC 920, LC 1866
概率论与期望 期望线性性、全概率公式、Fisher-Yates 原地洗牌、蓄水池抽样、概率期望 DP LC 688, LC 808, LC 837, LC 382, LC 384

6. 字符串算法 (String Algorithms)

模块 核心考点与理论 推荐代表真题
KMP 与前缀函数 前缀函数 \(\pi\) 数组、Border 树链、最小周期性引理、KMP 自动机状态机 DP LC 28, LC 459, LC 1392, LC 214
Z 算法 (扩展 KMP) Z 函数线性匹配、前缀与后缀最长公共前缀 (LCP)、周期判定 LC 2223, LC 3031, LC 3045
字符串哈希 多项式滚动哈希、双哈希防 Hack 冲突设计、倒序滑动窗口模逆元规避 LC 187, LC 1044, LC 1062, LC 2156
后缀数组 (SA) 倍增法与基数排序、Kasai 算法求高度数组 \(lcp\)、RMQ 快速 LCP 查询 LC 1163, LC 1044, LC 1754

🎯 面试高效通关指引

为了帮助不同阶段的学习者快速定位重心，推荐按以下梯度进行专项攻坚：

  1. 第一阶段：基石掌握（面试必考）
  2. 熟练掌握双指针、二分查找、滑动窗口与哈希、栈与括号序列；
  3. 掌握单源最短路 Dijkstra 与 Kahn 拓扑排序；
  4. 掌握基础 0-1背包 与序列 线性 DP。
  5. 第二阶段：经典模型深化（周赛上分 / 中大厂高频）
  6. 并查集 的各种代数关系合并与置换环；
  7. 树形 DP 与全源换根 DP（如 LC 310, LC 834）；
  8. 前后缀分解与接雨水 及不可逆操作的聚合维护；
  9. 数位 DP 记忆化模板，做到一遍过。
  10. 第三阶段：拔高与进阶（竞赛与 Hard 绝杀）
  11. 树状数组倍增二分 与 线段树动态合并；
  12. 树链剖分 HLD 与 Tarjan 割点与桥；
  13. 概率与期望 DP 及 状态压缩 DP。

🌟 每周高阶精选题推荐