更新题目 55. Jump Game

题目 lc55 · 修改（rev 2） · cc · 2026-10-27 00:34
body

@@ -1,7 +1,10 @@
 ## 题目
 
-`nums[i]` 是在位置 i 最多能往前跳几步。从位置 0 出发，问能不能到达最后一个位置。
+给一个非负整数数组 `nums`，`nums[i]` 是站在下标 i 时最多能往右跳几步（可以跳 1 到 `nums[i]` 步中的任意一种）。从下标 0 出发，问能不能到达最后一个下标。
 
-follow-up 是 LC45：保证能到达最后一个位置，问最少跳几次。
+- `[2, 3, 1, 1, 4]` 返回 True：从 0 跳 1 步到 1，再从 1 跳 3 步到 4。
+- `[3, 2, 1, 0, 4]` 返回 False：不管怎么跳都会停在下标 3，`nums[3] = 0`，过不去。
+
+常见的 follow-up 是 LC45 Jump Game II：题目保证一定能到达最后一个下标，问最少跳几次。`[2, 3, 1, 1, 4]` 的答案是 2（0 → 1 → 4）。
 
 [LC55](https://leetcode.com/problems/jump-game/) · [LC45](https://leetcode.com/problems/jump-game-ii/)
@@ -9,5 +12,10 @@
 ## 面经里怎么考的
 
-947513（backend NG，2022 Q4，Fail）：先考 LC55，follow-up 是 LC45【推断："舞舞""肆五"】。这类"看起来像 DP、其实贪心更好"的题和 GD 2025-03 那句评价的描述也对得上。
+- Visa：Senior Software Engineer 的 VO 第一轮（project 加 coding），coding 部分是 LC55 原题。这场面试楼主最后没拿到 offer，帖子的结果是整场的，不一定是这道题没答好。
+- Hive：backend NG（2022 Q4），先考 LC55，follow-up 是 LC45，原帖用谐音「舞舞」「肆五」写的题号。楼主这次面试挂了。
+- Temu：Payments backend 组的店面考 LC45，楼主没想到贪心。
+- Amazon：SDE II onsite 的 Round 2 DSA 考「跳跃游戏」，记录里没写是 55 还是 45。这场面试楼主最后也没拿到 offer，同样不一定是这道题的问题。
+
+Hive 那篇是先考 LC55 再追问 LC45，Temu 直接考 LC45，所以两题要连着准备。Temu 那位卡在想不到贪心，面试时可以先说出 DP 做法，再讲怎么用贪心降到 $O(n)$（见 Follow-up 第一条）。
 
 ## 思路
@@ -15,49 +23,82 @@
 ### LC55：能不能跳到最后
 
-**贪心：**维护目前能到达的最远位置 reach，从左往右扫。如果当前位置 i 已经超过了 reach，说明根本走不到这里，返回 False；否则用 `i + nums[i]` 更新 reach。
+从左往右扫，维护一个变量 `farthest`，意思是「下标 0 到 i − 1 里所有能到达的位置，最远能跳到哪个下标」。扫到下标 i 时分两种情况：
 
-**为什么贪心是对的：**能到达的位置一定是从 0 开始的一段连续区间。因为如果能从位置 i 跳到 j，那 i 和 j 之间的每个位置也都能跳到。所以只需要记住这段区间的右端点。
+- `i > farthest`：前面所有能到的位置都跳不到 i，i 到不了，i 后面的下标更到不了，直接返回 False。
+- `i <= farthest`：i 能到达，从 i 最远能跳到 `i + nums[i]`，用它更新 `farthest`。
+
+扫完都没返回 False，说明每个下标都能到达，包括最后一个。
+
+这样做对，是因为**能到达的下标一定是从 0 开始的一段连续区间**。站在下标 p 能跳 1 到 `nums[p]` 步，所以 p 到 `p + nums[p]` 之间的每个下标都能到。从 0 开始，每个能到的位置都把一段紧挨着的区间加进来，合起来始终是 `[0, farthest]` 这一段，中间不会有空洞。于是只需要记住区间的右端点 `farthest`，扫到第一个落在区间外的下标就说明卡住了。
+
+拿 `[3, 2, 1, 0, 4]` 走一遍：i = 0 到 3 时 `farthest` 分别是 3、3、3、3，i = 4 时 `4 > 3`，返回 False。
+
+> [!say] The set of reachable indices is always a prefix of the array, because from index i I can land on any index up to i plus nums[i]. So I only track the farthest reachable index. If I ever scan an index beyond it, that index is unreachable and I return false.
 
 ### LC45：最少跳几次
 
-**按 BFS 的层来理解：**第 0 层是位置 0；第 1 层是跳一次能到的所有位置；第 k 层是跳 k 次能到、但跳 k − 1 次到不了的位置。每一层也是一段连续区间，所以只需要记录当前这一层的右端点 cur_end，以及从这一层出发能到的最远位置 farthest。扫到 cur_end 时，当前这一层走完了，想继续往前就必须再跳一次，于是 steps 加 1，下一层的右端点变成 farthest。
+按 BFS 的层来看。第 0 层是下标 0。第 k 层是「最少要跳 k 次才能到」的下标。和 LC55 同样的道理，跳不超过 k 次能到的下标是一段从 0 开始的连续区间，所以每一层也是一段连续区间，紧接在上一层后面。
+
+用两个变量记录层：
+
+- `layer_end`：当前这一层的右端点，也就是跳 `jumps` 次最远能到哪。
+- `next_layer_end`：从已经扫过的下标再跳一次，最远能到哪。这就是下一层的右端点。
+
+从左往右扫，每个下标 i 先用 `i + nums[i]` 更新 `next_layer_end`。扫到 `i == layer_end` 时，当前这一层扫完了，终点还没到，必须再跳一次：`jumps` 加 1，`layer_end` 换成 `next_layer_end`。
+
+拿 `[2, 3, 1, 1, 4]` 走一遍：i = 0 时 `next_layer_end` 变成 2，同时 i 等于 `layer_end`（0），换层，`jumps` 为 1，`layer_end` 为 2。i = 1 把 `next_layer_end` 推到 4。i = 2 又等于 `layer_end`，换层，`jumps` 为 2，`layer_end` 为 4。i = 3 不换层。下标 4 是终点，不扫，答案是 2。第 1 层是下标 1 到 2，第 2 层是下标 3 到 4。
+
+这个答案是最少跳数，因为第 k 层的右端点就是跳 k 次能到的最远下标。终点第一次落进某一层时，那一层的编号就是最少跳数，跳更少的次数连那一层都到不了。
+
+> [!say] For Jump Game II, I think of it as BFS by layers. Each layer is a contiguous range of indices reachable with the same minimum number of jumps. I track where the current layer ends and the farthest index reachable from it. When I reach the end of the current layer, I have to jump once more, and the next layer ends at that farthest index. It's O(n) time and O(1) space.
 
 ## 代码
 
 ```python
-def canJump(nums):
-    reach = 0
-    for i, x in enumerate(nums):
-        if i > reach:               # 走到了够不着的位置
-            return False
-        reach = max(reach, i + x)
-    return True
+from typing import List
 
-def jump(nums):
-    steps = cur_end = farthest = 0
-    for i in range(len(nums) - 1):
-        farthest = max(farthest, i + nums[i])
-        if i == cur_end:            # 当前这一跳能到的范围走完了，必须再跳一次
-            steps += 1
-            cur_end = farthest
-    return steps
+
+class Solution:
+    def canJump(self, nums: List[int]) -> bool:
+        """LC55：从下标 0 出发，能不能到达最后一个下标。"""
+        farthest = 0                      # 目前能到达的最远下标
+        for i, step in enumerate(nums):
+            if i > farthest:              # 下标 i 够不着，后面的也够不着
+                return False
+            farthest = max(farthest, i + step)
+        return True
+
+    def jump(self, nums: List[int]) -> int:
+        """LC45：保证能到达最后一个下标，求最少跳几次。"""
+        last = len(nums) - 1
+        jumps = 0
+        layer_end = 0                     # 跳 jumps 次能到达的最远下标
+        next_layer_end = 0                # 再跳一次能到达的最远下标
+        for i in range(last):             # 不扫最后一个下标：到了就不用再跳
+            next_layer_end = max(next_layer_end, i + nums[i])
+            if i == layer_end:            # 这一层扫完了，还没到终点，必须再跳一次
+                jumps += 1
+                layer_end = next_layer_end
+        return jumps
 ```
+
+2026-10-27 用 Python 3.13 跑过：
+
+- 示例 `[2, 3, 1, 1, 4]`、`[3, 2, 1, 0, 4]`、`[0]`、`[1, 1]`、`[2, 0, 0]` 的结果分别是 True 和 2、False、True 和 0、True 和 1、True 和 1。
+- 和暴力解对拍：暴力解从下标 0 做 BFS，求出到最后一个下标的最少跳数，到不了就是 None。随机生成 20 万组长度 1 到 8、元素 0 到 4 的数组，`canJump` 和「暴力解不是 None」全部一致。其中 150600 组能到达，`jump` 和暴力解的跳数全部一致。
 
 ## 复杂度
 
-两题都是时间 O(n)、空间 O(1)。
+两题都只扫一遍数组，时间 $O(n)$，额外空间 $O(1)$。
 
 ## 易错点
 
-- **LC45 的循环只到 len(nums) − 2。**到达最后一个位置以后不需要再跳。如果循环包括最后一个位置，当 cur_end 恰好等于它时会多算一跳。
-- `[0]` 只有一个元素时，LC55 返回 True，LC45 返回 0。
+- **LC45 的循环不能扫到最后一个下标。**终点恰好是某一层的右端点时，扫到终点又会触发一次 `i == layer_end`，多加一跳。把循环改成 `range(len(nums))` 的错误版本，`[2, 3, 1, 1, 4]` 返回 3（正确是 2），`[0]` 返回 1（正确是 0）。在下面对拍用的 150600 组能到达的随机输入里，错误版本有 70547 组多算了 1 跳（2026-10-27 实测）。
+- **LC55 要先判断 `i > farthest`，再更新 `farthest`。**顺序反了，够不着的下标也会用自己的 `i + nums[i]` 去更新。`[0, 1]` 正确答案是 False，顺序反了的版本返回 True（2026-10-27 实测）。
+- **LC45 的代码依赖「一定能到达」这个前提。**`[0, 1]` 实际到不了，`jump` 却返回 1。面试官要是改成「到不了返回 −1」，就在 `i == layer_end` 时先判断：`next_layer_end <= i` 说明再跳一次也离不开下标 i，返回 −1。这个改法 2026-10-27 和暴力解在 20 万组随机输入上对拍过，结果全部一致。
 
 ## Follow-up
 
-- **为什么不用 DP：**dp[i] 表示到 i 的最少跳数，要从前面所有能跳到 i 的位置转移，O(n²)。可以先说出 DP，再说贪心把它降到 O(n)。
-- **输出具体的跳法：**在扫每一层时记下是哪个位置把 farthest 推到了最远，换层时把它记成这一跳的落脚点。
-- **LC1306 Jump Game III**（可以往左也可以往右跳，问能不能到值为 0 的位置）：这时区间不连续了，改用 BFS 或 DFS。
-
-## 英文讲法
-
-> [!say] For Jump Game II, I think of it as BFS by layers. Each layer is a contiguous range of indices reachable with the same number of jumps. I track where the current layer ends and the farthest index reachable from it. When I reach the end of the current layer, I have to jump once more, and the next layer ends at that farthest index. It's O(n) time and O(1) space.
+- **先想到 DP 怎么办【推断】。**Temu 那篇楼主没想到贪心，DP 是更容易先想到的做法。`dp[i]` 表示到下标 i 的最少跳数，要从前面所有能跳到 i 的下标转移过来，时间 $O(n^2)$。面试里可以先说出 DP，再说明能到的下标总是连续区间，每一层只要记右端点，扫一遍就够，降到 $O(n)$。
+- **输出具体的跳法【推断】。**扫的时候额外记下把 `next_layer_end` 推到最远的那个下标，每次换层就把它记成这一跳的起跳点，最后补上终点。从这个下标起跳，下一层能到得最远，所以跳数等于 `jump()` 的结果，时间仍是 $O(n)$。2026-10-27 按这个做法写了代码，在约 15 万组能到达的随机输入上检查过：路径从 0 开始、到终点结束，每一跳不超过起跳点的 `nums` 值，跳数和暴力解一致。
+- **LC1306 Jump Game III【推断】。**每个下标往左或往右跳正好 `nums[i]` 步，问能不能到达值为 0 的下标。步数固定后能到的下标不再连续，「只记右端点」不成立，改成在下标上做 BFS 或 DFS，用 visited 数组去重，时间和空间都是 $O(n)$。
更新题目 55. Jump Game

body

meta
