这篇笔记是《算法笔记》系列的第五篇。前四篇我把数组、链表、哈希表、滑动窗口这几个专题捋了一遍这次终于轮到二分查找了顺便把最近参加 LeetCode 周赛 430 的复盘和《热门100题》的刷题路线一起整理进来。如果你正在刷 LeetCode尤其是卡在二分边界、找不到题目突破口、或者想系统规划刷题路线的这篇应该能帮上忙。这期内容以 LeetCode 875“爱吃香蕉的狒狒”为核心题解同时把二分答案这一类题的识别方法和模板一次讲透再结合周赛实战聊聊怎么用限时训练反哺日常刷题。1. 本期主题拆解为什么第五篇要集中啃二分查找1.1 二分查找不是背模板而是识别“单调性”很多人一看到“二分查找”四个字脑子里就是left、right、mid然后开始背边界条件。但刷到后面你会发现二分真正考察的不是边界怎么写而是你能不能在一道题里看出“答案可以二分”。LeetCode 上的二分题表面上分几类有序数组里找目标值、旋转数组里找最小值、在值域上二分答案。前两类是“在一堆已经排好序的数里找东西”套路相对固定第三类才是拉开差距的地方典型代表就是 875 题“爱吃香蕉的狒狒”。这类题有个共同特征题目要求你求一个“答案值”而这个答案值的可行性与一个单调变化的量挂钩。狒狒每小时吃的香蕉速度 K 越大吃完所有香蕉花费的总时间就越短这就是一个单调递减关系。只要存在这种单调性就可以在答案的取值范围内做二分——二分的是 K 的取值而不是题目给你的数组下标。判断一道题能不能用“二分答案”我在笔记里给自己定了三个硬标准第一答案有明确取值区间不可能是无限范围第二存在验证函数给定一个候选答案能快速算出是否可行第三验证结果随候选答案单调变化。三个条件都满足别犹豫直接往二分上想。这比看到“最小化最大值”“最大化最小值”这些词再去猜模板要靠谱得多因为很多题根本不会给你这么明显的提示。1.2 二分的三个易错点虽然二分逻辑简单但写起来容易出问题我自己的笔记里专门整理了一个避坑表每次写完都对着检查一遍。易错点典型表现解决思路中点计算溢出left right在 Java、C 里可能超出 int 范围用mid left (right - left) / 2或(left right) 1死循环同样是left right的循环更新left mid时可能永远走不出来当分支里有left mid时mid必须向上取整mid left (right - left 1) / 2答案差 1最后返回left或right边界搞混导致结果总是偏小或偏大先确定二分方向是“找最小可行解”还是“找最大可行解”再定更新规则第二个问题特别容易踩。比如你写找最大可行解的那类二分逻辑是“如果 mid 可行就继续往右试”所以会写left mid。这时候如果mid还是向下取整一旦right - left 1mid就等于left下次循环left mid没变化死循环。解决办法就是上面表格里的left mid时让mid向上取整。这个细节考试时不容易想到但刷题多了就会形成条件反射。2. 核心题解实操LeetCode 875 爱吃香蕉的狒狒2.1 题目理解与输入输出拆解先说明一下热词里写的是“leetcode 073 爱吃香蕉的狒狒”容易把两道题记混。LeetCode 第 73 题是“矩阵置零”跟香蕉没有关系爱吃香蕉的狒狒对应的是第 875 题。这道题在 LeetCode 上非常有名属于“二分答案”入门的必刷题。题目大意狒狒面前有 N 堆香蕉piles[i]表示第 i 堆香蕉的根数。狒狒每小时可以选择一堆香蕉以速度 K 根/小时开吃。如果这一堆剩下的香蕉不足 K 根狒狒会在这一小时内全部吃完但不会去碰下一堆因为每堆香蕉的处理是串行的。警卫会在 H 小时后回来狒狒需要保证在 H 小时内吃完所有香蕉问最小的 K 是多少。举个例子piles [3, 6, 7, 11]H 8答案应该是 4。验证一下速度 4 时第一堆要 1 小时第二堆要 2 小时6 根分两次吃第三堆要 2 小时第四堆要 3 小时总时间 8 小时刚好压线。速度 3 时总时间超过 8说明 3 不够所以最小速度就是 4。这里有一个隐含约束要注意因为狒狒每小时最多只能解决一堆香蕉所以如果 H 小于香蕉堆数 N那无论如何都吃不完题目保证输入 H 一定大于等于 N。另外piles[i]最大可以到 10 的 9 次方这个范围决定了暴力枚举 K 是肯定不行的必须二分。2.2 暴力思路到二分答案的推导最直观的做法是从 K 1 一直试到max(piles)对每个 K 算一遍吃完所有香蕉需要多少小时找第一个满足总时间小于等于 H 的 K。假设max(piles) M这玩意的复杂度是 O(N * M)M 到 10 的 9 次方级别时基本就是不可能完成的任务。再仔细看一下问题K 越大每小时能吃的香蕉越多总耗时就越短。具体来说总耗时函数time(K)是一个随 K 增大而单调递减的函数。我们想要“满足time(K) H的最小 K”这就是典型的“在单调序列上寻找左边界”的问题完全可以用二分。二分的值域是[1, max(piles)]K 最小是 1这是题目的限制K 最大是最大堆的香蕉数因为速度超过最大堆之后没有任何额外收益总时间不会继续下降至少需要 N 小时吃完 N 堆再大的速度也不会让总时间低于 N。在这个值域里二分每次用速度 mid 计算总耗时判断 mid 是否可行然后收缩区间。2.3 完整代码实现Python 与 Java 双版本Python 版本写起来很简洁核心是验证函数ok(k)def minEatingSpeed(piles, h): def ok(k): hours 0 for p in piles: hours (p k - 1) // k if hours h: return False return True left, right 1, max(piles) while left right: mid (left right) // 2 if ok(mid): right mid else: left mid 1 return leftJava 版本要注意数据范围总耗时可能超过 int用long接收public int minEatingSpeed(int[] piles, int h) { int left 1, right 0; for (int p : piles) { right Math.max(right, p); } while (left right) { int mid left (right - left) / 2; long hours 0; for (int p : piles) { hours (p mid - 1) / mid; if (hours h) { break; } } if (hours h) { right mid; } else { left mid 1; } } return left; }代码里有两个细节值得说。第一个是(p k - 1) // k这个写法它等价于向上取整直接算出“这堆香蕉以速度 k 需要吃几小时”。第二部分说hours h就提前break这样可以减少不必要的计算虽然本题不提前 break 也完全能过但这是一个好的习惯后面会遇到很多更严格的题。2.4 边界条件与时间复杂度这道题几个容易翻车的地方我单独拎出来说。第一右边界为什么是max(piles)。有人会想是不是设成更大更保险比如 10 的 9 次方。其实没必要因为当 K 大于最大堆时总时间就是堆数 N不会再变小继续往右二分没有意义。把右边设成max(piles)可以让二分区间更小也可能省几次迭代。第二hours (p mid - 1) / mid用的是long。极端情况一万堆香蕉每堆 10 的 9 次方速度是 1 的时候总耗时会达到 10 的 13 次方int 根本装不下。Java 里如果用 int 累加一旦溢出可能变成负数负数就永远小于 h二分结果直接出错。这个问题在实际比赛中坑过很多人所以写累加和的时候先想一下数据范围。第三这题的时间复杂度是 O(N log M)其中 M max(piles)。二分迭代次数约 30 次因为 2 的 30 次方已经是 10 的 9 次方级别每次遍历一遍 piles 数组整体执行次数在 30 万左右跑起来飞快。3. 周赛430复盘一次真实限时刷题实录3.1 周赛做题节奏与时间分配打完周赛 430我最想分享的不是具体哪道题而是整个过程中暴露出来的节奏问题。很多人觉得周赛就是“查漏补缺”其实它更像面试的模拟固定时间、不能中途查资料、每题都有时间成本。我的习惯是前 10 分钟不急着敲代码。先把四道题全部看一遍在草稿纸上标清楚每道题的数据范围、大概题型和可能的坑。这一步看起来浪费时间实际上能避免“在一道困难题上写了 20 分钟发现思路完全错”的惨案。周赛 430 的题型分布里前两题基本属于热身题第三题开始出现明显分叉第四题是压轴题。我给自己定的规矩是每题最多投入 20 分钟超过 20 分钟没有清晰思路就先跳过回头做后面的如果第三题卡住很久果断先做第四题的第一档数据。这方法在周赛里特别有用因为 LeetCode 的周赛评测是做完一题提交一题最终排名看的是总得分和罚时。与其和中等题死磕 30 分钟再交一个错误答案不如先保证能拿到的分都拿到。3.2 这次周赛踩到的坑周赛 430 过程中我最深刻的教训来自数据范围。第一题很简单很容易上手但我看了一眼数据范围后用了int做累加结果本地测试通过提交却错了一个测试用例。原因很直接大样例下累加值超过 int 上限。这种错在平时刷题时几乎不犯但在限时压力下人会不自觉地省略“先看数据范围”这一步。第二个坑是第三题的思路方向。我看到题目描述里提到图相关的词汇第一反应是建图、跑 DFS结果写着写着发现状态转移其实可以用更简单的贪心解决。等意识到这一点时已经过去 15 分钟。复盘时我把教训记在笔记里周赛第三题往往不会直接考察某个大算法的完整实现而是隐藏在一个中等难度的包装里先手动算几个例子猜结论再决定用不用重算法这个顺序比一上来就套模板重要得多。第三个坑是赛后补题。我之前一直有个坏习惯周赛打完就算了错题也不看解析。后来被朋友点醒周赛最有价值的就是赛后 24 小时内的复盘看官方题解、看评论区的大佬写法、对比自己的思路差距在哪里。这次周赛 430 我用了三题的数据结构和官方题解做对比发现有两题其实有更优解而我当时根本没想到。3.3 从周赛看自己算法的短板几次周赛打下来我对自己水平有了更清晰的认识。能稳定通过前两题说明基础数据结构、字符串处理、简单模拟这些基本功已经过关偶尔能做出来第三题说明对常见算法套路有一定敏感度第四题基本属于超出当前水平但偶尔能靠特殊数据范围拿一些部分分。我建议每个刷 LeetCode 的人都要保持周赛频率。周赛的评分和排名能真实反映你的临场反应速度这种反馈是平时刷题给不了的。而且周赛题目会涉及很多近期热门考点比如前缀和、滑动窗口、树上 DFS这些正好能帮你检验《热门100题》刷完之后到底掌握到什么程度。把周赛中反复出现的题型记下来回到 LeetCode 题库里找同类题专项突破这是我觉得周赛的最大价值。4. 《热门100题》刷题路线与笔记方法4.1 热门100题是什么值得刷吗LeetCode 的“热门 100 题”Top 100 Liked Questions是官方从全题库里挑出的高讨论量、高点赞、高频面试题目合集。它和“剑指 Offer”那套题单不是一个思路剑指 Offer 偏面试原题题型覆盖面窄但针对性强热门 100 题更偏算法思维体系难度分布均匀从一串简单题到压轴难题都有适合用来建立整体刷题框架。我的观点很明确如果你时间有限比如只需要准备校招或者社招算法面热门 100 题是性价比最高的题单。因为很多大厂面试官出题就是在热门题基础上做变形把原题吃透至少面对中等题能够快速分析。但热门 100 题不等于刷完就万事大吉。它里面没有覆盖所有算法分支图论、线段树、状态压缩 DP 这些都不全只能作为主线不能替代系统学习。我的策略是把它当作主线题单同时从题解区反查同类题把热门题背后的一类题都摸一遍。4.2 推荐刷题顺序与分类路径刷题顺序非常影响效率。按我自己的经验分成五个阶段比较合理每阶段的题目类型和代表性题目可以照着选。第一阶段先搞数组与哈希。两数之和、字母异位词分组、最长连续序列这几道是必刷的这一阶段主要建立“哈希表优化查找”的思维。第二阶段是双指针与滑动窗口盛最多水的容器、三数之和、无重复字符的最长子串、最小覆盖子串这四道题做完基本就懂两种窗口写法了。第三阶段是链表翻转链表、合并两个有序链表、LRU 缓存机制重点练指针操作和 dummy 节点技巧。第四阶段是二叉树中序遍历、层序遍历、从前序与中序遍历序列构造二叉树、二叉树中的最大路径和树是最容易出变形的题必须把递归遍历吃透。第五阶段才是动态规划和回溯全排列、组合总和、零钱兑换、最长递增子序列、编辑距离这个阶段要开始学会画状态转移表。路线可以参考表格但我更想强调一点不要按难度从 Easy 开始一口气刷完所有 Easy那会陷入“会做但没提高”的陷阱。按专题刷一个专题内部的题目难度交错反而更能理解算法本质。阶段核心内容代表题掌握目标一数组与哈希1. 两数之和、49. 字母异位词分组、128. 最长连续序列会分析查找瓶颈用哈希打表二双指针与滑动窗口11. 盛最多水的容器、15. 三数之和、3. 无重复字符的最长子串、76. 最小覆盖子串能区分快慢指针和左右收敛三链表206. 反转链表、21. 合并两个有序链表、146. LRU 缓存机制熟练处理边界和 dummy 节点四二叉树94. 二叉树的中序遍历、102. 二叉树的层序遍历、105. 从前序与中序遍历序列构造二叉树、124. 二叉树中的最大路径和递归函数返回值设计五回溯与动态规划46. 全排列、39. 组合总和、322. 零钱兑换、72. 编辑距离能画状态转移图4.3 算法笔记应该怎么记既然这篇笔记标题是“算法笔记”那记录方法值得单独说一说。我以前也走过弯路见一题抄一题题解结果抄完就忘。后来换成结构化笔记模板每道题固定记五个部分题目链接和难度、我的第一思路、正确思路的推导过程、代码实现、错因分析。错因分析这个部分最关键因为这是独一无二的信息。我会写清楚自己为什么想错是在哪个环节卡住的以及下次遇到同类题应该先尝试什么方向。比如在做最小覆盖子串时我第一次没意识到滑动窗口需要“先扩展再收缩”卡了半天。这个经验写进笔记后下次再做这类题就会条件反射地想到“窗口合法性判断”。笔记还应该按专题组织而不是按时间顺序。我在 Obsidian 里建了五个文件夹数组、链表、树、DP、其他每个文件夹里放同专题的题解和经验总结。这样做的好处是复习时有很强的关联性一打开“二分查找”这个文件夹就能看到所有做过的二分题和它们的共性问题比每次从头翻聊天记录高效得多。5. 常见问题与排查技巧实录5.1 二分查找代码常见的三类报错刷了这么多二分题我把踩过的坑归类成三类保证看完能避开一大半雷区。第一类是超时。典型的错误是把二分写成了暴力循环比如在“爱吃香蕉的狒狒”里有人会写for k in range(1, max(piles)1)然后逐个验证乍一看没错但数据一大就超时。另一种超时在于验证函数里做了过重的工作比如每次验证都去排序或者重建数据结构这种就需要重新审视 check 函数的复杂度。第二类是死循环。死循环常见于区间更新逻辑与中点取整方向不一致的场景。比如用left right循环分支里写left mid但 mid 是向下取整当left 2, right 3时mid 2如果此时可行left还是 2无限循环。解决办法我前面提过left mid的分支要搭配向上取整的 mid。第三类是结果差 1。这类错误最隐蔽因为大部分测试用例都能过就挂在一个边界上。比如找“最小可行速度”你在可行分支里写left mid而不是right mid结果返回的是最后一个不可行的值就差 1。我的习惯是每次写完都对着题干的“最小/最大/首次/最后一次”这些词确认二分方向。5.2 刷题环境与本地调试经验很多人刷题直接在网页里写代码遇到复杂逻辑就不知道去哪调试。我的做法是本地建一个 Java/Python 项目每个题独立一个文件配合测试用例跑。提交之前至少跑三组数据示例输入、边界输入、随机数据。边界输入要特别设计。对“爱吃香蕉的狒狒”来说边界就是piles [1]且H 1的情况此时 K 应该等于 1还有H刚好等于堆数 N 的情况此时 K 必须大于等于最大堆因为每小时只能吃一堆不可能压缩总时间所以答案强制等于max(piles)。这种极端测试很容易暴露算法里隐藏的假设。调试复杂逻辑时我喜欢用print或System.out.println输出中间状态尤其是二分过程中每次 mid 对应的时间值。看一遍输出就能直观感受到“可行区间是怎么一点点缩小的”这比自己干想代码强得多。等确认无误再删掉调试语句提交。5.3 避坑清单这些细节别再踩了场景建议累加计数变量先看数据范围不确定就用 long大不了多占 8 字节二分区间上下界先想清楚候选答案的最小值和最大值写死在代码里比推导表达式更稳验证函数复杂度每次验证控制在 O(N) 或 O(N log N)不能再重取整方向记住向上取整公式(a b - 1) / b向下取整(a b) / b周赛做题顺序先通读所有题签到题先写难题固定 20 分钟止损最后再说一点实在的。关于二分很多人会陷入恐惧觉得边界永远处理不好。但真实情况是二分其实是最容易形成肌肉记忆的算法之一关键在于把模板吃透然后反复练“二分答案”类题目。我自己的感受是每次刷 LeetCode 周赛或者做热门 100 题翻车最多的往往是“想当然”而不是“不会”比如不检查溢出、不验证边界、不确认单调方向。只要在刷题时多留个心眼把这些常见问题变成条件反射你的解题稳定性一定会明显上一台阶。 二分查找算法笔记：LeetCode 875爱吃香蕉的狒狒题解与刷题路线
这篇笔记是《算法笔记》系列的第五篇。前四篇我把数组、链表、哈希表、滑动窗口这几个专题捋了一遍这次终于轮到二分查找了顺便把最近参加 LeetCode 周赛 430 的复盘和《热门100题》的刷题路线一起整理进来。如果你正在刷 LeetCode尤其是卡在二分边界、找不到题目突破口、或者想系统规划刷题路线的这篇应该能帮上忙。这期内容以 LeetCode 875“爱吃香蕉的狒狒”为核心题解同时把二分答案这一类题的识别方法和模板一次讲透再结合周赛实战聊聊怎么用限时训练反哺日常刷题。1. 本期主题拆解为什么第五篇要集中啃二分查找1.1 二分查找不是背模板而是识别“单调性”很多人一看到“二分查找”四个字脑子里就是left、right、mid然后开始背边界条件。但刷到后面你会发现二分真正考察的不是边界怎么写而是你能不能在一道题里看出“答案可以二分”。LeetCode 上的二分题表面上分几类有序数组里找目标值、旋转数组里找最小值、在值域上二分答案。前两类是“在一堆已经排好序的数里找东西”套路相对固定第三类才是拉开差距的地方典型代表就是 875 题“爱吃香蕉的狒狒”。这类题有个共同特征题目要求你求一个“答案值”而这个答案值的可行性与一个单调变化的量挂钩。狒狒每小时吃的香蕉速度 K 越大吃完所有香蕉花费的总时间就越短这就是一个单调递减关系。只要存在这种单调性就可以在答案的取值范围内做二分——二分的是 K 的取值而不是题目给你的数组下标。判断一道题能不能用“二分答案”我在笔记里给自己定了三个硬标准第一答案有明确取值区间不可能是无限范围第二存在验证函数给定一个候选答案能快速算出是否可行第三验证结果随候选答案单调变化。三个条件都满足别犹豫直接往二分上想。这比看到“最小化最大值”“最大化最小值”这些词再去猜模板要靠谱得多因为很多题根本不会给你这么明显的提示。1.2 二分的三个易错点虽然二分逻辑简单但写起来容易出问题我自己的笔记里专门整理了一个避坑表每次写完都对着检查一遍。易错点典型表现解决思路中点计算溢出left right在 Java、C 里可能超出 int 范围用mid left (right - left) / 2或(left right) 1死循环同样是left right的循环更新left mid时可能永远走不出来当分支里有left mid时mid必须向上取整mid left (right - left 1) / 2答案差 1最后返回left或right边界搞混导致结果总是偏小或偏大先确定二分方向是“找最小可行解”还是“找最大可行解”再定更新规则第二个问题特别容易踩。比如你写找最大可行解的那类二分逻辑是“如果 mid 可行就继续往右试”所以会写left mid。这时候如果mid还是向下取整一旦right - left 1mid就等于left下次循环left mid没变化死循环。解决办法就是上面表格里的left mid时让mid向上取整。这个细节考试时不容易想到但刷题多了就会形成条件反射。2. 核心题解实操LeetCode 875 爱吃香蕉的狒狒2.1 题目理解与输入输出拆解先说明一下热词里写的是“leetcode 073 爱吃香蕉的狒狒”容易把两道题记混。LeetCode 第 73 题是“矩阵置零”跟香蕉没有关系爱吃香蕉的狒狒对应的是第 875 题。这道题在 LeetCode 上非常有名属于“二分答案”入门的必刷题。题目大意狒狒面前有 N 堆香蕉piles[i]表示第 i 堆香蕉的根数。狒狒每小时可以选择一堆香蕉以速度 K 根/小时开吃。如果这一堆剩下的香蕉不足 K 根狒狒会在这一小时内全部吃完但不会去碰下一堆因为每堆香蕉的处理是串行的。警卫会在 H 小时后回来狒狒需要保证在 H 小时内吃完所有香蕉问最小的 K 是多少。举个例子piles [3, 6, 7, 11]H 8答案应该是 4。验证一下速度 4 时第一堆要 1 小时第二堆要 2 小时6 根分两次吃第三堆要 2 小时第四堆要 3 小时总时间 8 小时刚好压线。速度 3 时总时间超过 8说明 3 不够所以最小速度就是 4。这里有一个隐含约束要注意因为狒狒每小时最多只能解决一堆香蕉所以如果 H 小于香蕉堆数 N那无论如何都吃不完题目保证输入 H 一定大于等于 N。另外piles[i]最大可以到 10 的 9 次方这个范围决定了暴力枚举 K 是肯定不行的必须二分。2.2 暴力思路到二分答案的推导最直观的做法是从 K 1 一直试到max(piles)对每个 K 算一遍吃完所有香蕉需要多少小时找第一个满足总时间小于等于 H 的 K。假设max(piles) M这玩意的复杂度是 O(N * M)M 到 10 的 9 次方级别时基本就是不可能完成的任务。再仔细看一下问题K 越大每小时能吃的香蕉越多总耗时就越短。具体来说总耗时函数time(K)是一个随 K 增大而单调递减的函数。我们想要“满足time(K) H的最小 K”这就是典型的“在单调序列上寻找左边界”的问题完全可以用二分。二分的值域是[1, max(piles)]K 最小是 1这是题目的限制K 最大是最大堆的香蕉数因为速度超过最大堆之后没有任何额外收益总时间不会继续下降至少需要 N 小时吃完 N 堆再大的速度也不会让总时间低于 N。在这个值域里二分每次用速度 mid 计算总耗时判断 mid 是否可行然后收缩区间。2.3 完整代码实现Python 与 Java 双版本Python 版本写起来很简洁核心是验证函数ok(k)def minEatingSpeed(piles, h): def ok(k): hours 0 for p in piles: hours (p k - 1) // k if hours h: return False return True left, right 1, max(piles) while left right: mid (left right) // 2 if ok(mid): right mid else: left mid 1 return leftJava 版本要注意数据范围总耗时可能超过 int用long接收public int minEatingSpeed(int[] piles, int h) { int left 1, right 0; for (int p : piles) { right Math.max(right, p); } while (left right) { int mid left (right - left) / 2; long hours 0; for (int p : piles) { hours (p mid - 1) / mid; if (hours h) { break; } } if (hours h) { right mid; } else { left mid 1; } } return left; }代码里有两个细节值得说。第一个是(p k - 1) // k这个写法它等价于向上取整直接算出“这堆香蕉以速度 k 需要吃几小时”。第二部分说hours h就提前break这样可以减少不必要的计算虽然本题不提前 break 也完全能过但这是一个好的习惯后面会遇到很多更严格的题。2.4 边界条件与时间复杂度这道题几个容易翻车的地方我单独拎出来说。第一右边界为什么是max(piles)。有人会想是不是设成更大更保险比如 10 的 9 次方。其实没必要因为当 K 大于最大堆时总时间就是堆数 N不会再变小继续往右二分没有意义。把右边设成max(piles)可以让二分区间更小也可能省几次迭代。第二hours (p mid - 1) / mid用的是long。极端情况一万堆香蕉每堆 10 的 9 次方速度是 1 的时候总耗时会达到 10 的 13 次方int 根本装不下。Java 里如果用 int 累加一旦溢出可能变成负数负数就永远小于 h二分结果直接出错。这个问题在实际比赛中坑过很多人所以写累加和的时候先想一下数据范围。第三这题的时间复杂度是 O(N log M)其中 M max(piles)。二分迭代次数约 30 次因为 2 的 30 次方已经是 10 的 9 次方级别每次遍历一遍 piles 数组整体执行次数在 30 万左右跑起来飞快。3. 周赛430复盘一次真实限时刷题实录3.1 周赛做题节奏与时间分配打完周赛 430我最想分享的不是具体哪道题而是整个过程中暴露出来的节奏问题。很多人觉得周赛就是“查漏补缺”其实它更像面试的模拟固定时间、不能中途查资料、每题都有时间成本。我的习惯是前 10 分钟不急着敲代码。先把四道题全部看一遍在草稿纸上标清楚每道题的数据范围、大概题型和可能的坑。这一步看起来浪费时间实际上能避免“在一道困难题上写了 20 分钟发现思路完全错”的惨案。周赛 430 的题型分布里前两题基本属于热身题第三题开始出现明显分叉第四题是压轴题。我给自己定的规矩是每题最多投入 20 分钟超过 20 分钟没有清晰思路就先跳过回头做后面的如果第三题卡住很久果断先做第四题的第一档数据。这方法在周赛里特别有用因为 LeetCode 的周赛评测是做完一题提交一题最终排名看的是总得分和罚时。与其和中等题死磕 30 分钟再交一个错误答案不如先保证能拿到的分都拿到。3.2 这次周赛踩到的坑周赛 430 过程中我最深刻的教训来自数据范围。第一题很简单很容易上手但我看了一眼数据范围后用了int做累加结果本地测试通过提交却错了一个测试用例。原因很直接大样例下累加值超过 int 上限。这种错在平时刷题时几乎不犯但在限时压力下人会不自觉地省略“先看数据范围”这一步。第二个坑是第三题的思路方向。我看到题目描述里提到图相关的词汇第一反应是建图、跑 DFS结果写着写着发现状态转移其实可以用更简单的贪心解决。等意识到这一点时已经过去 15 分钟。复盘时我把教训记在笔记里周赛第三题往往不会直接考察某个大算法的完整实现而是隐藏在一个中等难度的包装里先手动算几个例子猜结论再决定用不用重算法这个顺序比一上来就套模板重要得多。第三个坑是赛后补题。我之前一直有个坏习惯周赛打完就算了错题也不看解析。后来被朋友点醒周赛最有价值的就是赛后 24 小时内的复盘看官方题解、看评论区的大佬写法、对比自己的思路差距在哪里。这次周赛 430 我用了三题的数据结构和官方题解做对比发现有两题其实有更优解而我当时根本没想到。3.3 从周赛看自己算法的短板几次周赛打下来我对自己水平有了更清晰的认识。能稳定通过前两题说明基础数据结构、字符串处理、简单模拟这些基本功已经过关偶尔能做出来第三题说明对常见算法套路有一定敏感度第四题基本属于超出当前水平但偶尔能靠特殊数据范围拿一些部分分。我建议每个刷 LeetCode 的人都要保持周赛频率。周赛的评分和排名能真实反映你的临场反应速度这种反馈是平时刷题给不了的。而且周赛题目会涉及很多近期热门考点比如前缀和、滑动窗口、树上 DFS这些正好能帮你检验《热门100题》刷完之后到底掌握到什么程度。把周赛中反复出现的题型记下来回到 LeetCode 题库里找同类题专项突破这是我觉得周赛的最大价值。4. 《热门100题》刷题路线与笔记方法4.1 热门100题是什么值得刷吗LeetCode 的“热门 100 题”Top 100 Liked Questions是官方从全题库里挑出的高讨论量、高点赞、高频面试题目合集。它和“剑指 Offer”那套题单不是一个思路剑指 Offer 偏面试原题题型覆盖面窄但针对性强热门 100 题更偏算法思维体系难度分布均匀从一串简单题到压轴难题都有适合用来建立整体刷题框架。我的观点很明确如果你时间有限比如只需要准备校招或者社招算法面热门 100 题是性价比最高的题单。因为很多大厂面试官出题就是在热门题基础上做变形把原题吃透至少面对中等题能够快速分析。但热门 100 题不等于刷完就万事大吉。它里面没有覆盖所有算法分支图论、线段树、状态压缩 DP 这些都不全只能作为主线不能替代系统学习。我的策略是把它当作主线题单同时从题解区反查同类题把热门题背后的一类题都摸一遍。4.2 推荐刷题顺序与分类路径刷题顺序非常影响效率。按我自己的经验分成五个阶段比较合理每阶段的题目类型和代表性题目可以照着选。第一阶段先搞数组与哈希。两数之和、字母异位词分组、最长连续序列这几道是必刷的这一阶段主要建立“哈希表优化查找”的思维。第二阶段是双指针与滑动窗口盛最多水的容器、三数之和、无重复字符的最长子串、最小覆盖子串这四道题做完基本就懂两种窗口写法了。第三阶段是链表翻转链表、合并两个有序链表、LRU 缓存机制重点练指针操作和 dummy 节点技巧。第四阶段是二叉树中序遍历、层序遍历、从前序与中序遍历序列构造二叉树、二叉树中的最大路径和树是最容易出变形的题必须把递归遍历吃透。第五阶段才是动态规划和回溯全排列、组合总和、零钱兑换、最长递增子序列、编辑距离这个阶段要开始学会画状态转移表。路线可以参考表格但我更想强调一点不要按难度从 Easy 开始一口气刷完所有 Easy那会陷入“会做但没提高”的陷阱。按专题刷一个专题内部的题目难度交错反而更能理解算法本质。阶段核心内容代表题掌握目标一数组与哈希1. 两数之和、49. 字母异位词分组、128. 最长连续序列会分析查找瓶颈用哈希打表二双指针与滑动窗口11. 盛最多水的容器、15. 三数之和、3. 无重复字符的最长子串、76. 最小覆盖子串能区分快慢指针和左右收敛三链表206. 反转链表、21. 合并两个有序链表、146. LRU 缓存机制熟练处理边界和 dummy 节点四二叉树94. 二叉树的中序遍历、102. 二叉树的层序遍历、105. 从前序与中序遍历序列构造二叉树、124. 二叉树中的最大路径和递归函数返回值设计五回溯与动态规划46. 全排列、39. 组合总和、322. 零钱兑换、72. 编辑距离能画状态转移图4.3 算法笔记应该怎么记既然这篇笔记标题是“算法笔记”那记录方法值得单独说一说。我以前也走过弯路见一题抄一题题解结果抄完就忘。后来换成结构化笔记模板每道题固定记五个部分题目链接和难度、我的第一思路、正确思路的推导过程、代码实现、错因分析。错因分析这个部分最关键因为这是独一无二的信息。我会写清楚自己为什么想错是在哪个环节卡住的以及下次遇到同类题应该先尝试什么方向。比如在做最小覆盖子串时我第一次没意识到滑动窗口需要“先扩展再收缩”卡了半天。这个经验写进笔记后下次再做这类题就会条件反射地想到“窗口合法性判断”。笔记还应该按专题组织而不是按时间顺序。我在 Obsidian 里建了五个文件夹数组、链表、树、DP、其他每个文件夹里放同专题的题解和经验总结。这样做的好处是复习时有很强的关联性一打开“二分查找”这个文件夹就能看到所有做过的二分题和它们的共性问题比每次从头翻聊天记录高效得多。5. 常见问题与排查技巧实录5.1 二分查找代码常见的三类报错刷了这么多二分题我把踩过的坑归类成三类保证看完能避开一大半雷区。第一类是超时。典型的错误是把二分写成了暴力循环比如在“爱吃香蕉的狒狒”里有人会写for k in range(1, max(piles)1)然后逐个验证乍一看没错但数据一大就超时。另一种超时在于验证函数里做了过重的工作比如每次验证都去排序或者重建数据结构这种就需要重新审视 check 函数的复杂度。第二类是死循环。死循环常见于区间更新逻辑与中点取整方向不一致的场景。比如用left right循环分支里写left mid但 mid 是向下取整当left 2, right 3时mid 2如果此时可行left还是 2无限循环。解决办法我前面提过left mid的分支要搭配向上取整的 mid。第三类是结果差 1。这类错误最隐蔽因为大部分测试用例都能过就挂在一个边界上。比如找“最小可行速度”你在可行分支里写left mid而不是right mid结果返回的是最后一个不可行的值就差 1。我的习惯是每次写完都对着题干的“最小/最大/首次/最后一次”这些词确认二分方向。5.2 刷题环境与本地调试经验很多人刷题直接在网页里写代码遇到复杂逻辑就不知道去哪调试。我的做法是本地建一个 Java/Python 项目每个题独立一个文件配合测试用例跑。提交之前至少跑三组数据示例输入、边界输入、随机数据。边界输入要特别设计。对“爱吃香蕉的狒狒”来说边界就是piles [1]且H 1的情况此时 K 应该等于 1还有H刚好等于堆数 N 的情况此时 K 必须大于等于最大堆因为每小时只能吃一堆不可能压缩总时间所以答案强制等于max(piles)。这种极端测试很容易暴露算法里隐藏的假设。调试复杂逻辑时我喜欢用print或System.out.println输出中间状态尤其是二分过程中每次 mid 对应的时间值。看一遍输出就能直观感受到“可行区间是怎么一点点缩小的”这比自己干想代码强得多。等确认无误再删掉调试语句提交。5.3 避坑清单这些细节别再踩了场景建议累加计数变量先看数据范围不确定就用 long大不了多占 8 字节二分区间上下界先想清楚候选答案的最小值和最大值写死在代码里比推导表达式更稳验证函数复杂度每次验证控制在 O(N) 或 O(N log N)不能再重取整方向记住向上取整公式(a b - 1) / b向下取整(a b) / b周赛做题顺序先通读所有题签到题先写难题固定 20 分钟止损最后再说一点实在的。关于二分很多人会陷入恐惧觉得边界永远处理不好。但真实情况是二分其实是最容易形成肌肉记忆的算法之一关键在于把模板吃透然后反复练“二分答案”类题目。我自己的感受是每次刷 LeetCode 周赛或者做热门 100 题翻车最多的往往是“想当然”而不是“不会”比如不检查溢出、不验证边界、不确认单调方向。只要在刷题时多留个心眼把这些常见问题变成条件反射你的解题稳定性一定会明显上一台阶。