真正让我意识到刷题这件事可能哪里出了问题的是在周赛430那晚。前两题顺风顺水第三题耗了一个小时没写完整。赛后点开题解区热评第一写着“这不就是换了个皮的回溯加剪枝吗”那一刻我真的有点想关电脑。这种状态我猜很多人都不陌生。刷完所谓的LeetCode热门100题觉得自己见过的套路已经不少了结果碰到新题、尤其是周赛题照样容易大脑空白。问题出在哪我以前归因于题量不够后来归因于自己笨再后来才发现都不是。真正的问题是我长期把刷题当成背题把看题解当成抄答案很少去练那个最核心的能力从一道陌生题目里认出它属于什么模式然后快速把题目翻译成自己熟悉的解法框架。这篇文章不打算写那种一篇几十题的流水账题解。我想借LeetCode上三道看起来毫不相关的题来拆开聊这件事。第5题最长回文子串第494题目标和第875题爱吃香蕉的狒狒。三道题在LeetCode题解区和热门100题里的出现频率都不低而且刚好分别代表了刷题过程中最典型的三种卡点解法选型、数学抽象、以及对“二分查找”理解得太窄。把这三种卡点打通比多刷三十道新题有用得多。1. 从1到100题为什么刷题数量和时间不成正比1.1 我见过的两种典型刷题状态接触过不少准备面试的朋友我慢慢发现刷题人群基本可以分成两种状态。第一种状态是每道题都是一个独立任务。拿到题目先看题解题解里给了什么思路就照猫画虎写一遍能通过就算结束。偶尔遇到原题能秒遇到稍微换个问法的同类题就认不出来。这种刷法的问题在于题目本身不是靠“理解”进入脑子里的而是靠“印象”挂在脑子里。印象这个东西是最不靠谱的过两周就褪色之后只剩“我记得我好像做过这题”。第二种状态是刷题时始终多问一层这题为什么要用这个解法这个解法和暴力解法差在哪一步它依赖了题目给的哪个条件这类人刷题速度往往不快可能一道中等题要折腾一下午但三个月后你拿同知识点的变形题去考他他大概率能自己推出来。我自己的教训是走了很久的第一种状态直到被周赛按在地上摩擦才醒悟。LeetCode热门100题不是不能刷而是不能那样闭着眼睛刷。你把它当成一百个孤立题目去背它就会回报你一百个孤立记忆你要是把它当成七八种核心思想的载体去拆它才会成为真正能迁移的东西。1.2 刷题的本质是翻译不是背诵刷题这件事本质上是一场翻译工作。题目描述是一段人类语言它告诉你输入输出长什么样、求什么最值、满足什么条件。你要做的事情是在脑子里先把这段人类语言翻译成数学语言再翻译成算法语言最后落到代码上。比如“返回最长的回文子串”这句话问题的数学结构是“在字符串的连续区间里找满足对称性质的最长区间”。翻译成算法语言时你可以选择“枚举区间再判断”也可以选择“枚举对称中心再扩张”。两种都叫翻译但后者抓住了对称性的本质。很多同学看题解时只看最后一步的代码从来不关心作者是怎么从题目文字跳到这个解法的。这就是为什么代码看懂了自己做还是不会。你看懂的只是那个人的翻译结果但你没有跟着他走一遍翻译过程。本文后面的三道题我都会尽量把“从题面到思路”的跳跃过程拆开讲而不只是甩一段题解代码。2. 第5题最长回文子串一道题看穿“会做”和“做得好”的差距2.1 题目边界与暴力解法为什么必然超时先看题。给一个字符串s找到s中最长的回文子串。示例里s babad答案可以是bab或者aba因为两者长度都是3。这题在LeetCode上是热门100题里的常客字符串题目里几乎绕不开它。如果你完全没接触过回文题第一反应大概率是暴力。枚举所有子串起点和终点检查这段是不是回文记录最长的一段。这个思路没有任何问题但复杂度是O(n^3)枚举起点终点是O(n^2)检查回文又要线性扫一遍。当字符串长度到1000甚至5000的时候计算量直接爆炸超时是肯定的。暴力解法真正的问题不是慢而是它完全没有利用回文的结构。所谓回文就是正着读和反着读一样本质上是“关于中心对称”。如果你不知道抓住这个中心对称去设计算法就只能把每个子串都从头到尾验证一遍等于把一个本来只跟中心和半径有关的问题硬生生做成了区间枚举问题。我见过有人在这儿纠结要不要用KMP或者字符串哈希其实都跑偏了。这题的正确打开方式是从回文的结构出发。2.2 动态规划的填表顺序错了就全错很多人学这题时第一套解法是动态规划。思路也很经典设dp[i][j]表示s[i..j]这一段是不是回文。显然单个字符一定是回文也就是dp[i][i]为True如果s[i]等于s[j]并且去掉两端后s[i1..j-1]也是回文那s[i..j]就是回文。对应转移式可以写成dp[i][j] (s[i] s[j]) and (j - i 2 or dp[i 1][j - 1])j - i 2这个条件处理的是长度为1、2、3的子串。长度为1的单个字符当然是回文长度为2时只要两个字符相等就是回文长度为3时去掉两端剩单字符也一定是回文。所以不需要再去查dp数组里那些还没填过的位置。但这里有个很容易踩的坑填表顺序。dp[i][j]依赖的是dp[i1][j-1]也就是表格里“左下角”的那个状态。如果你按照常规的从左到右、从上到下去填二维数组你会发现算dp[i][j]的时候dp[i1][j-1]根本没算出来逻辑直接出错。正确做法是外层i从大到小遍历内层j从i向右遍历保证较短的子串始终先于较长子串被计算。很多人DP写不对不是不懂递推式而是二维表的遍历顺序错了这就很冤。不过说实话在面试里我对这道题并不推荐先用DP。虽然时间复杂度是O(n^2)但空间复杂度O(n^2)在字符串长度较大的时候并不好看。如果能用滚动数组优化空间代码复杂度又会上去。面试现场写错的风险偏高。2.3 中心扩展把“回文长得像什么”这件事吃透中心扩展是我个人最推荐面试时写的解法。它的核心观察特别朴素既然回文关于中心对称那我就枚举每一个可能的对称中心然后从这个中心往两边扩展能扩多长扩多长记录下最长的那个。需要注意的是对称中心有两种。奇数长度的回文对称中心是一个字符比如aba的中心是b。偶数长度的回文对称中心是两个字符中间的缝隙比如abba的中心在b和b之间。所以每个位置i既要尝试以i为中心的奇数扩展也要尝试以i和i1为中心的偶数扩展。一个长度为n的字符串一共有2n - 1个这样的中心。代码比DP短很多也好记class Solution: def longestPalindrome(self, s: str) - str: if not s: return start, end 0, 0 def expand(left: int, right: int): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 for i in range(len(s)): l1, r1 expand(i, i) # 奇数长度回文 l2, r2 expand(i, i 1) # 偶数长度回文 if r1 - l1 end - start: start, end l1, r1 if r2 - l2 end - start: start, end l2, r2 return s[start:end 1]这里有个小细节值得说expand函数里最后返回的是left1和right-1。因为循环退出时s[left]和s[right]已经不相等或者下标已经越界真正合法的回文区间是[left1, right-1]。复杂度上每个中心最多向外扩展n次一共2n-1个中心所以总复杂度O(n^2)空间只有O(1)。相比DP它没有二维数组也不用操心填表顺序写错的概率小很多。对我来说这题在面试中的标准答案就应该是中心扩展。2.4 Manacher算法心里有数但别执念聊到这题总有人会提Manacher算法号称能到O(n)。确实能到它利用已经计算过的回文半径来避免重复比较网上有很多讲解。但我对大多数人的建议是知道有这么回事就行别花大量精力去背模板。理由很简单。面试中O(n^2)的解法学完就能写代码量小逻辑直观。Manacher虽然更优但边界条件多很多细节需要理解得很透才能白板写对。如果不是目标公司明确要求超高难度算法这题用Manacher并不能给你加分反而可能暴露你“只会背复杂模板、基础解法反而讲不清楚”的问题。我自己对Manacher的态度是理解了它的核心思想知道它是用“已求得的回文半径”加速扩展但平时刷题不会优先用它。等中心扩展和DP都打得足够熟还有余力再研究不迟。3. 第494题目标和从回溯穷举到“负号子集划分”的思维跃迁3.1 回溯是万能的但只对超小数据万能目标和这道题是搜索与动态规划之间的一道经典分水岭。题面很简短给定非负整数数组nums和一个目标整数target你可以给每个元素前面放一个号或者-号问有多少种不同的表达式使得计算结果等于target。理解这道题不要一上来就看背包解法先把最朴素的思路走一遍。每个数字只有两种选择正或者负那典型的做法就是DFS。到最后一个位置时如果当前累计值等于target就计1种方案。from functools import lru_cache class Solution: def findTargetSumWays(self, nums, target): lru_cache(None) def dfs(i, cur_sum): if i len(nums): return 1 if cur_sum target else 0 return dfs(i 1, cur_sum nums[i]) dfs(i 1, cur_sum - nums[i]) return dfs(0, 0)这个代码很好理解复杂度是O(2^n)因为每个位置都要分出正负两条路。如果nums长度只有202^20大约一百万勉强能跑一旦长度到100这个复杂度就是天文数字。回溯不是错而是它没法应对数据规模扩大后的场景。如果你只会回溯说明你还没有完成从“穷举空间”到“合并重复状态”的思维升级。有同学可能会说那加个记忆化不就行了确实上面的lru_cache版本本质是记忆化搜索它能复用相同(i, cur_sum)的结果。但本题真正有意思的地方不在这里而在于它还可以被改写成一种完全不同的模型。3.2 关键转换把正负号问题看成子集划分我们来做一个简单的数学推导。假设所有数字的总和是total。当我们给一部分数字加正号、另一部分加负号时最终结果等于“所有正号数字之和”减去“所有负号数字的绝对值之和”。设正号那部分的数字和是P那么负号那部分的数字和就是total - P最终的值就是P - (total - P) 2P - total题目要求这个结果等于target所以可以解出P (total target) / 2。也就是说问题被转换成了从nums里挑出若干个数使它们的和正好等于P问有多少种选法。这个转换的本质是把每个数字前面“加号还是减号”的选择变成了“这个数要不要放进正号集合里”。原来的正负号问题变成了一个典型的01背包计数问题。这个思维跳跃特别重要因为它解释了为什么很多看起来很不一样的题目最后都能落到同一个DP模型上。坑也随之而来。total target必须是偶数否则P不是整数说明不存在合法的正号和等于P直接返回0如果 |target| total也不可能得到这个目标值同样返回0。这两个边界条件很多人会漏。3.3 01背包计数代码与零元素的坑当P算出来之后就可以用背包来数方案了。这里背包的容量是P每个数字是一个重量等于自身数值的物品要求恰好装满容量P的方案总数。初值dp[0] 1表示容量0有一种方案什么都不选。每来一个数字num容量从P往下倒序遍历执行dp[j] dp[j - num]。class Solution: def findTargetSumWays(self, nums, target): total sum(nums) if abs(target) total: return 0 if (total target) % 2 1: return 0 P (total target) // 2 dp [0] * (P 1) dp[0] 1 for num in nums: for j in range(P, num - 1, -1): dp[j] dp[j - num] return dp[P]这里有一个特别容易忽略的细节nums里可能有0。如果某个数字是0放它进正号集合和放它进负号集合对P没有任何影响但方案数会翻倍。你在代码里看到循环从P到0遍历时num等于0意味着j和j-num是同一个下标dp[j]会等于自己加自己每个0都会让相关容量计数自然翻倍。也就是说当前这个写法其实已经正确处理了0元素的情况。只要你是按0/1背包的倒序遍历来写0元素会自然地累计倍数不需要额外处理。如果对这点不放心也可以把0单独拎出来最后乘上2的零元素个数次方。但在我实际测试里上面的倒序dp写法就能通过包含0的用例关键是别把循环内层写成从0到P的正序否则每个0会让同一件物品被重复选取无限次结果就错了。之前就见过有人一遇到0就翻车就是因为内层顺序写反。3.4 遇到“正负号凑target”先想一想子集划分随着这类题刷多之后你会发现一个规律凡是题目里说“给每个元素加正号或者负号”“把数组分成两部分”“求差值为某个数”之类的话第一反应不应该是去DFS枚举而是想一想能不能通过移项转换成“选一部分数求和等于P”的背包问题。第494题是最标准的例子。LeetCode里还有一道分割等和子集的题本质就是看能否选出一半总和那个也是同一个背包模型。我个人的建议是把这三类问法整理在一个笔记里加正负号求target、分割成两个和相等的子集、选物品使价值尽量接近某个容量。它们都指向同一套01背包代码。将来面试中如果遇到类似文字你就能很快判断出该往哪个方向走。4. 第875题爱吃香蕉的狒狒二分查找的对象不是数组是答案4.1 一个把“最快速度”误以为是模拟题的瞬间先解释一下题目的名字。原题英文叫Koko Eating Bananas题里的小动物Koko是一只猩猩中文社区不少题解翻译成“猩猩”但LeetCode题号列表里面经常有人把“073 爱吃香蕉的狒狒”这个Title传来传去狒狒和猩猩都行反正知道是同一个题就行。题面是这样狒狒有若干堆香蕉piles[i]表示第i堆有多少根。它每小时能选择一堆香蕉并吃掉其中最多k根。如果这一堆剩余的香蕉不足k根它把这堆吃完之后就停下来剩下的时间不会再吃别的堆。现在给你一个总小时数h问最少要用多大速度k才能在h小时内把所有香蕉吃完。刚看到这题的直觉很多人会以为这是模拟题从k1开始试慢到不行。确实这题如果按k从小往大暴力枚举也不是不能做无非是枚举到max(piles)。但当你把速度从1试到10的9次方时间复杂度就完全没法看了。这题真正的突破口在于把k当成一个“答案”然后问自己一个问题速度k和所需总时间之间是不是存在单调关系速度越大吃掉所有香蕉需要的时间越短速度越小需要的时间越长。单看这个性质答案的搜索空间天然就是有序的所以可以用二分。4.2 写出判断函数这题就完成一半二分答案的题最核心的部分不是二分本身而是判断函数怎么写。对于这个题给定速度k我们能在h小时内吃完吗答案来自一个简单的计算。因为每个小时狒狒最多只能处理一堆如果一堆香蕉有p根它要吃ceil(p / k)小时。把所有堆的时间加起来就是总时间。判断函数如下def can_finish(k: int, piles, h: int) - bool: hours 0 for p in piles: hours (p k - 1) // k # 等价于向上取整 return hours h用(p k - 1) // k代替ceil函数是为了避免浮点数误差也顺便省一次import。这一步想明白后面的二分就轻松了。我见过不少人卡住不是卡在二分找不到答案而是卡在没想清楚这个判断函数到底判什么。他们总觉得二分一定要作用在一个“数组”上数组里找不到饭吃。换一个角度既然答案本身是连续的整数区间而这个区间随着k增大可行性从False逐渐变成True那我们其实是在一个单调序列上二分查找第一个True的位置。这个序列不需要真的存在内存里只需要通过can_finish函数可以随时访问它的值就可以。4.3 mid边界和while写法死循环与溢出都在这里二分的时候搜索下界left是1因为速度最少每小时一根上界right可以直接取max(piles)因为如果你每小时能吃下最多那一堆的量那最多一堆只需要一小时吃完所有堆的时间不可能超过piles的数量肯定满足总时长限制。之后的二分模板用我自己的习惯写法是class Solution: def minEatingSpeed(self, piles: List[int], h: int) - int: def can_finish(k: int) - bool: hours 0 for p in piles: hours (p k - 1) // k return hours h left, right 1, max(piles) while left right: mid (left right) // 2 if can_finish(mid): right mid else: left mid 1 return left这个模板里最容易出问题的是mid更新时到底是right mid还是left mid 1。判断逻辑是如果当前速度mid能在h小时内吃完说明mid这个速度是可行的那答案就一定小于等于mid所以把右边界收到mid。如果当前速度吃不完说明mid不够答案一定比mid大所以左边界设成mid 1。由于循环条件是left right最后退出时left和right相等那个位置就是第一个满足条件的速度。两个小注意点。第一mid用(left right) // 2也就是向下取整配合left mid 1使用时不会出现死循环。如果哪天你换成了左边界不动right mid - 1的另一种模板mid就要相应改成向上取整否则可能来回跳。第二虽然这题数据规模不大但如果你处理的是两个int相加接近上限的题目写成mid left (right - left) // 2会更安全。4.4 同一套模板怎么迁移到其他“最小化xxx”的题吃完香蕉的狒狒看起来像一道独立小模拟但它其实是“二分答案”这个大类里最典型的入门题。LeetCode上一堆让新手头疼的题本质上都在用同一个模板。比如第1011题在D天内送达包裹的能力。求的是船的最小运载能力判断函数就是给定一个载重量weight看能不能在D天内把包裹按顺序运完。再比如第410题分割数组的最大值。求的是把数组分成m段后每段和的最大值最小化。判断函数是给定一个上界limit看能不能让所有子段和都不超过它并且段数不超过m。还有第1482题制作m束花所需的最少天数同样是二分答案。这些题的共同特点可以总结成一个三角色结构题目问的是一个“临界值”比如最小速度、最小运载量、最小天数这个临界值一旦可行所有比它更宽松的值一定也可行存在单调性判断一个值是否可行可以用一次线性扫描或简单DP完成。每次遇到这类题我建议先停下来问三个问题答案范围是什么可行性的单调性在哪里判断函数怎么写如果三个问题都能回答这道题其实已经做完了剩下的就是套二分模板而已。你在LeetCode评论区看到的所谓“这题就是个二分”说的就是前三步。5. 周赛复盘与热门100题把前面三道题的方法沉淀成自己的解题清单5.1 周赛430给我的一次“模式识别”教学回到开头说的周赛430。那晚我复盘了很久最后发现最让我沮丧的不是某道题的知识点没见过而是赛后看题解时那个解法我明明会。赛后总结里我写了一段话卡住的原因不是学得少而是没能在四十分钟内把长长的题目叙述翻译成自己熟悉的模型。周赛70分钟三道题真正考的速度不是打字速度而是模式识别的速度。从那之后我调整了刷题策略不再追求每天刷很多新题而是把同一类模式的题放在一起对比。今天吃透第5题的回文中心扩展明天就去找一道同样是“枚举中心”模型的题来验证。看起来进度变慢了但过两三个月回头看反而比盲目刷题掌握得更牢。5.2 我复盘一道错题的完整动作现在每当我周赛挂掉一道题做的第一件事不是马上看题解而是把当时的代码和思路原样留在编辑器里想一想我卡在哪一步。是没读懂题意是看出来该用动态规划但状态定义错了还是想到了状态定义却没想到空间压缩把卡点记录下来之后再去看题解。看题解时我重点看的是题解作者的“翻译路径”不是代码本身。作者是怎么从题面推导出这个解法的如果是数学题那个等式是怎么来的如果是DP题状态是怎么被定义出来的为什么这么定义如果是二分题单调性从哪来看清路径之后我会把题解关闭白板重写一遍。如果写不出来说明我还没真正理解第二天再重来。三天后我会再刷一遍错题直到能不看题解顺利通过为止。这个流程看起来很繁琐但它才是真正对抗遗忘的办法。LeetCode热门100题如果只是过一遍大概率是“我都做过但记不住解法”如果能挑出里面的经典题按上面流程做到三刷题感会完全不一样。这也是为什么我一直建议与其盲目刷300道新题不如把30道核心题按照“模式识别”的标准吃透。5.3 LeetCode热门100题的正确用法热门100题之所以热门不是因为它简单而是因为它恰好覆盖了面试中最常见的那几类模型双指针、滑动窗口、二叉树遍历、动态规划、二分查找、贪心、图论基础。它本身就适合作为“模式归组”的原始素材而不是用来刷遍数的任务清单。我自己整理标签时会把每道题挂到三个维度下一道题属于哪个模型、模型的本质特征是什么、和它易混淆的模型是什么。比如第5题挂在“字符串-回文-中心扩展”下还要备注“经典错误是想到DP先写DP”第494题挂在“背包-01背包-方案数”下备注“先做数学变形再套背包不要上来DFS”第875题挂在“二分-答案二分-可行性判断”下备注“当问题有单调性且求临界值时优先想二分”。这三个标签放在一起看很有意思最长回文子串教你选择更贴合问题本质的解法目标和教你把搜索问题抽象成集合划分爱吃香蕉的狒狒教你从最优化问题里识别二分答案的单调性。它们背后其实是三种非常重要的思维跳跃解法选型、数学建模、二分答案意识。刷题刷到一定阶段真正能留下的不是那些AC数而是这三个跳跃模型在脑中的反应速度。最后分享一个自己的小习惯我把每道错题凝炼成一句“人话”写在笔记里。第5题的笔记是“回文问题想对称中心不要一上来就枚举区间”第494题的笔记是“正负号想子集和相等想背包”第875题的笔记是“求临界值先想想单调别急着模拟”。下次周赛再遇到类似包装的新题这些句子会第一时间从脑子里跳出来提醒我别慌它其实换了个皮。