算法图解

01基础数据结构与二分

二分不是「背下来的模板」，而是「每次砍掉一半候选区间」这个动作。

二分查找：为什么是 log n

在一百万个数里找一个，最多问 20 次——因为 2²⁰ ≈ 104 万。每问一次，候选区间就减半，这就是全部的秘密。

三个边界最容易写错，记住这三句就够了：

• 循环条件写 lo <= hi，因为区间是闭区间 [lo, hi]。
• 更新写 lo = mid + 1 / hi = mid - 1，因为 mid 已经看过了。
• 取中写 lo + (hi - lo) / 2，避免 lo+hi 溢出。

// C++
int lower_bound(const vector<int>& a, int x) {
  int lo = 0, hi = (int)a.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < x) lo = mid + 1;
    else hi = mid - 1;
  }
  return lo;   // 第一个 >= x 的位置
}

栈与队列：两种「顺序」

链表：为什么要「哑结点」

删除头结点是一个特例：没有前驱。加一个不存数据的哑结点放在最前面，头结点就有了前驱，特例消失——这是链表题少写一半 if 的诀窍。

// Python：删除值等于 x 的结点
dummy = ListNode(0, head)
prev = dummy
while prev.next:
    if prev.next.val == x: prev.next = prev.next.next
    else: prev = prev.next
return dummy.next

02排序与查找

排序算法值得学的只有三件事：怎么分区、怎么合并、什么时候别排序。

快速排序的分区：一次扫描做完的事

选最后一个元素做基准。用一个指针 i 表示「小于基准的区域到哪了」，扫一遍，比基准小的都换到前面去。扫完之后把基准换到 i 的位置——它左边的都小，右边的都大，且位置已经确定。

// Lomuto 分区
int partition(vector<int>& a, int lo, int hi) {
  int pivot = a[hi], i = lo;
  for (int j = lo; j < hi; ++j)
    if (a[j] < pivot) swap(a[i++], a[j]);
  swap(a[i], a[hi]);
  return i;
}

归并排序：稳定，且能数逆序对

分到只剩一个元素（天然有序），再两两合并。合并时如果右边先出，说明左边剩下的都比它大——这一步顺手就能统计逆序对数量，这是快排做不到的。

堆：只要前 k 个，不用全排

求「最大的 k 个」用大小为 k 的小顶堆：新元素比堆顶大就换掉堆顶。复杂度 O(n log k)，比全排的 O(n log n) 省——数据量大而 k 小的时候差别明显。

03动态规划与贪心

动态规划不是「套公式」，是「把重复的子问题答案存下来」。想清楚三件事：状态是什么、怎么转移、边界在哪。

0/1 背包：一张表就是全部答案

dp[i][c] = 只考虑前 i 件物品、容量 c 时能装的最大价值。每件物品只有两个选择：不拿（继承上一行）或拿（上一行容量减重 + 价值）。

// 一维滚动数组，注意容量要倒着遍历
vector<int> dp(C + 1, 0);
for (int i = 0; i < n; ++i)
  for (int c = C; c >= w[i]; --c)
    dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
return dp[C];

贪心什么时候是对的

贪心只做当前最优选择，不回头。它对的前提是最优子结构 + 贪心选择性质：局部最优能推出全局最优。区间调度（按结束时间排）满足；0/1 背包按「性价比」贪心就不满足——反例：容量 10，物品 (重 6 值 10) 和 (重 5 值 9) 加 (重 5 值 9)。

状态设计的四个常见维度

• 位置：走到第 i 个 / 第 i 行第 j 列。
• 容量或剩余：背包剩余空间、还剩几次操作。
• 状态机：手里有没有股票、处于第几个阶段（买 / 冷冻 / 卖）。
• 集合：已经访问过哪些点（状压 DP，n ≤ 20 时可用）。

04图论与搜索

图的题只有两种：要么「走一遍」（BFS/DFS），要么「算最短路」（Dijkstra/Floyd）。

BFS：一层一层地扩散

队列里放「待访问的节点」。每次取出一个，把它的邻居里没访问过的加进队列。因为先进先出，所以先被加进来的（离起点更近的）先被处理——这就是「最短步数」的由来。

// 多源 BFS：把所有源点先入队
queue<int> q;
for (int s : sources) { dist[s] = 0; q.push(s); }
while (!q.empty()) {
  int u = q.front(); q.pop();
  for (int v : g[u])
    if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
}

DFS 与回溯：一条路走到黑

DFS 用递归或栈，适合「问是否存在」「枚举所有方案」。回溯 = DFS + 撤销选择，模板只有四步：做选择 → 递归 → 撤销 → 剪枝。

并查集：只关心「是不是一伙的」

两个操作：find（找根）、union（合并）。路径压缩 + 按秩合并后，单次操作接近 O(1)。连通性问题、Kruskal 求最小生成树都用它。

parent[i] = i;
int find(int x){ return parent[x]==x ? x : parent[x]=find(parent[x]); }
void uni(int a,int b){ parent[find(a)] = find(b); }

Dijkstra：为什么不能有负权

Dijkstra 的核心假设是「一旦一个点被取出，它的最短路就定了」。有负权时，后面可能通过一条负边把已经确定的距离改小——假设崩塌。所以它只适用于非负权图。

05字符串与数学

字符串匹配的关键不是「比对」，而是「失配时别从头再来」。

KMP：把「已经匹配的前缀」变成跳转表

暴力匹配在失配时把模式串整体右移一位，前面的比较全部浪费。KMP 观察到：失配位置之前的那段文本我们已经知道内容了，如果模式串自己有个前缀等于后缀，就可以直接跳到那里继续比。

// 前缀表：next[i] = 前 i 个字符里最长相等前后缀长度
vector<int> build(const string& p) {
  vector<int> nxt(p.size() + 1, 0);
  for (int i = 1, k = 0; i < (int)p.size(); ++i) {
    while (k && p[i] != p[k]) k = nxt[k];
    if (p[i] == p[k]) ++k;
    nxt[i + 1] = k;
  }
  return nxt;
}

哈希：O(1) 的代价是冲突

哈希表把键映射到桶。桶少了冲突多，桶多了浪费内存——负载因子（元素数 / 桶数）就是那个旋钮，一般超过 0.75 就扩容。

两种冲突解法：

• 链地址法：每个桶挂一条链表（或红黑树）。实现简单，删除方便，Java 的 HashMap 就这么做。
• 开放寻址：冲突了就往后找空位。缓存友好，但删除要打墓碑标记，否则会把查找链断掉。

数学：几道必须会的

• 快速幂：a¹³ = a⁸ · a⁴ · a¹，二进制拆指数，O(log n)。
• gcd：辗转相除，O(log min(a,b))。
• 筛法：埃氏筛 O(n log log n) 求 n 以内所有素数。
• 逆元：模意义下的除法要乘逆元，a^(p−2) mod p（p 为素数）。