算法修炼之练气篇说的就是把算法入门这段路给境界化。为什么非要用修仙的框架来讲因为算法这东西光看懂了没用得练。看题解是看别人的心法自己写出来、调通、跑过边界用例那才叫把真气纳进经脉。我带过几届新人也混过不少刷题群发现大部分人卡住不是因为脑子不行而是没搞清自己现在处于哪个阶段、该练什么、练到什么程度算过关。练气十层这套刻度就是解决这个问题的——它把从复杂度认知到动态规划入门这十个台阶拆开每层给你明确的判定标准、必练的算法和踩坑清单。适合刚接触算法的在校生、转行补基础的开发者也适合工作几年但算法底子虚、想系统回炉的同行。下面我按十层的顺序把每一层该干什么、为什么这么排、坑在哪全摊开讲一遍。1. 为什么给算法学习设计一套练气境界1.1 练气十层的划分逻辑先讲清楚这套境界凭什么这么分。练气十层的排序不是拍脑袋来的它遵循一条很硬的主线先建立对代价的直觉再学如何降低代价最后学如何在约束下做决策。一层到三层解决的是怎么把数据摆顺和怎么衡量快慢这是所有后续内容的地基四层到六层开始进入特定数据结构支持的查找与匹配属于用工具换效率七层到十层则是图论、贪心、动态规划这些需要建模能力的硬骨头。换句话说前六层是内功招式后四层是实战心法。我见过太多人一上来就啃动态规划结果连递归的栈深度都算不清楚写出来的状态转移方程看着像那么回事一跑就超时或者结果错误。根子就在跳级。修仙小说里越级挑战要么天赋异禀要么有奇遇算法修炼里没有奇遇只有老老实实把每层的基础打牢。练气十层的意义就是让你清楚自己现在该待在哪个境界不要眼高手低。1.2 每层的判定标准与修炼周期判定一个人是不是真的过了某一层我一般看三个指标能默写核心代码、能说清复杂度、能识别变体。默写是肌肉记忆说清复杂度是知其所以然识别变体是能迁移。三个都满足才算过关只满足一个那叫看过不叫练过。周期上如果每天能保证两小时有效练习一层大概三天二三层各一周四五六层加起来两周七八九层三周十层状态设计这一步最磨人可能要一个月甚至更久。下面这张表是我给新人做评估时用的速查表你可以对照看看自己目前大概在哪一层卡着境界核心能力典型算法常见卡点一层复杂度分析大O估算分不清最好/最坏/平均二层基础排序冒泡、选择、插入循环边界写错三层分治思想归并排序递归合并逻辑混乱四层有序查找二分查找死循环、边界偏移五层字符串匹配KMPnext数组理解不透六层堆结构堆排序、优先队列下沉上浮搞反七层图遍历DFS、BFS访问标记遗漏八层生成树与最短路Prim、Dijkstra松弛条件写错九层贪心与剪枝区间调度、回溯剪枝贪心策略选错十层动态规划线性DP、背包状态定义不清注意这张表是自评工具不是给人贴标签用的。卡在某一层很正常关键是要知道卡住的原因而不是盲目往下跳。2. 练气一层到三层复杂度与基础排序的打磨2.1 一层把时间复杂度的直觉练出来练气一层看起来最简单其实最容易被轻视。这一层要练的是对代价的本能反应。什么叫本能反应就是你看到双重循环脑子里立刻跳出这是 O(n²)看到循环里套一个二分立刻想到这是 O(n log n)。这个直觉不是靠背定义背出来的是靠大量估算了之后形成的。我当初练这一层的方法很笨但有效随便找个自己写过的函数先自己估复杂度再去数实际执行次数验证。比如一个嵌套循环外层跑 n 次、内层跑 i 次总次数就是 12...n n(n1)/2去掉常数和低阶项就是 O(n²)。这种手算做上二三十个你对复杂度的感觉就来了。空间复杂度同理重点看有没有开辟和输入规模同量级的额外空间递归还要把调用栈算进去。很多人忽略递归的栈空间写个深度 n 的递归还以为是 O(1) 空间这是典型的坑。这一层还有一个必须澄清的误区最好、最坏、平均复杂度是三件事。快速排序平均 O(n log n)最坏 O(n²)这个最坏不是理论上的边角料而是真实会发生的——有序数组配上一个傻选的基准分分钟退化。理解这一点你在后面的层数里才会主动去考虑最坏情况而不是只看平均表现。2.2 二层冒泡、选择、插入三兄弟怎么选到了二层正式开始接触排序。冒泡、选择、插入这三兄弟复杂度都是 O(n²)很多教程讲完就带过其实这里面有讲究。冒泡排序是相邻比较交换一趟下来最大的元素冒到末尾它的特点是稳定而且如果在某一趟没有发生任何交换说明已经有序可以提前退出所以对近乎有序的数据表现还不错。选择排序是每趟找最小值放到前面交换次数最少最多 n-1 次但无论数据什么状态都要跑满 O(n²)而且它不稳定。插入排序才是这三兄弟里最实用的。它的逻辑像整理手里的扑克牌把新牌插到已排好序的部分里。虽然也是 O(n²)但当数据基本有序时插入排序接近 O(n)所以很多工业级排序库在处理小数组比如长度小于 16时会退化成插入排序就是这个道理。下面这段 C 是插入排序的标准写法注意内层循环从后往前、边比较边挪位void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; // 从后往前找插入位置顺便把比 key 大的元素往后挪 while (j 0 arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; // 此时 j1 就是 key 该待的位置 } }写这段最容易错的地方是arr[j 1] key这一句。因为循环结束时 j 已经减到了不满足条件的位置真正的空位是 j1。我见过新手写成arr[j] key结果把元素覆盖了。这就是练气二层最典型的坑循环结束后的指针位置和你想要的位置差一个。2.3 三层分治思想与归并排序三层的核心不是学一个新的排序而是理解分治这个思想。归并排序把数组一分为二各自排好再合并这个过程天然适合递归描述。它的复杂度稳定在 O(n log n)不会像快排那样退化代价是需要 O(n) 的额外空间来做合并。这个用空间换稳定的取舍是三层要建立的意识。归并的关键在合并这一步两个已经有序的子数组各拿一个指针从头扫谁小拿谁。写法如下void merge(int arr[], int l, int m, int r) { int n1 m - l 1, n2 r - m; vectorint left(n1), right(n2); for (int i 0; i n1; i) left[i] arr[l i]; for (int j 0; j n2; j) right[j] arr[m 1 j]; int i 0, j 0, k l; while (i n1 j n2) { // 用 保证稳定性 if (left[i] right[j]) arr[k] left[i]; else arr[k] right[j]; } while (i n1) arr[k] left[i]; while (j n2) arr[k] right[j]; }这里和的区别决定了排序是否稳定。用时左边相等元素优先稳定性得以保持。练气三层要养成的习惯是每次写比较都要想一下相等元素该怎么处理。这个问题在后面很多算法里都会反复出现。3. 练气四层到六层查找、字符串与堆的进阶3.1 四层二分查找的边界是魔鬼二分查找的代码短但它是公认的看一眼就会、一写就错的典型。四层要练的核心就是边界。二分最常见的写法有左闭右闭[left, right]和左闭右开[left, right)两种选哪种都行但整个算法必须自洽不能混用。我推荐左闭右闭因为直觉上更好理解。标准写法int binarySearch(int arr[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; // 防溢出 if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }mid left (right - left) / 2这个写法是为了防止(left right)溢出在有符号整数里left right超过上限会变成负数导致 mid 变负、数组越界。这个细节在小数据上测不出来一到大数据就炸属于必须刻进肌肉记忆的写法。判断循环条件用还是取决于你的区间定义左闭右闭用左闭右开用。判断完还要看更新时是mid 1 / mid - 1还是mid混了就是死循环。提示二分查找还有一个查找边界的变体——找第一个大于等于目标的位置、找最后一个小于等于目标的位置。这类题是四层的进阶热词里的二分查找算法高频出现练熟了对后面做贪心和DP的优化都有帮助。3.2 五层KMP 与 next 数组的真面目字符串匹配是五层的主菜。暴力匹配每次失配都要把模式串回退到开头KMP 的精髓在于失配时利用已匹配的信息让模式串回退到最长相等前后缀的位置而不是从头再来。这个最长相等前后缀就是 next 数组存的东西。很多人学 KMP 卡在 next 数组的求解上其实你可以这样理解next[i] 表示模式串前 i 个字符组成的子串里最长相等前后缀的长度。求 next 数组的过程本身就是模式串自己和自己匹配的过程用两个指针一个表示当前已匹配的前缀末尾一个表示正在处理的位置。这段代码值得反复默写void getNext(const string p, vectorint next) { int n p.size(); next[0] 0; int j 0; // j 指向前缀末尾 for (int i 1; i n; i) { while (j 0 p[i] ! p[j]) j next[j - 1]; if (p[i] p[j]) j; next[i] j; } }那个while (j 0 p[i] ! p[j]) j next[j - 1];是灵魂它的意思是当前失配了就往前找更短的相等前后缀直到匹配上或者 j 回到 0。理解不了就画图把模式串写成aabaa这种有重复前缀的一步步跟着 j 走一遍走三次就通了。五层还有一层隐藏价值KMP 的利用已算信息避免重复计算这个思路是后面动态规划的思想雏形别把它当孤立的字符串技巧。3.3 六层堆结构和堆排序的取舍六层进入堆。堆是一棵完全二叉树用数组存储父节点和子节点的下标关系是left 2*i1、right 2*i2、parent (i-1)/2。大顶堆保证每个父节点不小于子节点。堆排序分两步先建堆再反复把堆顶最大值和末尾交换、缩小堆范围、下沉调整。void siftDown(int arr[], int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n arr[l] arr[largest]) largest l; if (r n arr[r] arr[largest]) largest r; if (largest ! i) { swap(arr[i], arr[largest]); siftDown(arr, n, largest); // 继续下沉 } }堆排序复杂度稳定 O(n log n)原地排序但它是不稳定的而且实际运行常数比快排大所以工业界用得不多。那为什么还要练因为堆真正的价值不在排序而在优先队列。很多算法比如 Dijkstra、A*、哈夫曼编码都需要每次取当前最小值这个操作堆正好提供 O(log n) 的插入和取顶。六层的目标是让你看到需要动态取最值就条件反射想到堆而不是每次排序一遍。4. 练气七层到十层图论、贪心与搜索的实战4.1 七层图的两种遍历与访问标记七层开始接触图。图有两种基本遍历DFS 和 BFS。DFS 靠递归或栈一路走到底再回溯BFS 靠队列一层一层往外扩。两者都要维护一个visited数组防止重复访问和小环导致死循环。这个visited是七层最容易出错的地方图有环不像树那样天然无环忘记标记就会无限递归或者无限入队。邻接表的 DFS 写法void dfs(int u, vectorvectorint adj, vectorbool visited) { visited[u] true; for (int v : adj[u]) { if (!visited[v]) dfs(v, adj, visited); } }DFS 适合判断连通性、找路径、拓扑排序BFS 适合求无权图最短路、求层数。选哪个要看问题需要什么。我见过新手一律用 DFS结果求无权最短路时写出一堆逻辑来模拟层数绕远了。记住一条无权图的最短路径用 BFS因为 BFS 第一次访问到某个点时的层数就是最短距离。这条直觉能帮你在很多题里省下大量时间。4.2 八层Prim 最小生成树与最短路八层上生成树和最短路。Prim 算法求最小生成树思路是维护一个已加入树的顶点集合每次从连接树内和树外的边里挑最短的那条把对应顶点拉进树里。用优先队列优化后复杂度是 O(E log V)。核心代码int prim(int n, vectorvectorpairint,int adj) { vectorbool inMST(n, false); priority_queuepairint,int, vectorpairint,int, greater pq; pq.push({0, 0}); // {权值, 顶点} int total 0, cnt 0; while (!pq.empty() cnt n) { auto [w, u] pq.top(); pq.pop(); if (inMST[u]) continue; // 这条边已过时 inMST[u] true; total w; cnt; for (auto [v, wt] : adj[u]) if (!inMST[v]) pq.push({wt, v}); } return cnt n ? total : -1; }if (inMST[u]) continue;这句是懒惰删除因为同一个顶点可能被多次入队取出时如果已经在树里就跳过。这个技巧在 Dijkstra 里同样适用。说到最短路Dijkstra 和 Prim 长得非常像区别在于 Prim 存的是到树的边权Dijkstra 存的是从源点到该点的累计距离。热词里的最短路径算法prim算法都是这一层的重点建议两个一起练对比着记效率翻倍。注意Dijkstra 不能处理负权边因为它的贪心前提是已确定的最短距离不会再被缩短。有负权要用 Bellman-Ford 或者 SPFA。这个边界很多人栽过跟头。4.3 九层贪心策略与剪枝的尺度九层是贪心和剪枝。贪心的难点不在代码而在证明——你得说明为什么每一步取局部最优最后能得到全局最优。热词里跳跃游戏2 贪心算法就是经典例子每次在当前能跳到的范围内选一个能跳得更远的点作为下一跳落点。代码很短但要想清楚为什么这样不会错过最优解。剪枝则是回溯搜索里的艺术。比如求组合总和如果当前和已经超过目标就返回如果剩余元素加上当前和还不够目标也可以返回。剪枝的核心是尽早排除不可能的分支但剪枝条件写错容易误杀正确解所以要格外小心。检验剪枝是否正确的方法先写不剪枝的暴力版本跑小数据得到标准答案再加上剪枝对比结果是否一致。这个先暴力后优化的习惯能帮你避免大量调试时间。智能优化算法里那些听起来玄乎的名字——蚁群算法、粒子群、模拟退火——本质上都是带随机性的启发式搜索它们不保证最优只在解空间里找一个足够好的解。想深入的话等练气十层过了再碰现在碰容易走火入魔。4.4 十层动态规划入门与状态设计练气十层的最后一层也是最难的一层是动态规划。DP 的核心就三件事定义状态、写状态转移方程、确定遍历顺序和初始化。听起来简单做起来每一步都是坑。以最经典的 0-1 背包为例dp[j]表示容量为 j 时能装的最大价值转移方程是dp[j] max(dp[j], dp[j - weight[i]] value[i])遍历时容量要从大到小保证每个物品只用一次。int knapsack(int W, vectorint wt, vectorint val) { vectorint dp(W 1, 0); for (int i 0; i wt.size(); i) { // 0-1 背包容量必须倒序遍历 for (int j W; j wt[i]; --j) { dp[j] max(dp[j], dp[j - wt[i]] val[i]); } } return dp[W]; }为什么 0-1 背包要倒序、完全背包要正序因为正序时dp[j - wt[i]]可能已经被本物品更新过相当于允许重复使用倒序时用的还是上一轮的值保证只用一次。这个方向问题是十层最容易出错、也最能考察理解深度的地方。热词里的数据结构与算法算法设计与分析这些大词落到实操就是这一层层啃下来。状态设计没思路时我的经验是从最后一步倒推问自己到达最终答案的最后一手操作是什么这个操作之前的子问题是什么。把这个想清楚状态和转移往往就浮出来了。这个倒推法帮我解决过很多一开始完全没头绪的题。5. 常见问题与排查技巧实录5.1 算法修炼常见问题速查表下面这张表是我这些年收集的高频问题按境界分类卡壳时对着查比重新看教程快得多现象可能原因排查方向程序无输出、卡住死循环/死递归检查循环变量是否更新、visited 是否遗漏结果差一边界少算或多算检查循环是还是下标偏移大数才出错整型溢出检查 mid 计算、累加是否用 long long排序后相等元素乱序稳定性被破坏检查比较时用还是二分搜不到答案区间更新写错左闭右闭必须mid±1DP 结果偏大遍历方向错0-1 背包容量倒序完全背包正序最短路径有负权结果错Dijkstra 不适用换 Bellman-Ford 或 SPFA5.2 独家避坑心得第一个心得每写一个循环先在纸上跑一遍最小规模。比如数组长度为 1、为 0、为偶数、为奇数这四种情况都手动走一遍循环。我见过太多 bug 都是在这些边角规模上暴露的而大测试用例反而掩盖了它们。第二个心得不要一上来就追求最优解。先写能跑通的暴力版本拿到正确结果当作对照再逐步优化。这样一旦优化版本出错你立刻知道是优化引入的 bug排查范围缩小一大截。这个暴力打底的策略是我调试复杂算法时最依赖的方法没有之一。第三个心得复杂度不是背出来的是估出来的。拿到一个算法先别急着查资料自己数一数循环嵌套了几层、每层跟什么规模相关、有没有 log 出现。估完再对答案长期下来你对算法的敏感度会远超只会背结论的人。第四个心得刷题要按境界来不要随机刷。很多人今天做道简单题、明天挑战困难题知识结构是散的。按练气十层的顺序系统推进每一层练透了再上一层的题你会发现后续内容都是前面能力的组合越练越顺。我个人的节奏是每过一层就把这一层的核心代码脱离题解默写一遍写不出来就说明还没真正过。算法入门没有捷径但有一条相对顺的路就是这练气十层。一层一层往上走等十层过完回过头看动态规划、图论这些当初觉得高不可攀的东西其实都是地基上自然长出来的。我自己当年也是从冒泡排序一行一行敲过来的那种终于把整段逻辑跑通的踏实感比任何速成都可靠。