打卡 Top Interview 150 的第四天我待办清单上排着两样东西55. Jump Game和一个 hashtable 专题。说实话第一眼看到这个组合我以为是排版把两个毫不相关的东西硬凑到一起——一个是数组跳跃一个是查找结构怎么看都不像能互相启发的样子。可等我刷完 Jump Game再回头整理哈希表笔记时忽然发现这两件事其实在讲同一个道理与其把每一个状态都完整存下来不如只留一个最关键的变量或者说最快的索引让判断持续更新下去。如果你也在啃 Top Interview 150或者正准备面试这篇复盘应该能帮上忙。它不只是一道题的标准答案而是我把一道题从递归想到 DP 再想到贪心的完整过程顺带聊聊哈希表为什么会频繁出现在数组题的讨论区以及怎么把一道新题真正消化成自己的东西。1. 为什么第四天我会把 Jump Game 和哈希表排在同一个清单里1.1 Top Interview 150 前三天的常见节奏Top Interview 150 是不少人在准备算法面试时的主力题单它的编排大体按专题走。一开始你会刷很多数组、字符串的基础题之后的题目会慢慢穿插哈希表、贪心、双指针、滑动窗口这些高频考点。排到第四天的时候正好处在一个转折点数组基础题已经热过身哈希表的常见题型开始大面积出现贪心题也偶尔冒出来。所以当你看到“55. Jump Gamehashtable”出现在同一个标题里其实并不奇怪——它在题单里可能分属不同分类但在刷题计划中完全可以被安排在同一天。我当时的做法是把第四天定成“贪心入门 哈希表复习”。新题选 Jump Game然后用一个复习块把哈希表的核心题型过一遍。这种方式最大的好处是一天只消化两个知识点一个偏思路一个偏结构交叉着来反而不容易困。1.2 每天两道题一道新题加一个专题回顾我的打卡模板大概是这样新题固定刷一道专题复习挑一个数据结构或者一类算法。以第四天为例新题是 LeetCode 55专题是 hashtable。刷的时候我还会额外记一个问题这道题里有没有可能用到哈希表如果没有为什么不依赖哈希表也能做到 O(1) 访问这种提问让我慢慢跳出了“看到数组题就套哈希表”的条件反射也让我理解了数据结构选型背后真正的约束。这里提醒一句刷题打卡别只盯着数量。第四天如果一口气刷五道哈希表题看起来进度很快但大概率到周末就忘了大半。反而是一天一道新题配一个旧知识点的回看能让记忆留在更深的地方。1.3 哈希表复习不只是“map 的底层是什么”很多人复习哈希表会先背“底层是数组加链表”或者“红黑树”但说实话面试官更在意的是你什么时候该用哈希表。哈希表解决的问题本质是快速映射根据一个 key 在平均 O(1) 的时间内找到对应的 value。这个特性在刷题里被用在三件事上去重、计数、记录索引。我之所以把 Jump Game 和哈希表放在同一天是因为刷完 Jump Game 后我忽然意识到一个很妙的对照给定一个非负整数数组下标本身就是天然的“哈希键”数组本身就是一个保证 O(1) 访问的映射结构。哈希表只是把这种能力扩展到任意键上而已。所以在追求空间更优时我们会想尽办法用数组代替哈希表而今天这道 Jump Game 更是连数组都可以只扫描一遍不需要额外记录任何东西。2. Jump Game 的第一反应递归回溯与 DP 备忘录有多“自然”就会有多慢2.1 题目描述与输入输出示例Jump Game 的题意其实非常短给你一个非负整数数组 nums你最开始位于数组的第一个下标。每一个元素代表你在该位置可以跳跃的最大长度。你只需要判断能不能跳到最后一个下标。注意是“能不能”不是“最少几步”。比如 nums [2, 3, 1, 1, 4]从下标 0 开始可以跳最多 2 步先跳到下标 1再跳 3 步直接到终点所以是 true。而 nums [3, 2, 1, 0, 4]从下标 0 出发无论怎么跳最后都会落到下标 3 这个位置那里可跳长度为 0无法继续前进所以是 false。这个题看起来像是模拟题但真正写代码的时候第一反应往往不是贪心而是递归。2.2 直觉是 DFS 回溯枚举每一种跳法最开始拿到题目绝大多数人都会这样想从下标 0 开始每一步选择跳 1 步、2 步一直到 nums[i] 步只要其中有一种选择能到达终点就说明可以抵达。这种思路对应的就是 DFS 回溯。def canJump(nums): def dfs(pos): if pos len(nums) - 1: return True for step in range(1, nums[pos] 1): if dfs(pos step): return True return False return dfs(0)这段代码很直观但复杂度是灾难性的。假设数组里每个位置都能跳很远比如 nums [5, 5, 5, 5, ...]那么每一步都会分裂成最多 5 个分支整棵递归树呈指数增长。LeetCode 上通常会有一组长数组样例这段代码跑上去直接超时。我把这个直觉称为“最自然但最不划算”的思路。新手阶段写 DFS 没有错错的是在看到可行性判断时没有继续追问一步这些子问题之间有没有重复能不能把已经算过的结果留作缓存2.3 加备忘录优化成 DP 状态仔细观察上面的递归树会发现位置 pos 是否可达终点其实和“之前是怎么到达 pos 的”没有关系。比如你从下标 0 跳到 2和从 0 跳到 1 再跳到 2只要到了 2后面的事就只取决于 2。这种“后续状态只由当前点决定”的特性就是无后效性。于是很自然地可以加一个 memo 数组把每个位置的结果缓存起来。这个版本叫记忆化搜索本质上就是自顶向下的动态规划。def canJump(nums): n len(nums) memo [None] * n # None 表示未知True 表示能到终点False 表示不能 memo[-1] True def dfs(pos): if memo[pos] is not None: return memo[pos] max_step nums[pos] for step in range(1, max_step 1): nxt pos step if nxt n and dfs(nxt): memo[pos] True return True memo[pos] False return False return dfs(0)这个版本能不能过分情况。如果测试数据比较温和它能跑完但时间复杂度还是很高。每个位置 pos 要枚举它所有能跳到的后续位置最坏情况下是 O(n^2)空间 O(n)。LeetCode 55 的数组长度可以到 10^4最坏情况下的平方复杂度通常会被设计成超时。所以 DP 并不是这道题的终点它只是让我们意识到我们已经把状态压缩到了“一个位置一个结果”却仍然在重复扫描区间。2.4 为什么 DP 在这道题上显得笨重dp 状态的本质是位置 i 是否能到终点取决于所有在 i 的可达区间内的位置。这个依赖关系需要遍历区间才能确定。可问题是我们真的需要精确知道每个位置能不能到终点吗其实我们需要知道的是“当前已经探索过的位置里最远能到哪里”。如果最远可达位置已经覆盖了终点那结果就是 true如果遍历过程中出现了一个位置连前面的最远边界都没到达那说明中间出现了无法跨越的断层结果就是 false。到这个节点贪心的答案已经呼之欲出了。3. 贪心解法记录最远可达位置而不是关心每一步怎么跳3.1 关键观察可达位置一定是连续的贪心解法有一个重要的前提观察从起点 0 开始所有可达的下标在数轴上会形成一个连续区间 [0, max_reach]。为什么是连续的呢因为你在任何一个位置 i 能跳的步长范围是 1 到 nums[i]中间不会有缺失的整数。哪怕某个中间位置本身跳不远只要你曾经到达过它那么它左边所有位置也一定已经被到达过。这样我们维护一个变量 farthest表示遍历到当前位置为止能够到达的最远下标。只要当前位置 i 还没有超过 farthest就说明当前这个位置是可达的然后用它去更新 farthest max(farthest, i nums[i])。如果某一次循环发现 i farthest说明当前位置已经超出了所有可达范围直接返回 false。如果 farthest 已经大于等于 n - 1说明终点已经在射程内返回 true。3.2 算法步骤初始化 farthest 0。遍历 i 从 0 到 n-1如果 i farthest说明当前位置不可达直接返回 False。更新 farthest max(farthest, i nums[i])。如果 farthest n - 1返回 True。循环结束返回 True实际上通常提前返回。3.3 Python 代码def canJump(nums): n len(nums) farthest 0 for i in range(n): if i farthest: return False farthest max(farthest, i nums[i]) if farthest n - 1: return True return True这段代码的时间复杂度是 O(n)空间复杂度 O(1)。很多人第一次看会觉得“就这”是的就这。但难的地方不是代码而是你怎么能从 DFS 一路走到这个简洁的结论。面试时如果你能先把 DP 思路讲清楚再给这个贪心优化说服力会强很多。3.4 用生活类比解释为什么够用可以想象自己在开荒一张地图你每到一个地点地图会告诉你最多还能往前跨几步。你不需要真的把每个位置都踩一遍只需要拿一张纸不断更新“我的探索队最远已经推进到了哪个位置”。只要这个最远位置一直在向前走后面就算遇到某个点跳不动了你也可以绕道从更早的位置跨过去。而如果最远位置被卡住了比如地图显示只能走到下标 3但你现在人在下标 4那就说明前面已经无路可走宣告失败。这个类比对应到代码里就是 i 和 farthest 的关系i 是你的“当前坐标”farthest 是“已探索边界”。只要当前坐标没有超出边界你总能找到一条路走过来。3.5 边界情况和常见反直觉用例有几个用例值得单独拎出来说。第一个是 nums [0]。此时你已经在最后一个下标结果应为 true。代码执行过程farthest 0i 0 时 i farthest 不成立更新 farthest max(0, 0) 0farthest 0 成立返回 true。正确。第二个是 nums [1, 0]。起点能跳一步到终点结果 true。代码i 0 时 farthest 更新为 1i 1 时发现 farthest 1返回 true。正确。第三个是 nums [2, 0, 0]。从下标 0 可以直接跳到下标 2结果 true。代码i 0 时 farthest 2i 1 时仍可达farthest 保持 2i 2 时 farthest 2返回 true。正确。第四个是 nums [3, 2, 1, 0, 4]。这个用例经常让人产生误解下标 3 的值为 0看起来是唯一卡点。其实不是“遇到 0 就一定失败”而是“最远边界被锁死在 0 所在的位置”。代码会一直执行到 i 4发现 i farthest于是返回 false。关键点在于当 farthest 不再增长时边界就变成了一堵墙一旦当前位置越过墙就说明已经无路可走。4. 回溯、DP、贪心三种解法在 55 题上的真实对比4.1 三种解法的开销对照为了把这道题彻底吃透我把三种解法放进一张表里对比。解法核心思想时间复杂度空间复杂度实际表现DFS 回溯枚举所有跳跃路径指数级O(n) 递归栈大样例直接超时DP 记忆化缓存每个位置能否到终点O(n^2)O(n)中等数据能过但不够优雅贪心维护最远可达边界O(n)O(1)最优解面试最想看到这张表最有价值的不是最后一行的结论而是中间那行DP 明明已经做了“缓存”为什么还是慢因为它缓存的是一个布尔值数组状态之间是“从 i 看后面所有可达位置”的关系。每一次更新都要扫描一个区间区间长度之和很容易到 n^2。而贪心是把整个可达区间抽象成唯一的关键值每次更新只做一次取最大值操作这两种做法的信息密度完全不同。4.2 从这道题学到的做题顺序我后来把这道题的思考顺序总结成了一个做题方法拿到一个可行性判断题先尝试定义“状态”再观察状态转移里有没有“单调性”。如果 dp[i] 是否成立只取决于某个不断向外扩张的变量那大概率可以用一个贪心标量替代整个 dp 数组。这个规律不是只在 Jump Game 里有效。很多看似需要动态规划的题只要能够证明每一步的最优决策不依赖前面的精确选择而是只依赖一个不断更新的边界值就能转成贪心。遇到这类题时先写 DP 再看能不能压缩是一个很稳妥的思考路径。4.3 和 Jump Game II 的分岔口如果你接着刷 LeetCode 45会发现这道题换了个问法假设总能到达最后一个下标问最少需要跳几次。这时候贪心依旧能做但你需要维护两个变量当前能跳到的边界以及下一跳能跳到的最远位置。每次越过当前边界时步数加一并把边界更新为下一跳最远位置。这就是为什么我建议先把 55 题彻底想明白再碰 45 题。55 题只需要一个 farthest45 题需要两个变量配合如果你没有真正理解“最远可达边界”的含义46 题会很容易写错边界更新的时机。从一变量到两变量的演进是贪心距离感的一次很好锻炼。4.4 一个让我改掉“背写法”的关键问题我刷这道题时犯过一个典型错误看到某位题解里写了“遇到 nums[i] 0 就返回 false”于是照着背。结果遇到 [2, 0, 1, 1, 4] 时被顶回来了。这个用例里下标 1 的值是 0解释却仍然是 true因为你可以从下标 0 直接跳到下标 2避开 0 所在的坑位。真正的原因是0 并不是失败条件只有“最远边界被卡住且当前遍历点越过边界”才是失败条件。也就是说nums[i] 0 本身不可怕可怕的是它出现在 farthest 的边界上并且没有其他位置能帮你越过这个边界。死记硬背结论不如理解边界条件背后的过程。5. Hashtable 与 Jump Game 的思维暗线用固定状态取代全量记录5.1 今天把 hashtable 放在一起的真实原因刚才花了大篇幅讲贪心现在回头解释标题里为什么还有 hashtable。哈希表在刷题里的核心价值是“用空间换时间的高速索引”。当你需要一个键到值的映射时数组把键限制为下标哈希表则把键扩展为任意类型。可换个角度看哈希表本身也在做一件事用一个固定的映射规则把庞大的信息压缩到可快速查询的结构里。这道 Jump Game 恰好是反面例子它不需要额外的哈希表因为数组已经天然提供了下标映射而且值就是可跳跃长度。更要紧的是我们连数组都不需要额外存储一份只需要在线扫描过程中维护一个标量 farthest。从“用哈希表存下每个位置能否到达”到“只用一个标量代表整个可达区间”是一种信息压缩的跃迁这个思维过程和哈希表很像只是压缩的目标更极端。5.2 常见哈希表题型的答题框架我在第四天顺带整理了三类最常见的哈希表题型这里简单罗列一下答案框架。第一类是两数之和类型遍历的时候查 target - 当前值是否在哈希表里如果在直接得到答案如果不在就把当前值和下标登记进去。哈希表负责保存“已经见过的值”用空间换时间。第二类是去重和重复判断类型比如判断数组里有没有重复元素或者判断两个重复元素的下标距离是否不超过 k。这类题用 set 或者 map 记录最后一次出现的位置每次遍历查一下即可。第三类是连续序列类型先把所有数放进 set然后只对序列的起点做向后查找避免重复扫描。这里的哈希表更像是一个“快速判断某个数是否存在”的集合。这三类有一个共同点哈希表的价值不在于存储本身而在于你可以随时回答“这个元素是不是已经出现过”或者“这个值对应的信息是什么”。这和 Jump Game 中“更新最远边界”其实是一枚硬币的两面都是在维护一个可以快速读取的关键状态。5.3 哈希表的一个隐藏坑时间复杂度是均摊不是绝对刷题时我习惯用哈希表但有一点需要特别提醒哈希表的 O(1) 是均摊意义下的不是绝对保证。如果哈希函数设计得很差或者所有 key 都产生了冲突最坏情况下插入和查找会退化到 O(n)。LeetCode 测试数据通常不会专门整你但面试官很喜欢拿这个问题追问。如果数据范围很小比如字符串只包含 26 个小写字母那么用长度 26 的数组代替哈希表会更稳定。这本质上是一个“受限哈希表”把 key 直接映射到固定下标。在日常开发里不一定有这个限制条件但在刷题场景中能够想到这种替换说明你对哈希表的理解已经从“会用 API”进化到了“会设计映射”。5.4 把“哈希表思维”用到贪心问题里我真正觉得这天收获最大的是意识到哈希表思维和贪心思维并不冲突。哈希表思维是“给我一个 key我要快速得到 value”贪心思维是“给我一段历史信息我只要保留最关键的摘要”。这两者的结合点就是“状态压缩”。在 Jump Game 里所有可达下标被压缩成一个最远点 farthest。你可以把它想象成一个区间哈希表的 key区间内所有下标共享同一个可达状态。只是因为我们追求的是最右端所以只需要保存右边界不需要保存整个区间。理解了这点后再看很多题解里写的“XXX 可以优化成一个变量”你就不会觉得那是魔术而是会想“这里是把什么状态压缩成了什么”。6. Top Interview 150 第四天复盘从看懂题解到写进笔记的距离6.1 我的刷题四步流程每次刷题我都会走一套固定流程第四天也是这样。先说结果这道题我完整跑完花了大概一小时四十分钟其中有一大半时间花在“看题解之后觉得自己懂了但关掉题解重新写时卡住”的过程里。流程大致是四步第一步独立思考十分钟。哪怕想不出来也要把混乱的思路和疑问写下来。第二步看题解。重点看最优解为什么要那么做尤其是“为什么能贪心”的证明部分。第三步关掉题解空手写一遍代码。这一步会立刻暴露你有没有真正掌握。第四步写笔记。笔记里不抄题解原文只用自己的话把思考过程重新讲一遍。第四天我在第三步卡住了。问题出在一个很简单的地方我以为记住“遇到 i farthest 就返回 false”就够了但实际写代码时忘记把 farthest 的更新放在循环开头还是结尾导致有一次用例输出错误。后来我意识到这不是语法问题而是我没有理解这个变量的生命周期遍历到 i 时farthest 必须代表“从起点到 i-1 这一段能到达的最远位置”。只有先把 i 是否可达判断完才能考虑用 i 去更新 fartherst。6.2 我用的笔记本模板如果你也想把刷题笔记做得不流于形式可以参考我的模板一共四块题目编号和一句话记忆点。我的初始错误思路是什么。最优解的核心思路以及它为什么对。同类题链接和下次要复习的时间。对于 Jump Game我写下的一句话记忆点是“用一个不断向外扩张的边界标记判断每个位置是否被覆盖。”这句话比背代码有用得多。过几天回来看笔记时只要看到这句话我就能立刻从 0 把整个算法推出来。6.3 第四天的时间分配和效率心得我实际的时间分配是这样的前十到十五分钟快速把哈希表常见题型扫一遍算作复习接下来二十分钟在草稿纸上演算 Jump Game 的 DFS 和 DP 解法试图寻找规律之后五十分钟沉浸在题解的证明和三种解法对比里最后二十分钟挑了一道哈希表练习题做收尾。有读者可能会觉得刷一道题花一个多小时太慢了。但我的经验是前期的慢会在后期加倍赚回来。算法题的难点不是某道题的答案而是你面对陌生题时建立起的那套分析路径。如果你能把“DFS 超时、DP 可以但不够好、贪心最优”的完整推理链条走顺以后遇到类似题目的时候就不会一上来只背结论。6.4 关于“Top Interview 150 要不要全刷”的体会Top Interview 150 这个题单有价值的点不在于“刷完 150 道”这个数字而在于它帮你把算法考点分好了类。但我个人强烈建议不要机械地按题号从上到下刷而要按专题交叉着刷。第四天的“贪心 哈希表”就是一个例子两个知识点互相不重叠但思维上又有呼应反而会比连续刷十道数组题让人印象更深。如果你已经刷到第四天感觉有点焦虑进度不够快我特别能理解。请放宽心把每一天的重点放在“我真的理解了什么”而不是“我完成了多少题”。面试最终看的是解决问题的能力不是计数器上的数字。6.5 这天的打卡里我最想留下的话最后分享一句我在当天笔记末尾写的话最远的距离不是一步步走出来而是一开始就知道自己最远能走到哪哈希表的价值也不是存得多而是查得快。这句话现在仍然写在我那页笔记的边上每次看到它我都能想起从 DFS 走到贪心的那个下午也能提醒自己在写代码之前先想清楚要保留哪一条最关键的信息。