★ FEATURED ARTICLE 1. 先把“C常见算法”这四个字拆开看刚入行那几年我也在网上搜过一模一样的词翻出来一堆清单冒泡、快排、二分、KMP、Dijkstra……然后就没了。清单本身没错问题在于它把三层完全不同的东西混在一起讲学的人自然抓不住重点。后来带新人多了才慢慢想明白所谓“C常见算法”其实要分成四层来看每一层的练法和用途完全不同混着练只会浪费时间。第一层是 STL 现成算法也就是algorithm和numeric里那几十个函数。这一层不需要你手写需要你背得住、选得对比如什么时候用std::sort、什么时候用std::stable_sort、std::nth_element能解决什么问题。第二层是必须能手写的基础排序与查找冒泡、插入、选择、快排、归并、堆排、二分这些是面试和笔试的硬通货写不出来基本没得谈。第三层是字符串与图论KMP、字符串哈希、并查集、最短路、最小生成树、二分图匹配属于解决具体问题的工具。第四层是思维类算法贪心、回溯剪枝、动态规划、数论小算法这一层考的不是模板记忆而是把实际问题翻译成可计算模型的能力。这么分的好处是你练的时候心里有数第一层靠查文档和记忆第二层靠反复手写形成肌肉记忆第三层靠理解原理加模板化沉淀第四层靠大量做题积累“手感”。我见过太多人卡在第二层和第三层之间排序能背一到图论就懵根因就是没把层次分开试图用一个通用方法解决所有问题。这篇内容就按这四层往下走每一层都给能直接跑的代码、能耗时的细节以及我自己踩过的坑。适合刚学完 C 语法、准备系统补算法的人也适合工作几年、想把这部分知识重新捋顺的人。1.1 为什么“只会调 STL”迟早要还债先泼一盆冷水STL 非常好用但它的边界很明确。std::sort不保证稳定std::priority_queue默认是大顶堆std::find是线性查找这些如果记混了写出来的代码逻辑能跑通但结果不一定对。更关键的是面试和实际项目里的复杂问题往往是“用 STL 搭骨架 手写逻辑填肉”你不可能全程只调函数。举个最典型的例子求数组中第 K 大的元素很多人第一反应是sort完取下标时间复杂度 O(n log n)。但用std::nth_element平均 O(n) 就能搞定因为它内部是快排的 partition 思路只把第 K 个位置放对左右不排序。#include algorithm #include vector // 求第 k 大k 从 1 开始计数 int kthLargest(std::vectorint a, int k) { std::nth_element(a.begin(), a.begin() (k - 1), a.end(), std::greaterint()); return a[k - 1]; }这段代码短但背后是“你知不知道有这个东西”的差距。所以我一直建议第二层的手写功夫必须过一遍不是为了用而是为了在选 STL 的时候知道它内部大概在干什么。知道归并排序怎么合并你才会理解stable_sort为什么更慢知道堆的上浮下沉你才会明白priority_queue为什么不能随便遍历。1.2 一个可执行的练习顺序我把自己的练习顺序放在这里供参考。先花两天把三种 O(n²) 排序手写到不看资料也能写出来重点是边界条件然后用一周啃快排、归并、堆排要求能讲清楚平均复杂度和最坏情况的差异接着攻二分查找务必练到“闭区间和左闭右开两种写法都不出错”再进字符串和图论模板写在一个自己的template头文件里反复默写最后用两到三周专门刷贪心和 DP 的题。整个过程大概一个月到一个半月每天两小时节奏刚好不会因为跨度太长而前面忘了后面。提示模板不要复制别人的就完事一定要自己敲一遍、跑一组数据、故意改错一个符号看结果怎么变。这个过程花的时间远比多看十篇文章值。2. 基础排序三个 O(n²) 算法为什么还值得写我自己带过的实习生里十个有九个觉得冒泡排序“没技术含量不用学”。这话对了一半从工程角度看确实没人会在生产代码里写冒泡但换个角度冒泡的交换次数是一个非常有用的信号量。比如统计一个序列的逆序对数量级冒泡的交换次数就是逆序对数这在分析“数据有多乱”时很直接。所以这一节我不只给代码还会说清楚每个算法的“副产品”是什么。2.1 冒泡排序交换次数就是逆序对冒泡的核心是相邻比较、逆序交换每轮把当前未排序部分的最大值“冒”到末尾。加一个swapped标志可以在已经有序时提前退出这在近乎有序的数据上能把复杂度降到 O(n)。void bubbleSort(std::vectorint a) { int n static_castint(a.size()); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { std::swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 已经有序提前收工 } }注意内层循环的上界是n - 1 - i因为后 i 个元素已经是排好的最大值。这个细节写错的话程序不会崩只是多做无用功但面试官一眼就能看出你对算法的理解停留在抄代码的层面。另外swapped标志放在内层还是外层也是有讲究的必须是每轮开始前置为 false否则提前退出永远不会触发。2.2 插入排序小数组和近乎有序数据的王者插入排序的逻辑是“把当前元素往前面已经有序的部分里插”实现起来有三种常见写法边比较边移动、先找位置再腾挪、用std::rotate。生产里最常用的是第一种。void insertionSort(std::vectorint a) { for (int i 1; i static_castint(a.size()); i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; --j; } a[j 1] key; } }插入排序真正的价值在于它是很多工业级排序的底层收尾手段。数组长度小于某个阈值通常是 16 或 32时插入排序的常数极小比继续递归快排还快。这就是为什么成熟的sort实现里都是“快排递归到小区间 插入排序收尾”的混合策略。理解这一点你再看std::sort的源码就不会觉得突兀。2.3 选择排序交换次数最少的那一个选择排序每轮从后面找最小值和当前位置交换。它的比较次数固定是 n(n-1)/2不会因为数据有序而减少但交换次数最多只有 n-1 次。这个特性在“交换代价远大于比较代价”的场景下反而有用比如元素是大结构体移动一次开销很大。void selectionSort(std::vectorint a) { int n static_castint(a.size()); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) minIdx j; } if (minIdx ! i) std::swap(a[i], a[minIdx]); } }这里加if (minIdx ! i)是个小习惯能省掉一次自交换。虽然std::swap对自己交换是安全的但白跑一趟总是没必要。2.4 三个算法的横向对比算法平均时间最坏时间空间稳定性特点冒泡排序O(n²)O(n²)O(1)稳定交换次数等于逆序对数可提前退出插入排序O(n²)O(n²)O(1)稳定小数组极快近乎有序时接近 O(n)选择排序O(n²)O(n²)O(1)不稳定交换次数最少比较次数固定稳定性这一列经常被忽略但实际影响很大。所谓稳定就是相等元素排序后相对顺序不变。如果你按“分数”排序一批学生希望同分的学生保持原来的学号顺序那选择排序就不能用因为它会把后面的同分元素换到前面来。这个坑我在做报表导出的时候真踩过排查了半天才发现是排序算法不稳定导致的。3. 高级排序快排、归并、堆排是三条不同的路如果说基础排序是“会写就行”那这三个是“必须理解为什么”。它们代表了三种完全不同的设计哲学快排是分治加原地分区归并是分治加外部空间合并堆排是利用数组模拟完全二叉树。三条路的适用场景差异很大选错了性能差一个数量级都正常。3.1 快速排序分区写对一切好说快排最核心的不是递归是 partition。写快排出错九成出在分区边界上。我推荐先掌握“左右双指针向中间夹”的写法也就是 Hoare 分区的变体它对重复元素多的数据表现更均匀。void quickSort(std::vectorint a, int l, int r) { if (l r) return; int i l, j r; int pivot a[l (r - l) / 2]; // 取中间值避免有序数据退化 while (i j) { while (a[i] pivot) i; while (a[j] pivot) --j; if (i j) { std::swap(a[i], a[j]); i; --j; } } quickSort(a, l, j); quickSort(a, i, r); }有两个细节值得展开。第一pivot 取中间下标而不是第一个元素是因为如果数据本身已经有序取首元素会让分区极度不平衡递归深度退化成 O(n)栈空间直接爆掉。第二两个递归调用的区间是[l, j]和[i, r]不是[l, i-1]和[i1, r]因为循环结束后j ii和j之间的元素已经处理完了。这个写法看起来别扭但能在有大量重复元素时保持性能。注意递归版快排在数据量很大且分布恶劣时可能栈溢出。工程上一般改成“先递归较小的一半较大的一半用 while 循环处理”或者直接切到迭代加显式栈。这个优化叫尾递归消除不难但能省掉很多莫名其妙的崩溃。3.2 归并排序稳定、可并行、能解决逆序对归并的特点是必须额外 O(n) 空间换来的是稳定的 O(n log n)任何数据分布都不退化。它的合并过程本身很有价值因为“合并两个有序序列”这个操作可以脱离排序单独用比如合并两个有序链表、求逆序对、做外排序。void mergeSort(std::vectorint a, std::vectorint tmp, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(a, tmp, l, mid); mergeSort(a, tmp, mid 1, r); int i l, j mid 1, k l; while (i mid j r) tmp[k] (a[i] a[j]) ? a[i] : a[j]; while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int t l; t r; t) a[t] tmp[t]; }判断条件里用a[i] a[j]而不是就是为了保证稳定性左边相等时优先拿左边。逆序对的做法也藏在里面当a[i] a[j]时左边从 i 到 mid 的所有元素都和 a[j] 构成逆序对一次性加上mid - i 1即可。3.3 堆排序原地、O(n log n)、最坏情况也稳堆排的价值在于它是唯一能同时做到“原地 最坏 O(n log n)”的常用比较排序。它的核心是两个操作建堆和下沉调整。void siftDown(std::vectorint a, int root, int end) { while (root * 2 1 end) { int child root * 2 1; if (child 1 end a[child] a[child 1]) child; if (a[root] a[child]) { std::swap(a[root], a[child]); root child; } else { return; } } } void heapSort(std::vectorint a) { int n static_castint(a.size()); for (int i n / 2 - 1; i 0; --i) siftDown(a, i, n - 1); for (int end n - 1; end 0; --end) { std::swap(a[0], a[end]); siftDown(a, 0, end - 1); } }建堆从n/2 - 1开始因为叶子节点天然满足堆性质不用调整。建堆的复杂度是 O(n) 而不是 O(n log n)这个结论第一次看会觉得反直觉但它来自等比级数求和值得自己推一遍。堆排的缺点是缓存不友好每次访问2*i1和2*i2都是跳跃的所以实际跑起来通常比快排慢两三倍尽管复杂度一样。3.4 STL 排序怎么选实际写代码时排序绝大多数情况直接用 STL选哪个看需求需求推荐原因一般排序std::sort内省排序平均最快保持相等元素顺序std::stable_sort归并实现必要时才分配额外空间只要前 k 个或第 k 个std::partial_sort/std::nth_element不必全排数据已基本有序std::sort 插入场景提前退出的优化效果有限但也不亏需要自定义比较且高频传 lambda注意别捕获太重比较函数会被调用 O(n log n) 次最后提醒一个高频错误自定义比较函数必须满足严格弱序。写成return a b;是错的因为a b时返回 true会让排序内部逻辑判断混乱某些实现下直接越界崩溃。正确写法是return a b;或return a b;相等时返回 false。4. 二分查找看起来最简单写起来最容易错我在面试里最爱让人写二分查找不是因为难而是因为它能准确区分“背过”和“想通了”。统计下来一次写对且没有死循环、没有越界的人不到三成。问题集中在三个地方区间定义不清、中点计算溢出、循环退出条件搞混。4.1 两种区间写法选一种吃透二分查找有两种主流写法左闭右闭[l, r]和左闭右开[l, r)。我强烈建议只精一种我个人只写左闭右开因为它和lower_bound的语义一致不容易混。// 左闭右开[lo, hi) int binarySearch(const std::vectorint a, int target) { int lo 0, hi static_castint(a.size()); while (lo hi) { int mid lo (hi - lo) / 2; // 防止 lo hi 溢出 if (a[mid] target) return mid; if (a[mid] target) lo mid 1; else hi mid; } return -1; }mid lo (hi - lo) / 2这个写法一定要养成习惯。虽然 C 里int加法溢出是未定义行为但用lo hi在接近 21 亿的数据量下确实会出事。这个习惯是从 Java 的Arrays.binarySearch源码里学来的值得抄。4.2 lower_bound 和 upper_bound 的真实用法std::lower_bound返回第一个不小于目标的位置std::upper_bound返回第一个大于目标的位置。这两个组合起来能干很多事#include algorithm #include vector std::vectorint v {1, 3, 3, 3, 7, 9}; auto lo std::lower_bound(v.begin(), v.end(), 3); // 指向第一个 3 auto hi std::upper_bound(v.begin(), v.end(), 3); // 指向 7 int cnt static_castint(hi - lo); // 3 出现的次数 3 bool exists std::binary_search(v.begin(), v.end(), 7); // true这三个函数的共同前提是区间已经有序用之前先确认排序。我见过有人直接对std::map用lower_bound虽然也能跑但那是成员函数版本语义是按键查找和通用版本是两回事。std::map::lower_bound是 O(log n)而如果误用了通用版本会退化成 O(n)性能差几百倍。4.3 二分答案真正拉开差距的用法二分查找最值钱的用法不是查元素而是“二分答案”。当一个问题满足“答案具有单调性”——也就是猜一个值 x能判断它偏大还是偏小——就可以用二分把最优化问题转成判定问题。典型的例子把 n 根长度不一的绳子剪成 k 段等长绳子求每段最大长度。#include vector #include cmath bool canCut(const std::vectordouble ropes, int k, double len) { if (len 0) return true; long long cnt 0; for (double r : ropes) cnt static_castlong long(r / len); return cnt k; } double maxLen(const std::vectordouble ropes, int k) { double lo 0.0, hi 1e9; for (int iter 0; iter 100; iter) { // 固定迭代次数比 eps 判断更稳 double mid (lo hi) / 2; if (canCut(ropes, k, mid)) lo mid; else hi mid; } return lo; }这里有个实践细节浮点二分不要用while (hi - lo 1e-9)因为当数值量级很大时这个条件可能永远不满足直接死循环。固定迭代 100 次精度已经远超 double 能表达的极限而且执行时间完全可预测。这个习惯是从写几何题的经验里总结出来的救过我不少次。5. 字符串算法KMP 与哈希是两把不同的刀字符串问题在笔试里出现频率极高而且套路明显。掌握 KMP 和字符串哈希这两样能覆盖七八成的情况。剩下的可以用std::string::find应付但要清楚它的最坏复杂度是 O(nm)。5.1 KMPnext 数组到底在算什么KMP 的核心思想是“利用已经匹配成功的部分避免主串指针回退”。而 next 数组也常叫前缀函数或失配数组记录的是“以当前位置结尾的子串的最长相等前后缀长度”。#include string #include vector std::vectorint buildNext(const std::string p) { std::vectorint nxt(p.size(), 0); for (std::size_t i 1, j 0; i p.size(); i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; if (p[i] p[j]) j; nxt[i] static_castint(j); } return nxt; } int kmpSearch(const std::string s, const std::string p) { if (p.empty()) return 0; std::vectorint nxt buildNext(p); for (std::size_t i 0, j 0; i s.size(); i) { while (j 0 s[i] ! p[j]) j nxt[j - 1]; if (s[i] p[j]) j; if (j p.size()) return static_castint(i - j 1); } return -1; }看buildNext里那一行while (j 0 p[i] ! p[j]) j nxt[j - 1];这是整个算法的灵魂。它的含义是失配了就退到上一个可能的匹配位置继续试而不是退到起点。理解这一行的关键在于把nxt[j-1]理解成“长度为 j 的前缀中最长相等前后缀的长度”退到那里可以保证前面那一段仍然匹配。我第一遍学 KMP 的时候最大的卡点是为什么 next 数组要用j - 1去索引。后来想通了j表示当前已匹配的长度nxt[j-1]才是“长度 j 的子串”的答案。这个下标差一位的坑几乎每个人都踩过。5.2 字符串哈希简单粗暴但要注意冲突哈希的思路是用一个数值代表一个子串比较数值比逐字符比较快得多。用滚动哈希可以在 O(1) 时间内求出任意子串的哈希值。#include string #include vector #include cstdint struct StringHash { static constexpr std::uint64_t BASE 131; std::vectorstd::uint64_t h, pw; explicit StringHash(const std::string s) { h.assign(s.size() 1, 0); pw.assign(s.size() 1, 1); for (std::size_t i 0; i s.size(); i) { h[i 1] h[i] * BASE static_castunsigned char(s[i]); pw[i 1] pw[i] * BASE; } } // 区间 [l, r] 的哈希下标从 0 开始 std::uint64_t get(int l, int r) const { return h[r 1] - h[l] * pw[r - l 1]; } };用std::uint64_t自然溢出当取模速度很快但理论上存在被构造数据攻击的可能。做线上服务时建议改用双哈希或者一个大质数取模。做算法题时单哈希通常够用但如果题目数据特别刁钻还是双哈希保险。5.3 两个高频小套路回文判断可以用双指针从两端往中间夹也可以用哈希加二分求最长回文子串。双指针写法简单但只能判断整个串求最长回文多用中心扩展O(n²) 但常数极小实际比 Manacher 更容易写对。统计子串出现次数如果模式串很短直接std::string::find循环找就行如果模式串长或者要查很多次先对文本建哈希然后 O(1) 比较每个候选位置总复杂度 O(n m)。这个套路的性价比极高代码量只有 KMP 的一半。6. 图论算法从存图开始就别写错图论题翻车的重灾区不是算法本身而是图的存储方式。用邻接矩阵存稠密图没问题存稀疏图就浪费 O(n²) 空间用邻接表存稠密图遍历效率又不如矩阵。选错了不是算错而是直接超内存或者超时。6.1 三种存图方式的选择存储方式空间适用场景备注邻接矩阵O(n²)n ≤ 1000 的稠密图查询两点是否相邻 O(1)邻接表O(n m)大多数稀疏图最常用链式前向星O(n m)边数极大的场景缓存友好但写起来繁琐日常练习和面试用std::vectorstd::vectorint或者std::vectorstd::vectorstd::pairint,int就够了。链式前向星主要在竞赛里为了卡常数才用工程代码里可读性更重要。6.2 Dijkstra堆优化之后才算真正能用朴素 Dijkstra 是 O(n²)堆优化之后是 O((n m) log n)。C 里直接用std::priority_queue配合一个惰性删除的技巧写起来很短。#include vector #include queue #include utility #include limits std::vectorlong long dijkstra(int n, const std::vectorstd::vectorstd::pairint,int g, int src) { const long long INF std::numeric_limitslong long::max() / 4; std::vectorlong long dist(n, INF); using Node std::pairlong long,int; // (距离, 节点) std::priority_queueNode, std::vectorNode, std::greaterNode pq; dist[src] 0; pq.emplace(0, src); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 惰性删除过期条目直接跳过 for (auto [v, w] : g[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.emplace(dist[v], v); } } } return dist; }INF取LLONG_MAX / 4而不是直接取LLONG_MAX是为了避免dist[u] w时溢出成负数。这个细节在写多源或带负权判断时特别重要。另外 Dijkstra 不能处理负权边如果题目里有权值为负的边要换 Bellman-Ford 或 SPFA。我见过有人硬套 Dijkstra 跑负权图结果输出一个看起来很合理但完全错误的答案很难发现。6.3 Prim 与 Kruskal稠密图和稀疏图的分别最小生成树两个算法选择依据很简单边少用 Kruskal点少用 Prim。Kruskal 需要排序所有边加并查集代码短、好写、好调试日常首选。#include vector #include algorithm #include numeric struct Edge { int u, v, w; }; struct DSU { std::vectorint p, r; explicit DSU(int n) : p(n), r(n, 0) { std::iota(p.begin(), p.end(), 0); } int find(int x) { return p[x] x ? x : p[x] find(p[x]); } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (r[a] r[b]) std::swap(a, b); p[b] a; if (r[a] r[b]) r[a]; return true; } }; long long kruskal(int n, std::vectorEdge edges) { std::sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); DSU dsu(n); long long total 0; int used 0; for (const Edge e : edges) { if (dsu.unite(e.u, e.v)) { total e.w; if (used n - 1) break; } } return used n - 1 ? total : -1; // -1 表示图不连通 }这里的并查集用了路径压缩加按秩合并单次操作接近常数。find写成三目表达式的递归形式虽然看起来有点炫技但它确实比显式栈的循环版更短而且现代编译器对尾递归优化得不错。唯一要注意的是超大图节点数百万时递归深度可能出问题那时候改成循环更稳妥。6.4 匈牙利算法二分图最大匹配的入门选择匈牙利算法解决的是二分图最大匹配问题思路是不断找增广路。它的复杂度是 O(V·E)对于中等规模的图完全够用。理解它的关键是明白used数组的作用防止在同一次寻找中重复访问同一节点导致死循环。#include vector bool tryKuhn(int u, const std::vectorstd::vectorint g, std::vectorint matchR, std::vectorint used, int tag) { for (int v : g[u]) { if (used[v] tag) continue; used[v] tag; if (matchR[v] -1 || tryKuhn(matchR[v], g, matchR, used, tag)) { matchR[v] u; return true; } } return false; } int maxMatching(int nLeft, const std::vectorstd::vectorint g) { std::vectorint matchR(g.size(), -1), used(g.size(), 0); int res 0; for (int u 0; u nLeft; u) if (tryKuhn(u, g, matchR, used, u 1)) res; return res; }用tag代替每次清空used数组是一个很实用的小优化。如果每次找增广路都std::fill(used.begin(), used.end(), false)总复杂度里会多一个 O(V) 的常数因子。用递增的时间戳判断条件从是否访问过变成是否在本轮访问过语义完全一致但省掉了清空操作。7. 思维类算法贪心、剪枝、动态规划怎么练前面几层都是有模板可背的第四层不一样。贪心和动态规划没有万能模板靠的是对问题结构的敏感度。这也是很多人刷了几百题还是不会做的原因他们记的是题不是结构。7.1 贪心先证明再写代码贪心的定义很简单每一步都选当前看起来最好的。难点在于证明这个局部最优能推出全局最优证明不了就不能用。最典型的例子是跳跃游戏问是否能从起点跳到终点策略是维护一个当前能到达的最远位置。#include vector #include algorithm bool canJump(const std::vectorint nums) { int reach 0; for (int i 0; i static_castint(nums.size()); i) { if (i reach) return false; // 这个位置根本到不了 reach std::max(reach, i nums[i]); if (reach static_castint(nums.size()) - 1) return true; } return true; }为什么这个贪心是对的因为能到达的最远位置这个信息是单调不减的只要当前位置在覆盖范围内往后所有位置的可达性都可以通过 reach 来判断。如果题目要求的是最少跳几次贪心就不能简单地取最远而要额外维护当前层能到的最远和下一层能到的最远做法变成类似 BFS 的层次遍历。这类变形非常常见值得专门练。7.2 回溯与剪枝暴力搜索的工程化回溯的本质是带撤销的 DFS。剪枝则是在搜索过程中尽早砍掉不可能产生答案的分支。剪枝做得好不好直接决定程序是跑 0.1 秒还是 10 秒。以组合总和为例给定候选数组和目标值求所有和为目标的组合每个数可重复使用。基本回溯找到所有解加上排序后剪枝能大幅提速。#include vector #include algorithm void dfs(const std::vectorint cand, int target, int start, std::vectorint path, std::vectorstd::vectorint res) { if (target 0) { res.push_back(path); return; } for (int i start; i static_castint(cand.size()); i) { if (cand[i] target) break; // 已排序后面的只会更大直接剪掉 path.push_back(cand[i]); dfs(cand, target - cand[i], i, path, res); // 传 i 而不是 i1允许重复取 path.pop_back(); } } std::vectorstd::vectorint combinationSum(std::vectorint cand, int target) { std::sort(cand.begin(), cand.end()); std::vectorstd::vectorint res; std::vectorint path; dfs(cand, target, 0, path, res); return res; }剪枝的常见手段有四种可行性剪枝当前路径已经不可能满足约束、最优性剪枝当前代价已经超过已知最优解、搜索顺序剪枝先试更可能成功的分支、记忆化剪枝同一状态不重复计算。前两种最常用也最容易见效。7.3 动态规划从状态定义开始DP 的核心不是写转移方程而是定义状态。状态定义对了方程往往水到渠成状态定义错了怎么写都别扭。以 0-1 背包为例状态定义为前 i 个物品、容量为 j 时的最大价值。#include vector #include algorithm int knapsack01(const std::vectorint w, const std::vectorint v, int cap) { int n static_castint(w.size()); std::vectorint dp(cap 1, 0); for (int i 0; i n; i) { for (int j cap; j w[i]; --j) { // 逆序保证每件物品只用一次 dp[j] std::max(dp[j], dp[j - w[i]] v[i]); } } return dp[cap]; }内层循环必须逆序这是 0-1 背包和完全背包的分界线。逆序保证在更新dp[j]时dp[j - w[i]]还是上一轮的状态也就是这件物品还没被放过。如果写成正序同一件物品会被放多次变成完全背包。这个细节我在纸上推了三四遍才彻底记住光看文字解释容易忘。7.4 数论小算法判断质数和快速幂判断质数最常见的优化是只试到 √n并且跳过偶数。bool isPrime(long long n) { if (n 2) return false; if (n % 2 0) return n 2; for (long long d 3; d * d n; d 2) if (n % d 0) return false; return true; }注意循环条件写d * d n而不是d sqrt(n)。sqrt每次调用都有开销而且浮点误差可能在 n 是完全平方数时导致漏判。用d * d时要注意 n 接近int上限时d * d可能溢出所以参数用long long。如果需要判断很多次先用线性筛预处理出范围内的素数表然后 O(1) 查询这才是真正的优化方向。快速幂用于计算 a 的 b 次方模 m把 O(b) 降到 O(log b)。long long qpow(long long a, long long b, long long mod) { long long r 1 % mod; a % mod; while (b 0) { if (b 1) r r * a % mod; a a * a % mod; b 1; } return r; }1 % mod是为了处理 mod 等于 1 的边界情况这时候任何数模 1 都是 0。这种看似多余的写法在边界测试里能救命。8. 环境与踩坑算法练不下去往往是工具问题算法本身难环境和工具的坑更难因为它们跟算法没关系纯粹消耗你的耐心。我在社区里看到最多的问题不是KMP 怎么理解而是为什么我代码编译不过。这一节把最常见的几类问题集中说清楚。8.1 本地环境怎么配最省心Windows 上写 C 练习最省事的组合是 VSCode MinGW-w64通过 MSYS2 安装或者直接用 Visual Studio。VSCode 需要配置三个文件c_cpp_properties.json管智能提示的包含路径tasks.json管编译任务launch.json管调试。很多人只配了tasks.json就开始写结果调试器跑不起来白白浪费时间。核心的编译命令建议加上这些参数g -stdc17 -O2 -Wall -Wextra -g main.cpp -o main-stdc17保证能用结构化绑定和std::optional这些现代特性-O2开优化避免本地测出来的时间跟线上差太多-Wall -Wextra打开警告能提前发现未初始化变量、有符号无符号比较这类隐蔽 bug-g保留调试信息。这五个参数基本是我的默认配置写练习也一样。提示如果开了-Wall之后看到大量警告别急着关掉。警告里十有八九藏着真 bug特别是-Wsign-compare有符号和无符号比较和-Wuninitialized未初始化这两个在实际项目里都造成过线上事故。8.2 几个高频编译链接报错报错关键字常见原因处理方式undefined reference to ...函数声明了没定义或源文件没参与链接检查实现是否漏写、编译时是否带上了所有 cppcannot open source file xxx.h头文件路径没配好在c_cpp_properties.json里补 includePathredefinition of ...头文件被多次包含加#pragma once或 include guardexpected ; at end of ...多半是上一行或宏展开出了问题从报错行的上一行开始查缺VCRUNTIME140.dll之类运行库缺失安装对应的运行库发行包最后一类问题在 Windows 上特别常见尤其是拿到别人编译好的程序运行时报缺 dll。这跟算法没关系装好对应的运行库就行。需要提醒的是不同版本的编译器产出的程序依赖不同版本的运行库发布时最好静态链接加-static或者把依赖一起打包省得用户那边各种报错。8.3 复杂度估算和数据规模对照写题之前先看数据规模基本就能定算法方向。这张表我建议贴在显示器边上数据规模 n可接受的复杂度典型算法n ≤ 10O(n!)全排列暴力n ≤ 20O(2ⁿ)状压 DP、子集枚举n ≤ 100O(n³)Floyd、区间 DPn ≤ 1000O(n²)朴素 Dijkstra、普通 DPn ≤ 1e5O(n log n)排序、堆、线段树n ≤ 1e6O(n)双指针、前缀和、单调栈n ≤ 1e9O(log n) 或 O(√n)二分、快速幂、试除法按一秒一亿次简单运算来估1e5 的数据跑 O(n²) 需要约 100 亿次操作直接超时。看到 n 是 1e5脑子里就该自动排除 O(n²) 的方案。这个直觉靠多做题养出来做的时候养成习惯先看规模再想算法。9. 常见问题速查表下面这些问题是我在带人和自己练习时反复遇到、也反复被问到的整理成表方便对照排查。问题现象可能原因排查思路快排在有序数据上栈溢出pivot 固定取首元素分区退化改取中间值或随机值或加小区间插入排序收尾二分查找死循环边界更新写成了lo mid或hi mid - 1混用统一采用左闭右开用lo hi作为退出条件排序后相等元素顺序乱了用了不稳定排序换std::stable_sort或把序号作为第二关键字KMP 结果偏一位next 数组索引差一记住nxt[j-1]表示长度为 j 的前缀函数值Dijkstra 结果错误图里有负权边换 Bellman-Ford 或 SPFA并查集超时没做路径压缩find里加p[x] find(p[x])DP 结果比正确答案大0-1 背包内层写成了正序容量维度改成从大到小遍历哈希判等误判单哈希被构造数据撞了改用双哈希或换更大的质数模程序本地跑得动线上超时本地开了-O2线上或没开提交前确认编译选项或改算法递归搜索超时没有剪枝或剪枝太弱加可行性/最优性剪枝调整搜索顺序关于哈希判等误判这一条想多说两句。用单哈希做字符串比较时理论上确实存在不同字符串哈希值相同的情况虽然概率很低但在一些数据被刻意构造的场合会被利用。做竞赛题时如果发现答案总是差一点点而其他部分看起来都对就值得怀疑是不是哈希冲突。换成双哈希或者干脆老老实实用 KMP问题就没了。这种排查经验很难从教科书上学到只能靠踩坑积累。另外关于递归搜索超时很多人以为加个if判断就叫剪枝了其实剪枝的质量差别很大。同样是组合求和剪枝前跑 3 秒排序后加一个if (cand[i] target) break;可能直接降到 0.05 秒。原因很简单这个 break 让整个搜索树的一大片分支直接消失了而不是逐个节点去判断。判断剪枝好坏的标准就是它一次性砍掉的是整棵子树还是一个节点前者才有意义。我在实际写这些算法的过程中体会最深的一点是算法能力的提升曲线不是线性的而是阶跃的。某个阶段你会觉得怎么练都没进步卡在同一个难度上然后突然某一天之前想不通的题目一眼就有思路。这个阶跃的触发点通常不是我又刷了五十道题而是我终于想通了某个结构。比如想通 KMP 的 next 数组本质上是在描述字符串的自相似结构想通 DP 的状态定义必须满足无后效性想通贪心必须证明想通二分答案的判定函数为什么可以不依赖具体答案。这些想通的时刻比刷题数量值钱得多。所以我的建议是刷题时别追求数量遇到想不通的题哪怕只有一道也停下来把它彻底拆开状态是什么、转移为什么成立、边界怎么定、剪枝为什么有效。拆透一道题的收获胜过模糊地做完十道。最后一个实用小技巧准备一个自己的模板文件把排序、二分、并查集、Dijkstra、KMP、快速幂这些代码整理进去每次写题前先默写一遍再对照。用不了两周这些模板就会变成你的条件反射之后你的注意力就能全部放在问题建模上而不是纠结数组下标有没有差一。
阅读完成 · 觉得有帮助？
