企业官网建设流程全解析

打卡 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 Game，hashtable”出现在同一个标题里，其实并不奇怪——它在题单里可能分属不同分类，但在刷题计划中完全可以被安排在同一天。

我当时的做法是，把第四天定成“贪心入门 + 哈希表复习”。新题选 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 题目描述与输入输出示例

55. 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 = 0，i = 0 时 i > farthest 不成立，更新 farthest = max(0, 0) = 0，farthest >= 0 成立，返回 true。正确。

第二个是 nums = [1, 0]。起点能跳一步到终点，结果 true。代码：i = 0 时 farthest 更新为 1，i = 1 时发现 farthest >= 1，返回 true。正确。

第三个是 nums = [2, 0, 0]。从下标 0 可以直接跳到下标 2，结果 true。代码：i = 0 时 farthest = 2，i = 1 时仍可达，farthest 保持 2，i = 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 三种解法的开销对照

为了把这道题彻底吃透，我把三种解法放进一张表里对比。

这张表最有价值的不是最后一行的结论，而是中间那行：DP 明明已经做了“缓存”，为什么还是慢？因为它缓存的是一个布尔值数组，状态之间是“从 i 看后面所有可达位置”的关系。每一次更新都要扫描一个区间，区间长度之和很容易到 n^2。而贪心是把整个可达区间抽象成唯一的关键值，每次更新只做一次取最大值操作，这两种做法的信息密度完全不同。

4.2 从这道题学到的做题顺序

我后来把这道题的思考顺序总结成了一个做题方法：拿到一个可行性判断题，先尝试定义“状态”，再观察状态转移里有没有“单调性”。如果 dp[i] 是否成立只取决于某个不断向外扩张的变量，那大概率可以用一个贪心标量替代整个 dp 数组。

这个规律不是只在 Jump Game 里有效。很多看似需要动态规划的题，只要能够证明每一步的最优决策不依赖前面的精确选择，而是只依赖一个不断更新的边界值，就能转成贪心。遇到这类题时，先写 DP 再看能不能压缩，是一个很稳妥的思考路径。

4.3 和 Jump Game II 的分岔口

如果你接着刷 LeetCode 45，会发现这道题换了个问法：假设总能到达最后一个下标，问最少需要跳几次。这时候贪心依旧能做，但你需要维护两个变量：当前能跳到的边界，以及下一跳能跳到的最远位置。每次越过当前边界时，步数加一，并把边界更新为下一跳最远位置。

这就是为什么我建议先把 55 题彻底想明白再碰 45 题。55 题只需要一个 farthest，45 题需要两个变量配合；如果你没有真正理解“最远可达边界”的含义，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 走到贪心的那个下午，也能提醒自己在写代码之前，先想清楚要保留哪一条最关键的信息。