三四年前我集中复习算法的时候最困惑的一点是每一类算法单独看都懂分治、排序、线性选择、动态规划、回溯、贪心、并查集、最小生成树、线段树、二维矩阵查询这些名字都能说上几句但题目一旦换个包装我就不知道怎么下手。后来我把这十类内容从“背模板”改成“按问题类型拉通梳理”才真正建立起一套解题的主线拆分问题用什么、决策问题用什么、连通关系用什么、区间统计用什么。这篇博文就是我那段时间沉淀下来的完整笔记从核心思想、典型习题到踩坑记录都会讲到。不想堆推导重点放在“什么时候用它、核心步骤是什么、容易错在哪”适合正在准备面试、想系统补一遍算法基础或者刷题遇到瓶颈的同学参考。1. 先看全景这十类经典算法到底在解决什么问题1.1 一个观察算法背后的四类问题模型如果把所有经典算法按“要解决的问题类型”重新分组会发现它们其实只干四件事拆解型问题分治、排序、线性选择共同点是“把大问题切成小问题分别处理再合并”。决策型问题动态规划、回溯、贪心共同点是“在多个选择里找最优解或可行解”。关系型问题并查集、最小生成树共同点是“维护元素之间的连通性、分组关系”。区间型问题线段树、二维矩阵查询共同点是“对连续区间或矩形区域做快速统计与更新”。这四类正好对应了笔试和面试里最高频的几类题目形态。我之前见过很多同学把每个算法当成孤立的模板去背结果遇到综合题就蒙。真正的学习方式应该是反向的先判断题目属于哪一类问题再决定用哪个算法组合。这套分类还有一个额外好处帮你建立“题感”。看到“给定一个数组支持区间求和和单点修改”第一反应是线段树方向看到“若干操作每次判断两个元素是否在同一集合”第一反应是并查集方向。这种映射关系建立得越早刷题效率越高。1.2 数据规模是第一道筛子很多人在选择算法时忽略了最关键的信息数据范围。数据规模直接决定了算法的复杂度上限。我一般习惯用下面这个经验表快速筛选数据规模大致可用复杂度常用算法n ≤ 20O(2^n)二进制枚举、回溯n ≤ 1000O(n^2)两层循环DP、简单排序n ≤ 10^5O(n log n)快排/堆排、线段树、Kruskaln ≤ 10^6O(n)线性选择、前缀和、计数排序注意这不是死规矩只是一个粗略的筛子。实际做题时还要看时间限制和常数大小比如同样是O(n log n)线段树常数比树状数组大不少但可处理的问题范围也更广。我踩过最典型的坑是看到一道“求区间最大值”的题数据规模只有1000却硬写线段树代码长了三倍还不一定写得对。后来养成习惯动笔前先看一眼输入规模再决定是暴力还是上数据结构省下来大量时间。1.3 推荐的学习顺序我比较推荐按“从简到繁、从基础到复杂”的顺序学分治与排序先行因为它们是递归和复杂度的基础然后是线性选择理解随机化和期望复杂度接着是动态规划和回溯掌握决策类问题的建模再学贪心理解局部最优和全局最优的关系之后进入图论方向的并查集和最小生成树最后啃线段树和二维矩阵查询这类区间数据结构。这个顺序有一个好处每一步用到的前置知识都在前一步刚学过。比如Kruskal依赖并查集二维前缀和依赖基础的动态规划思想前后衔接很顺不会出现学到一半发现基础缺一块的情况。2. 分治、排序与线性选择把数组玩明白2.1 分治法分解、解决、合并分治法的核心就三步分解原问题、递归解决子问题、合并子问题的解。听起来简单但在实际写代码时最容易漏掉的恰恰是第三步“合并”。拿归并排序举例分解和递归解决是固定的模板真正决定算法正确性和性能的是合并时如何把两个有序数组合成一个以及在合并过程中是否能顺带做一些额外统计。最经典的例子是“求数组中的逆序对”在合并两个有序子数组时只要发现右边数组的某个数比左边小那么左边数组剩余的所有数都比它大逆序对数量直接加上mid - i 1。这一步就是在合并过程中偷摸完成了统计时间复杂度保持在O(n log n)。如果只顾着递归下去忘了合并时的统计逻辑整个算法的输出必然错。这个坑我印象很深当时写出来跑小样例全对一换大数据就乱最后发现是合并函数里少维护了一个指针。主定理也是分治绕不开的内容它专门处理形如T(n) aT(n/b) O(n^d)的递推关系。按照n^log_b(a)和f(n)的大小关系分成三种情况直接代入就能得到复杂度。但要注意它只适用于这种标准形式像T(n) 2T(n/2) n log n这种直接套主定理会翻车需要用递归树展开才能算准。除了归并排序二分查找、快速幂、最大子数组和的分治解法也都值得单独写一遍。分治思想表面上简单但要做到“看到问题能主动想到拆成两半”需要反复练。2.2 排序算法选型没有银弹排序是整个算法体系的基础几乎每个工程师都能写出一种排序但真正问起“什么场景用哪种”很多人答不上来。先看一张对比表算法平均复杂度最坏复杂度稳定性额外空间快速排序O(n log n)O(n^2)不稳定O(log n)归并排序O(n log n)O(n log n)稳定O(n)堆排序O(n log n)O(n log n)不稳定O(1)插入排序O(n^2)O(n^2)稳定O(1)计数排序O(n k)O(n k)稳定O(k)工程语言的内置排序几乎没有单纯用某一种排序的。比如很多标准库的排序是“混合排序”数据量小的时候切到插入排序因为插入排序在小规模数据上有极低的常数递归深度超过阈值时切到堆排序避免快排退化到O(n^2)中间过程用三数取中选枢轴的三向切分快速排序。这种工程上的混合策略正是大家常说的“没有银弹”的体现。面试里排序题的变形比排序本身更重要。高频的几类是按颜色分组排序相当于只有0、1、2三种值用三个指针一趟搞定。合并多个有序数组经典解法是优先队列本质是归并思想的扩展。求排序后相邻元素最大差值突破口是桶排序把n个元素放进n1个桶最大差值必然跨越桶之间。我自己的建议是快排、归并、堆排都手写一遍不是为了面试时默写而是为了理解“分治”和“数据结构”在排序中各自承担的角色。写多了之后会发现很多非排序题目最终也能转化成熟练的排序思路。2.3 线性选择第K小/大的两条路线线性选择要解决的是“在一个无序数组里找第K小元素”。最容易想到的是先排序再取下标时间复杂度O(n log n)。但存在专门的算法可以做到期望O(n)甚至最坏O(n)。第一条路线是快速选择也就是Quickselect。它利用快速排序的partition思想随机选一个枢轴把数组分成小于、等于、大于三部分然后判断第K小落在哪部分只递归那一部分。因为每轮平均丢弃一半数据期望时间复杂度是O(n)证明了为什么随机化对这类算法如此重要。import random def quickselect(nums, k): # k为0-indexed即第k小的数 if not nums: return -1 pivot random.choice(nums) left [x for x in nums if x pivot] mid [x for x in nums if x pivot] right [x for x in nums if x pivot] if k len(left): return quickselect(left, k) if k len(left) len(mid): return pivot return quickselect(right, k - len(left) - len(mid))如果数组里有大量重复元素三路划分这个细节就很重要只做两路划分时可能会在重复值上反复递归退化成O(n^2)。第二条路线是BFPRT算法也叫“中位数的中位数”算法。它通过递归选取一个质量有保证的枢轴确保每次至少去掉固定比例的数据从而让最坏复杂度稳定在O(n)。问题是它的常数非常大工程上很少有人真用它更多是作为理论上的里程碑来理解。我在实际刷题中只用Quickselect随机枢轴基本不会触发最坏情况。注意“第K大”和“第K小”之间不要搞混直接转成k_small len(nums) - k_large再进函数思路就清晰了。3. 动态规划、回溯与贪心三类决策问题怎么选3.1 动态规划状态、转移、边界三件套动态规划是大部分人算法路上的第一道坎也是面试最常考的大类。我习惯把它拆成三件套每道题都按这个顺序写一是状态定义。这是整个DP的灵魂状态定义得好转移方程自然就顺状态定义得差后面怎么优化都别扭。比如0-1背包定义dp[i][j]为前i个物品在容量j下能获得的最大价值这个二维状态把“物品数”和“容量”两个维度都覆盖了后面所有的转移都围绕它展开。二是转移方程。0-1背包的方程很经典dp[i][j] max(dp[i-1][j], dp[i-1][j-w] v)含义是“不放第i个物品”或“放第i个物品取较大值”。这里有一个容易出错的地方内层循环为什么有时候要倒序遍历因为滚动数组复用了一维空间倒序可以保证每个物品只被使用一次这是完全背包和0-1背包实现上的关键区别。三是边界初始化。很多人写对了状态和转移却在初始化上丢分比如求最小值时初始化成0导致转移永远选到未更新的状态或者背包容量为0的情况没有单独处理。初始化不是随便填一遍而是要回到状态定义本身问自己“一个物品都不拿、容量为0时答案是多少”。DP的经典题型远不止背包最长递增子序列、最长公共子序列、编辑距离、最大子数组和都值得反复练。其中最大子数组和的Kadane算法是一个很好的特例它本质上是DP但通过滚动变量把空间复杂度压到了O(1)非常适合用来体会“优化”是怎么发生的。DP和记忆化搜索是同一个思路的两种写法一个自底向上迭代一个自顶向下递归。我在面试中经常先用记忆化搜索理清状态结构确认无误后再改成迭代DP拿更好的性能表现。3.2 回溯算法显式穷举加剪枝回溯算法是解决“排列、组合、子集”这类问题的万能钥匙本质是DFS加状态回退。它的标准模板是三个部分当前路径、可选列表、终止条件。写代码的框架基本都是同一个def backtrack(path, choices): if 满足终止条件: 记录结果 return for 选择 in choices: 做选择标记使用 backtrack(path, choices) 撤销选择恢复标记这个模板解决全排列时需要维护一个used数组防止同一个元素被重复使用解决组合问题时需要用start索引保证每次只从当前元素之后选择避免出现重复组合。这两者如果混了代码可能连样例都过不了。去重是回溯的一个高频易错点。典型场景是“数组中有重复元素求所有不重复的排列组合”。解决办法是先排序然后跳过相邻且前一个相同元素已经被撤销的分支。用一句话总结就是“同一层不重复选同一个值不同层可以选相同的值”。这个规则我一开始总是记反后来把所有回溯题都按这个逻辑走才稳定。剪枝决定了回溯能不能过大数据。N皇后、数独这类题目纯穷举根本跑不完必须提前判断某条分支是否还有可能产生合法解不行就直接return。另一个实用的剪枝是排序预判组合总和问题里先把数组排序一旦累计和超过目标就立刻停止这条分支效率能提升一个量级。回溯和动态规划最大的区别在于回溯是无脑穷举所有分支动态规划则通过重叠子问题的记忆化去掉重复计算。一个需要返回所有具体方案的题目基本只能回溯一个只需要返回最优值或方案数的题目优先考虑DP。3.3 贪心算法先证明再使用贪心是所有算法里“看起来最简单、实际最危险”的。策略往往一句话就能描述比如“每次都选结束时间最早的活动”但难点在于怎么证明这个局部最优能推出全局最优。我见过的有效证明手法是交换论证。以活动选择为例假设某个最优解的第一个活动不是结束时间最早的那把最优解的第一个活动替换成结束时间最早的剩余活动的可安排空间不会变小所以存在一个包含最早结束活动的全局最优解。用这种方式不断替换就证明了贪心策略的正确性。典型贪心题大致有几类区间调度按结束时间排序每次选最早结束的活动。跳跃游戏维护当前能跳到的最远位置遍历时不断更新直到覆盖终点。分发饼干两个数组都排序双指针满足小的胃口。柠檬水找零优先用10元找零把5元留下来应对后面更麻烦的场景。这些题的共同特点都是局部最优策略不会影响后续的选择空间或者听了之后反而扩大了后续可能性。如果在题目中找得到反例说明它不能贪心大概率需要动态规划。0-1背包就是个经典反例——局部最优地拿单位价值最高的物品会破坏剩余容量的整体规划。我自己的经验是判断能否贪心先试着构造反例。构造不出来再考虑贪心一旦用贪心写了必须花两分钟想清楚证明逻辑而不是抱着“感觉对”的心态提交。这个习惯救了我很多次。4. 并查集与最小生成树连通性问题的黄金搭档4.1 并查集路径压缩与按秩合并并查集解决的是“动态维护若干个集合、并快速判断两个元素是否属于同一集合”的问题。它有两个核心操作查找find和合并unite。find的路径压缩本质是把每个节点直接挂到根节点下面让后续查找几乎一步到位。unite的按秩合并保证每次都把矮树挂到高树上避免树退化成链表。两个优化都做时单次操作的均摊复杂度是反阿克曼函数基本可以视为常数级。int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int x, int y) { x find(x); y find(y); if (x y) return; if (rank[x] rank[y]) swap(x, y); parent[y] x; if (rank[x] rank[y]) rank[x]; }代码很短坑却不少。第一个坑是递归路径压缩可能爆栈如果数据量非常大、树深度又深可以改成迭代写法。第二个坑是合并之前必须分别find有人直接parent[y] x挂过去导致集合关系完全错乱。第三个坑是初始化时一定要写parent[i] i否则每个元素一开始都找不到自己的根。并查集的应用范围很广判断图中是否存在冗余连接、统计连通分量数量、实现朋友圈分组。它和深度优先搜索、广度优先搜索都能解决“图里有多少个连通块”这类问题但并查集最大的优势是支持动态加边不需要每次重跑一遍全图。带权并查集是在普通并查集基础上额外维护每个节点到根节点的权值解决“区间和是否矛盾”这类问题时特别顺手竞赛里很常见。4.2 最小生成树Kruskal和Prim怎么选最小生成树的目标是选出一个边集让整个图连通且总权重最小。两种经典算法各有各的适用场景。Kruskal的流程是把边按权重从小到大排序依次尝试加入生成树用并查集判断加入后会不会成环不成环就加入。它的复杂度是O(E log E)瓶颈在排序边的数量主导一切。Prim的思路则是从任意一个顶点开始维护一个候选边集合每次选出连接已选集合和未选集合的最小边优先队列优化后复杂度是O(E log V)。对比维度KruskalPrim堆优化核心依赖并查集优先队列复杂度O(E log E)O(E log V)实现难度较低中等适合场景稀疏图稠密图实际做题时稀疏图用Kruskal更简单直接边排序后遍历就行稠密图用Prim性能更好。但工程上很多最小生成树的题只要不是极端数据两个都能过所以不必在选型上太纠结。正确性证明统一依赖切割定理把图分成两个非空集合横跨这两个集合的最小边必然属于某个最小生成树。这个定理也是理解Kruskal和Prim为什么每次选最小边都安全的关键。最大生成树就更简单了把排序规则反过来或者边权取负数算法骨架完全不变。典型应用场景是“让所有节点连通的最小代价”比如网络布线、道路修建这类题目往往只是最小生成树的朴素套壳识别出来就好做。5. 线段树与二维矩阵查询区间数据结构的重武器5.1 线段树构建、查询、更新与懒标记线段树解决的是“一个数组支持区间修改和区间查询”的场景。常见的操作包括区间求和、区间最值、区间加一个数。它本质上是一棵基于数组下标的平衡二叉树每个节点存储一个区间对应的聚合信息。构建线段树的时间是O(n)单次查询和单点更新的时间复杂度都是O(log n)。实现上普遍用堆式存储开一个大小为4n的数组。为什么是4n不是2n因为线段树是一棵近似完全二叉树最坏情况下最后一层节点数接近2n加上内部节点4n才足够安全。很多人第一次开2n然后越界调半天才发现空间开小了。节点存储的聚合信息决定了它能处理什么类问题。区间和的节点存区间总和区间最值的节点存最大值和最小值。如果只涉及单点更新代码很简洁一旦涉及区间更新就必须引入懒标记。懒标记的精髓是“先记账不干活”更新一个区间时如果当前节点区间被完全覆盖就不再往下递归直接把值累加到节点上并打一个标记等到后续查询或更新必须深入子区间时才把标记下传给子节点。没有这个优化区间更新退化成逐个点更新复杂度会退化到O(n log n)甚至更高。懒标记的坑集中在标记下传的时机。我只写了一遍查和更新的版本测试小样例没问题但换了区间加法再套区间求和的场景就全错后来发现是查询时没有先把懒标记推到子节点导致子节点数据是旧值。凡是涉及父节点信息和子节点数据之间存在依赖的题目都得在递归前先执行pushdown。线段树的应用非常广动态区间和、滑动窗口最值、权值线段树查第K小都能做。它还区分递归实现和迭代实现后者通常叫zkw线段树常数更小但理解和调试成本更高我建议先掌握递归写法遇到性能瓶颈再考虑迭代。5.2 二维前缀和与二维差分O(1)统计矩形区域二维矩阵查询里最基础也最常用的是二维前缀和。它解决的是“静态矩阵上频繁查询某个子矩阵的元素和”这类问题。构建二维前缀和数组的递推公式是S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]这个公式用了一个非常典型的容斥思想加两个一维前缀再减去左上角被重复加的那一块。构建时按照行从上到下、列从左到右的顺序递推时间复杂度O(n*m)。查询子矩阵和的公式是对称的容斥过程sum(x1, y1, x2, y2) S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]其中(x1,y1)是子矩阵左上角(x2,y2)是右下角。这个公式能把单次查询降到O(1)在大量重复查询的场景下性能优势非常明显。与之配套的是二维差分它是二维前缀和的逆运算用于处理“多次给某个子矩阵的所有元素加同一个值最后求最终矩阵”的问题。二维差分的更新需要在四个位置打标记d[x1][y1] val d[x21][y1] - val d[x1][y21] - val d[x21][y21] val最后对差分数组做一遍二维前缀和就还原出每个位置的真实值。这里的下标边界非常容易出错尤其当坐标从1开始时x21和y21可能越界数组需要多开一行一列。我在实际练习中犯错最多的就是下标被搞混矩阵从1开始还是从0开始公式里的x1-1、x21是否仍合法。建议第一次做这类题时先画一个3x3的小矩阵手动推一遍容斥方向和边界确认无误再上代码能省下大量调试时间。6. 刷题路线与常见问题排查6.1 三个阶段的刷题路线算法知识的吸收不能只靠看书必须有节奏地做题。我把自己的学习过程划分成三个阶段每个阶段目标不同、方法也不同。阶段一是分类突破期。这一阶段按算法专题刷题刚学完分治就连续做归并排序相关的题刚学完DP就只做DP的题。目标是让每种算法形成肌肉记忆核心模板能默写看到题目至少能匹配到所属类别。每个专题至少做十道题不要贪快做完之后把模板和经典题解法记录到自己的笔记里。阶段二是混合实战期。这个阶段做题不再标注算法标签拿到的是一道只有题面的裸题。拿到题目之后先自己判断用哪个算法再动手写。这个转变很重要因为面试里没人告诉你“这题用动态规划”。如果判断不出来就试着从数据规模、问题形式、是否存在重叠子问题等维度倒推。阶段三是限时模拟期。按真实面试的节奏卡时间做题一道题只给自己二十分钟思考时间到没思路就直接看答案并复盘。复盘重点不是看懂解法而是找出自己卡住的环节是状态定义没想清楚还是边界条件漏了还是被某个常见套路迷惑了。把每次卡壳的原因记录到同一个文档里后期针对性训练。我见过不少刷题很多但进步缓慢的例子核心问题都是用阶段二的方法做阶段一的题每道题都想半天想不出来然后看答案。这其实是低效的专题突破期就应该允许自己“看着模板写”先把正确率提上来再追求脱离提示独立完成。6.2 常见报错与排查速查表算法题调试和写业务代码有点不一样问题往往不是功能逻辑没跑通而是性能、边界、内存这一类细节。我把高频问题整理成了速查表症状常见原因排查方向运行超时复杂度超标检查数据规模看是否有不必要的循环嵌套递归栈溢出递归层数过深改写成迭代或者增加递归深度限制数组越界下标未检查打印中间索引检查差一错误答案边界差1二分/前缀和的边界处理用最小数据集手算内存超限数组开得太大或重复存储考虑滚动数组、压缩状态超时是最常见也最让人头疼的。遇到超时先别急着优化常数回头数一下复杂度。如果数据规模是10^5你的解法是O(n^2)那不管怎么压常数都过不了必须换思路比如把二层循环改成前缀和或数据结构。数组中越界问题在二维矩阵和线段树题目里尤其多几乎每次越界都是下标定义不统一导致的。我的建议是全局统一一个取下标约定要么都用0-indexed要么都用1-indexed不要在同一个函数里混用两套规则。另一个容易出问题的点是小数据例子不够。很多人只测试了题目给的那个样例就交结果边界条件全是暗坑。我习惯准备一套固定的“冒烟测试”输入空数组、只有一个元素、全是重复元素、最大值。这些极端数据往往能暴露大部分边界问题。6.3 三条让我受益最多的实操心得说了这么多经典算法和习题最后分享三条我自己在实战中反复验证过的实操心得。第一所有模板必须手敲而且要敲三遍以上。复制粘贴的模板不可能变成自己的只有默写过程中卡壳的地方才真正暴露理解的缺口。我当年学并查集连续默写三遍之后才彻底想明白路径压缩的递归过程。第二做错题之后不要只改一个答案要定位到具体的算法知识维度。比如动态规划题做错是状态定义错了还是转移方程漏了一种情况还是初始化不对只有定位到维度才能补上对应的知识盲区否则下次遇到同类型问题还会错。第三每次做完一道题去讨论区看别人的复杂度分析和不同解法。刷题不只是为了“过了”还是为了建立自己的复杂度直觉和算法库。一道题能想出暴力解、数据结构优化解和最优解远好过三题每题只有一种解法。这套学法的反馈循环很重要做题过程中遇到问题先看自己栽在哪个环节然后回到对应的知识模块重新补带着问题再刷下一批题。几次循环下来经典算法这十类内容就不再是孤立的知识点而是变成了一套有结构、能迁移的问题解决框架。最后再分享一个小技巧刷题时给每类算法画一个简洁的“关键词触发清单”比如看到“区间查询、单点更新”就联想线段树看到“动态判断连接关系”就联想并查集看到“最大/最小值且可选多次”就联想动态规划。这个清单不复杂但它能帮你在看到题面的前几秒就锁定方向大幅缩短思考时间。把它写下来贴在电脑边比你再多做二十道题更顶用。