今天是算法强化训练的第3天。前两天的学习让我意识到刷题量并不能直接等于算法能力的提升真正拉开差距的是对“为什么用这个算法”的理解。于是DAY3我调整了策略把重心从“刷更多的题”转移到“彻底吃透几个高频算法核心”包括归并排序、KMP、剪枝与贪心思想。这篇文章就是我这一天完整的学习笔记和实操记录包含了原理拆解、代码实现、常见错误、性能实测和刷题路线希望对正在自学算法或者准备面试的朋友有一些参考价值。1. 第三天的学习计划与设计思路1.1 为什么DAY3会选这几个主题如果你有印象很多人的算法学习会卡在第3天到第7天之间。第一天兴致最高第二天还能坚持第三天开始出现“我是不是不适合学算法”的念头。我特意把DAY3安排成“分治 字符串匹配 搜索策略 贪心”的组合就是考虑到这个阶段需要用经典问题来建立正反馈。归并排序是分治思想的典型代表它天然地引导你理解递归、合并、复杂度分析不会像动态规划那样一上来就劝退。KMP则是“字符串匹配”里最有面试价值的算法它看起来复杂但拆开来看就是一套固定的模式掌握之后你会突然理解“预处理”三个字的重量。剪枝和贪心则帮你从“暴力枚举”的思维陷阱里走出来是后面学习深搜广搜和动态规划的衔接点。1.2 DAY3的量化目标比速度更重要的是理解深度我给自己定的目标不是“做完20道题”而是“能不看任何资料独立推导出归并排序和KMP的核心证明”。为什么这么定因为我发现很多人在面试里手写归并能写出来但被问一句“为什么归并排序的复杂度是O(n log n)”就卡住了。这就是典型的知其然不知其所以然。为了量化学习效果我做了一个简单的自测计划自测项考察点达标标准归并排序手写分治框架与边界处理8分钟内无编译错误通过测试用例归并排序复杂度推导递归方程理解能用T(n)2T(n/2)O(n)推出O(n log n)KMP next数组手算前缀后缀理解5个随机串快速给出next数组剪枝案例设计搜索优化意识能说清“什么时候剪是安全的”贪心选择证明贪心正确性分析能说明区间调度为什么按结束时间排序说实话DAY3这一天我学到的最大教训是算法的核心能力不是写代码而是“证明”和“解释”。2. 归并排序分治思想的完整抓手2.1 朴素的排序思路与归并排序的突围排序是所有算法学习绕不开的一块基石。你大概已经见过冒泡排序、选择排序、插入排序这些O(n²)级别的算法它们在数据量小的时候够用可一旦数据量上了十万级别二次方的复杂度会让程序明显变慢。归并排序之所以重要是因为它把排序的时间复杂度降到了O(n log n)而且这个思想可以顺带解决大量非排序问题比如逆序对计数。归并排序的核心逻辑极其简洁先把数组从中间拆成两半分别排序然后再把两个有序数组合并成一个有序数组。这个过程用递归实现每一层都在“分解”到底层每个子数组只有一个元素天然有序然后再一层一层“合并”回去。很多人第一次接触归并排序时觉得递归的流程很绕。我建议用生活类比来理解像整理一副打乱的扑克牌你先把牌分成两叠每叠再分成两叠分到每叠只有一张牌然后从最小的一叠开始两两按顺序合并最终合回一整副有序的牌。核心引擎是“合并两个有序数组”这个基本的操作写熟了归并就拿下一半了。2.2 手写归并排序的完整代码解析下面是我DAY3手写的归并排序代码使用的是经典的“左右闭区间”写法void mergeSort(vectorint nums, int left, int right) { if (left right) return; // 递归终止只有一个元素或空区间 int mid left (right - left) / 2; mergeSort(nums, left, mid); // 排序左半 mergeSort(nums, mid 1, right); // 排序右半 merge(nums, left, mid, right); // 合并两个有序区间 } void merge(vectorint nums, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (nums[i] nums[j]) temp[k] nums[i]; else temp[k] nums[j]; } while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; for (int idx 0; idx temp.size(); idx) { nums[left idx] temp[idx]; } }这里有个细节值得多说一句mid left (right - left) / 2而不是(left right) / 2是为了防止整数溢出。虽然现在的测试数据很少让你碰到溢出边界但这个习惯能在关键时候救你一把。另外我把merge单独抽成函数是为了方便单元测试这种“一个函数干一件事”的风格在代码评审里非常加分。2.3 复杂度推导为什么它稳定是O(n log n)面试官最喜欢追问的问题在这里。归并排序的递归方程写成T(n) 2T(n/2) O(n)含义是排序n个元素的耗时等于排序两个n/2子数组的耗时再加上合并两个有序数组的O(n)开销。怎么解这个递推式用主定理可以直接得到O(n log n)。如果你不想直接背主定理可以用“递归树”的方式画出来第一层有1个规模为n的问题合并耗时n第二层有2个规模为n/2的问题每个合并耗时为n/2总耗时还是n第三层4个问题总耗时还是n……一共log2(n)层所以总耗时就是 n * log2(n)。每一个节点都在做O(1)到O(n)的合并工作整个树形结构非常均衡。归并排序还有一个天然优势是稳定排序因为合并时用了判断相等的元素会优先取左侧数组的值保持了原来的相对顺序。这在处理对象数组的多关键字排序时非常关键。2.4 归并排序的实战演练逆序对数量DAY3我做的最有价值的练习是用归并排序求逆序对数量。题目是剑指Offer 51给定一个数组返回其中逆序对的总数。所谓逆序对就是一对下标(i, j)满足i j且nums[i] nums[j]。如果你用暴力枚举双层循环就能解决复杂度O(n²)。而用归并排序你可以在合并的过程中顺手统计当右侧数组元素nums[j]小于左侧当前元素nums[i]时说明左侧区间里从i到mid的所有元素都比nums[j]大这些都能与nums[j]组成逆序对于是逆序对数量一次加mid - i 1。这个“顺手统计”的技巧太重要了因为它体现了分治算法的高效之处——子问题合并时不仅能得到有序结果还能顺带计算出额外信息。类似的应用还有求数组中的“小和”问题、“翻转对”问题核心套路完全相同。2.5 归并排序踩坑记录我在实操中犯过一个低级错误合并时直接把辅助数组写成了局部变量并在每次递归里重新创建。小数据量看起来没事但数据量一上来频繁构造vector的开销会拖慢整体性能。优化方式有两种一是把辅助数组定义在递归函数外作为参数传递二是使用std::vector::reserve预留空间。实测下来复用辅助数组的性能提升非常明显。另外一个常见错误是边界写错。比如递归终止条件写成left right而不是left right虽然也能跑但会多一层的无意义递归。再有就是合并完忘记把临时数组拷贝回原数组这一步漏了整个递归过程就全乱了。我调试了很久才发现最后总结出一个习惯任何跟区间有关的算法先把“左闭右开”还是“左闭右闭”确定下来再写代码。3. KMP算法从next数组到字符串匹配实战3.1 为什么要放弃暴力匹配KMP算法是字符串匹配领域的经典算法。它的目标很单纯给定一个文本串和一个模式串找出模式串在文本串中出现的所有位置。朴素做法是从每个位置开始逐个字符比较时间复杂度O(n * m)其中n是文本长度m是模式串长度。当文本和模式串都很长时这个复杂度非常尴尬。KMP的核心思想是把已经匹配过的信息利用起来匹配失败时让模式串跳转到合适的位置继续而不是从头再来。要知道暴力匹配最痛苦的地方在于明明已经比了前五个字符都相等第六个不相等结果指针就要退回到第二个字符重新开始之前五次的比较工作全部作废。KMP就做了一件事记住模式串内部的前后缀关系失败时向右移动尽可能多的距离。很多人觉得KMP的难点在于理解next数组但实际上next数组没那么玄它就是模式串每一个前缀里“最长的相等真前后缀的长度”。这个词听起来绕我拆开解释假设模式串是ABABC看前缀ABAB它的真前缀有A、AB、ABA真后缀有B、AB、BAB相等且最长的是AB长度2那么对应位置的前缀函数值就是2。3.2 手动构造next数组一个简单可靠的方法我在DAY3提出了一个“理解优先代码在后”的学习顺序。先拿一个具体例子手算next数组再写代码验证。以模式串ABABCABAB为例前缀最长相等前后缀长度A无0AB无0ABAA1ABABAB2ABABC无0ABABCAA1ABABCABAB2ABABCABAABA3ABABCABABABAB4手算流程很机械对每个前缀从最长的真前后缀开始尝试一点点缩短直到找到相等的情况。等你对“最长相等前后缀”有了手感之后再来看代码。3.3 KMP的完整代码实现KMP的代码分为两步构建next数组以及用next数组做匹配。// 构建next数组 vectorint buildNext(const string pattern) { int m pattern.size(); vectorint next(m, 0); int len 0; // 当前最长相等前后缀长度 int i 1; while (i m) { if (pattern[i] pattern[len]) { len; next[i] len; i; } else { if (len ! 0) { len next[len - 1]; } else { next[i] 0; i; } } } return next; } // KMP匹配 vectorint kmpSearch(const string text, const string pattern) { vectorint result; int n text.size(), m pattern.size(); if (m 0) return result; vectorint next buildNext(pattern); int i 0, j 0; while (i n) { if (text[i] pattern[j]) { i; j; } else { if (j ! 0) j next[j - 1]; else i; } if (j m) { result.push_back(i - j); j next[j - 1]; // 继续寻找下一个匹配位置 } } return result; }这段代码我一开始写的时候被递归式的len next[len - 1]弄晕过。后来我用一个生活类比帮助自己理解这就像你在看一本书时某句话没看懂你不会翻回第一页重看而是翻回到“上一个关键节点”继续推敲。len next[len - 1]做的事情就是回溯到“当前已匹配前缀的最长相等前后缀长度”处继续尝试而不是完全归零。3.4 时间复杂度到底怎么算KMP的时间复杂度严格说是O(n m)这点常常被误解成O(n*m)或者O(nm)只适用于最好情况。为什么O(n)因为指针i从不回退始终向右移动为什么O(m)因为next数组构建中len最多增加m次、回退m次。当你把匹配过程和next构建看成两个独立的线性过程时总复杂度就是O(nm)。我在自己的检查清单里记了一条如果你在面试中写KMP一定要主动讲出“i指针永不回溯”这个关键点这句话往往就是面试官给你加分的转折点。很多人光写了代码但讲不清楚原理容易印象分低。3.5 一个直观的匹配案例模式串ABABCABAB文本串ABABDABABCABABABABC用上面的代码匹配核心流程是文本串的第0位和第1位匹配成功到第3位时模式串匹配到ABAB之后的C与文本的D不相等于是j next[3] 2模式串跳到第三个字符A重新开始比对。这一步把你的视线瞬间从文本串的第4个字符拉回到了模式串内部的2号位置省掉了从文本第1位开始的重复比较。实际测试下来这段代码在长文本里匹配效率非常高尤其模式串本身长、文本串里重复模式多的时候优势比朴素匹配成倍放大。3.6 扩展从KMP到Boyer-Moore和AC自动机KMP解决了单模式串匹配但工程上更常用的是Boyer-Moore算法常用于文本编辑器查找、Sunday算法实现简单等。多模式串匹配则要用AC自动机它本质上是KMP思想在Trie树上的扩展。你在理解KMP之后再看AC自动机会感觉豁然开朗因为fail指针的作用和next数组几乎一模一样。我在DAY3并没有深入AC自动机但这份笔记给自己留了一个延伸方向多模式匹配的搜索引擎索引构建场景会非常依赖这些算法的变体。4. 剪枝、贪心与A*三种优化思想的统一视角4.1 暴力枚举为什么会失效如果你刷过一定量的递归题会发现自己一开始的解法往往都是搜索所有的可能性然后选出正确答案。这种“暴力枚举”在数据范围小的时候完全可行比如一个问题的状态空间只有几百个枚举一遍可能只要几毫秒。可问题是很多真实问题的状态空间是组合爆炸级别的枚举全部状态在时间上不可行。于是“剪枝”出现了。剪枝的意思是在搜索过程中一旦确定某个分支不可能产生最优解或合法解就立刻停止沿着这个分支继续往下走。它不是在改变问题的解而是在缩小搜索空间。举一个经典例子求一个数的所有因数分解方案比如12可以分解成2*2*3、3*4等。如果当前已经选定了一个较大的因数后续再选另一个更大的因数时乘积必然超过目标值此时可以直接剪枝不用往下递归。这类剪枝叫做“可行性剪枝”。还有一种叫“最优性剪枝”常见于最优化问题当前部分解的代价已经超过已知最优解那这个分支没必要继续。4.2 记忆化搜索与剪枝的边界初学者很容易混淆剪枝和记忆化搜索。剪枝是在递归树的某个节点直接放弃整个子树记忆化搜索则是把某个状态的结果存下来下次遇到相同状态直接用。前者抛弃的是“不可能得到答案”的路径后者复用的是“已经算过”的路径。二者的目的一样避免无效计算但适用场景不同。我DAY3做了一道典型的剪枝题组合总和III要求从1到9的数字中选出k个数使它们的和为n每个数字只能用一次。用回溯法枚举时如果累计和已经大于n就立刻剪枝返回。这道题配合排序还能做进一步的“提前剪枝”如果剩余可选数字的最小和都超过剩余目标同样可以提前停止递归。实测下来剪枝后耗时从几十毫秒降到几毫秒效果非常显著。4.3 贪心每一步都选当下最优真的靠谱吗贪心算法听起来像是“最偷懒”的算法因为它的策略极其简单每一步都选择当前看起来最优的选项不回头、不后悔。贪心最难的地方不是写代码而是判断当前问题能不能用贪心。如果一个问题满足“贪心选择性质”和“最优子结构”那么贪心才是安全的。我DAY3练手的是经典区间调度问题给定一组区间计算最多能保留多少个互不重叠的区间。贪心策略是“按区间结束时间从小到大排序每次选择结束最早且与之前选择不冲突的区间”。为什么按结束时间排序而不是按开始时间因为结束得早留给后续区间的空间就更大这是最直观的“当下最优”选择同时可以通过交换论证证明它是全局最优的。这个“交换论证”的方法建议每一个学贪心的人都要熟悉它是证明贪心正确性的核心工具。4.4 A*算法的统一视角启发式搜索的剪枝思想热搜词里出现了a*算法、a*算法原理图我顺势把A也纳入了DAY3的思考范围。A本质上是对搜索树的“最优性剪枝”加“启发式引导”它每次从待扩展节点中选出f(n) g(n) h(n)最小的节点来扩展其中g(n)是从起点到当前节点的实际代价h(n)是从当前节点到终点的估计剩余代价。h(n)不能高估真实代价否则无法保证找到最优解这是A*算法的重要前提。如果你理解了这个框架再看普里姆算法、Dijkstra算法会发现它们都是A的特例Dijkstra相当于h(n)0的A而带启发式信息的搜索可以大幅减少访问节点数。所以我把剪枝、贪心、A*放到同一天来学因为它们本质上都是“利用已知信息减少无用计算”的思路。DAY3我还练了一道迷宫寻路的A实现题启发函数选了曼哈顿距离。对比纯BFSA在空旷地图上访问的节点数量少了一半以上。地图越大这种差距越明显。不过要注意A*的空间开销也更大因为需要维护Open表和Closed表这点在嵌入式地图场景里需要权衡。4.5 贪心算法在面试中的三个常用套路面试里贪心题的高频考法主要是区间调度、跳跃游戏、分发饼干、股票买卖时机。这些题看上去千变万化实际上核心策略都围绕着“排序、双指针、优先队列”三个工具展开。比如跳跃游戏II你需要在每一步计算当前能跳到的最大位置本质上也是“贪心选择最远的可达点”。这类题我总结了一个分析模板先猜一个贪心策略然后尝试构造反例再用交换论证或归纳法验证。如果反例构造了半天都找不到那大概率策略是对的别急着证明先把代码写出来跑测试用例。证明的事情可以推后但思考路径要完整。5. DAY3刷题实录与常见问题速查5.1 今日刷题清单与收获为了让你对DAY3的学习密度有直观感受我把完成的题目和对应的考点整理成了一张表题目考点我的完成时间复盘结论LeetCode 912 排序数组归并排序/快排6分钟边界还需注意剑指Offer 51 逆序对归并排序应用12分钟核心技巧是mid-i1LeetCode 28 找出字符串中第一个匹配项的下标KMP15分钟对next数组的含0问题加深理解组合总和III回溯剪枝10分钟剪枝能极大提速无重叠区间贪心区间排序8分钟排序策略是关键这份清单不是让你照抄而是展示一个DAY3应该有的密度既有基础排序又有进阶应用还有字符串与搜索策略。这种“同一天覆盖多个重点方向”的安排适合已经有两三天基础的人参考。如果完全零基础建议把归并排序和KMP分成两天来学贪心可以放到第4天。5.2 常见报错与排查思路学习过程中我踩了坑也整理了其他学习者常遇到的问题做成一个速查表症状可能原因解决办法归并排序结果部分有序但整体错乱合并后忘记拷贝回原数组检查for回填逻辑递归栈溢出递归终止条件错误确认left right提前返回KMP匹配遗漏重叠匹配找到一次匹配后直接结束匹配成功后执行j next[j-1]继续查找next数组值全部为0相等判断写成了pattern[i] pattern[j]而不是len检查循环里的索引变量回溯题超时缺少剪枝分析状态空间增加可行性剪枝和最优性剪枝贪心题得到错误答案贪心策略错误尝试构造反例验证是否满足贪心选择性质区间重叠判断错误对“端点相接”处理方式不一致明确条件lastEnd currentStart是否允许相接5.3 关于“算法工程师面试”的一点切身体会热搜词里有一个是“算法工程师面试”DAY3我特意花了一个小时研究面试中算法考察的重点分布。从各大公司近年的真实面经看排序和字符串匹配属于“热身题”真正的区分度在后面动态规划、图论、系统设计。但热身题的意义在于它能在前五分钟里决定面试官对你的技术印象。我见过太多候选人能快速讲懂Transformer却在手写归并排序时思路混乱。我的建议是准备面试前先把基础排序、二分查找、链表操作、二叉树遍历这四类问题做到“肌肉记忆”级别再谈深度学习或机器学习项目。因为在大多数面试中算法题是最可控的筛选指标你不会希望在“最简单的归并排序”这里失去主动权。5.4 下一个DAY4的预习路线按照我的个人学习规划DAY4应该进入动态规划的初步。动态规划里的“最优子结构”和“状态转移方程”与今天学的贪心、分治有着天然的连续性。比如当你理解了“分治是自上而下拆分动态规划是自下而上填表”之后就会明白为什么很多问题既可以用递归加记忆化解决也可以用迭代的DP解决。我给DAY4预留的预习题目包括爬楼梯、打家劫舍、最长递增子序列、编辑距离。这几道题覆盖了DP最核心的一维和二维状态定义方式也衔接了今天贪心题里出现的“选与不选”逻辑。如果你也在自学算法不妨和我一起在DAY4做这几个题然后把对比心得写在留言区。另外我还想做一个小的代码仓库把DAY1到DAY3的练习代码全部整合成一个包含单元测试的项目。这样后续复习时跑一遍测试就能快速校验自己有没有遗忘关键点。结语DAY3教会我的三件小事算法训练到第三天我最真实的收获不是“会写归并排序”或者“能背出KMP的next数组”而是重新理解了学习的节奏。第一件小事一个算法真正学会的标志是你能把它的证明过程讲给自己听。第二件小事刷题量只是输入复盘才是转化做5道题然后深度复盘一道比做20道题不回头更有效。第三件小事卡住的时候不要死磕超过30分钟去写一写最简单版本的暴力解往往思路就通了。今天的笔记就写到这里了。代码和详细扩展都在我本地的工程目录里。如果你也处在算法学习的前期阶段希望这篇DAY3记录能给你一点参考。后面我还会继续更新DAY4、DAY5的内容把动态规划和图论的实战记录补上来保持同样的节奏原理、代码、踩坑、复盘。