跳跃游戏 I 与 II
使用贪心的范围扩展方法确定可达性和最少跳跃次数，从而避免使用 DP。
跳跃游戏 I 与 II 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
跳跃游戏 I：您能到达终点吗？
跳跃游戏 I（LeetCode 55）：给定一个数组，其中 nums[i] 表示从索引 i 出发时能够跳跃的最大长度，判断从索引 0 出发是否能够到达最后一个索引。对于 [2, 3, 1, 1, 4]，您可以到达终点（先从 2 跳到 3，然后从 3 到达终点）。对于 [3, 2, 1, 0, 4]，您无法到达终点（总会落在 0 上，而它的跳跃长度为 0）。贪心解法的时间复杂度为 O(n)。
# Can you reach the last index?
nums1 = [2, 3, 1, 1, 4] # True: 0→1→4 or 0→2→3→4
nums2 = [3, 2, 1, 0, 4] # False: always land on index 3 (value 0)
# At index 3 (value 0): no matter how you get here,
# you can't jump further to reach index 4
print('nums1 last index:', len(nums1)-1)
print('nums2 index 3 jump value:', nums2[3]) # 0 = stuck贪心：跟踪最大可达位置
跳跃游戏 I 的贪心洞察是：维护 max_reach，表示当前为止能够到达的最远索引。在每个索引 i 处，更新 max_reach = max(max_reach, i + nums[i])。如果某一时刻 i > max_reach，则当前索引不可达——返回否定结果。如果到达或越过最后一个索引，则返回肯定结果。不需要 DP 或回溯。
def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: # can't reach index i
return False
max_reach = max(max_reach, i + jump)
if max_reach >= len(nums) - 1:
return True # early exit
return True
print(can_jump([2, 3, 1, 1, 4])) # True
print(can_jump([3, 2, 1, 0, 4])) # False
print(can_jump([0])) # True (already at last index)
print(can_jump([1, 0, 0])) # False跟踪跳跃游戏 I
跟踪 [3, 2, 1, 0, 4]：i=0，jump=3，max_reach=3。i=1，jump=2，max_reach=max(3,3)=3。i=2，jump=1，max_reach=max(3,3)=3。i=3，jump=0，max_reach=max(3,3)=3。i=4，i=4 > max_reach=3 → 返回否定结果。该算法正确识别出索引 4 不可达。由于索引 3 处的 0 将 max_reach 限制为 3，从索引 0 出发的每条路径都会被困住。
def can_jump_trace(nums):
max_reach = 0
for i, jump in enumerate(nums):
print(f'i={i}, jump={jump}, max_reach before={max_reach}', end='')
if i > max_reach:
print(' → UNREACHABLE')
return False
max_reach = max(max_reach, i + jump)
print(f' → max_reach={max_reach}')
return True
print('Result:', can_jump_trace([3, 2, 1, 0, 4]))跳跃游戏 II：最少跳跃次数
跳跃游戏 II（LeetCode 45）要求求出到达最后一个索引所需的最少跳跃次数（题目保证始终可达）。贪心方法采用范围扩展策略：维护当前跳跃的最远可达位置（curr_end）和下一次跳跃的最远可达位置（farthest）。当当前跳跃的范围耗尽时，您必须进行一次跳跃——增加 jumps，并将 curr_end = farthest。
def jump(nums):
n = len(nums)
if n == 1: return 0 # already at destination
jumps = 0
curr_end = 0 # end of current jump's range
farthest = 0 # farthest reachable in next jump
for i in range(n - 1): # don't jump from last index
farthest = max(farthest, i + nums[i])
if i == curr_end: # exhausted current jump range
jumps += 1
curr_end = farthest
if curr_end >= n - 1: break
return jumps
print(jump([2, 3, 1, 1, 4])) # 2 (0→1→4)
print(jump([2, 3, 0, 1, 4])) # 2 (0→1→4)
print(jump([1, 2, 1, 1, 1])) # 3可视化理解跳跃游戏 II
可以把跳跃游戏 II 理解为一种逐层 BFS方法，只是没有队列开销。每次跳跃对应一层 BFS。curr_end 是当前层的边界，farthest 是下一层可到达的最大索引。当完成对当前层的扫描（i == curr_end）时，您已经确定了下一层的边界，并且必须增加跳跃次数。这相当于在隐式图上执行 BFS，时间复杂度为 O(n)，空间复杂度为 O(1)。
def jump_traced(nums):
n = len(nums)
jumps = curr_end = farthest = 0
for i in range(n - 1):
farthest = max(farthest, i + nums[i])
print(f'i={i}: farthest={farthest}, curr_end={curr_end}')
if i == curr_end:
jumps += 1
curr_end = farthest
print(f' → JUMP #{jumps}, new range ends at {curr_end}')
if curr_end >= n - 1: break
return jumps
print('Min jumps:', jump_traced([2, 3, 1, 1, 4]))为什么跳跃游戏 II 的贪心解法正确
为什么贪心方法（始终扩展到最远位置）能够得到最少跳跃次数？交换论证如下：假设最优解进行了一次没有到达最远位置的跳跃。我们总可以将这次跳跃延长到 farthest，而不会增加任何额外代价——它仍然只算一次跳跃。通过每次跳跃都选择最大的范围，我们就能保证所需跳跃次数最少。任何每次跳得更近的解法都不可能做得更好，反而需要更多次跳跃才能覆盖相同的距离。
# Correctness verification: compare to BFS
from collections import deque
def jump_bfs(nums):
n = len(nums)
if n == 1: return 0
visited = [False] * n
visited[0] = True
queue = deque([0])
level = 0
while queue:
level += 1
for _ in range(len(queue)):
pos = queue.popleft()
for j in range(1, nums[pos] + 1):
nxt = pos + j
if nxt >= n - 1: return level
if not visited[nxt]:
visited[nxt] = True
queue.append(nxt)
return -1
# Both should give same results
for nums in [[2,3,1,1,4],[2,3,0,1,4],[1,2,1,1,1]]:
print(jump(nums), '==', jump_bfs(nums))跳跃游戏 II 的 DP 替代方案
一种 DP 解法是：dp[i] 表示到达索引 i 所需的最少跳跃次数。对于每个位置 j，更新所有可达的位置：当 k 取 1..nums[j] 时，执行 dp[j+k] = min(dp[j+k], dp[j]+1)。该方法的时间复杂度为 O(n × max_jump)，空间复杂度为 O(n)，比时间复杂度为 O(n) 的贪心方法慢得多。在这里贪心方法更优；展示 DP 是为了进行对比，说明贪心方法如何避免内层循环。
def jump_dp(nums):
n = len(nums)
dp = [float('inf')] * n
dp[0] = 0
for j in range(n):
for k in range(1, nums[j] + 1):
if j + k < n:
dp[j+k] = min(dp[j+k], dp[j] + 1)
return dp[n-1]
print(jump_dp([2, 3, 1, 1, 4])) # 2
print(jump_dp([1, 2, 1, 1, 1])) # 3
# Greedy is O(n), DP is O(n * max_jump)
# For large inputs with big jump values, greedy is much faster跳跃游戏 III：到达索引 0
跳跃游戏 III（LeetCode 1306）：从给定索引开始；从索引 i 可以跳到 i + nums[i] 或 i - nums[i]。您能到达值为 0 的任意索引吗？这是一个可达性问题（BFS/DFS），而不是最小化问题，因此贪心不适用。使用带有已访问集合的 BFS 来避免循环。时间复杂度为 O(n)。
from collections import deque
def can_reach(arr, start):
n = len(arr)
visited = set()
queue = deque([start])
while queue:
idx = queue.popleft()
if arr[idx] == 0: return True
if idx in visited: continue
visited.add(idx)
for nxt in [idx + arr[idx], idx - arr[idx]]:
if 0 <= nxt < n and nxt not in visited:
queue.append(nxt)
return False
print(can_reach([4,2,3,0,3,1,2], 5)) # True (5→4→1→3, arr[3]=0)
print(can_reach([3,0,2,1,2], 2)) # False (can't reach index 1, arr[1]=0)跳跃游戏 VII：通过范围判断可达性
跳跃游戏 VII（LeetCode 1871）：给定一个二进制字符串，您能否从索引 0 跳到最后一个索引；从位置 i 可以跳到区间 [i+minJump, i+maxJump] 中的任意一个 '0'？对可达数组使用滑动窗口和。维护可达位置的前缀和；如果区间 [j-maxJump, j-minJump] 中存在可达位置，则位置 j 可达。
def can_reach_vii(s, min_jump, max_jump):
n = len(s)
reach = [False] * n
reach[0] = True
pre = [0] * (n + 1) # prefix sum of reachable positions
pre[1] = 1
for j in range(1, n):
# Window sum: any reachable position in [j-maxJump, j-minJump]?
lo = max(0, j - max_jump)
hi = max(0, j - min_jump + 1)
window_sum = pre[hi] - pre[lo]
if s[j] == '0' and window_sum > 0:
reach[j] = True
pre[j+1] = pre[j] + (1 if reach[j] else 0)
return reach[n-1]
print(can_reach_vii('011010', 2, 3)) # True
print(can_reach_vii('01101110', 2, 3)) # False比较贪心解法和 BFS 解法
跳跃游戏 II 有两种等价的 O(n) 方法：贪心范围扩展和BFS 逐层遍历。贪心方法使用 O(1) 空间（不需要队列），而 BFS 需要 O(n) 空间来保存已访问集合。在面试中，通常更推荐贪心方法，因为它更节省空间。不过，BFS 更容易首先推导出来——如果您难以看出贪心解法，可以先编写 BFS，得到一个可运行的解法，然后再进行优化。两种方法都能正确计算最少跳跃次数。
# Both approaches are O(n) time
# Greedy: O(1) space — preferred in interviews
# BFS: O(n) space — easier to derive
# Greedy advantage: no auxiliary data structures
def jump_greedy(nums):
n, jumps, curr, far = len(nums), 0, 0, 0
for i in range(n-1):
far = max(far, i+nums[i])
if i == curr: jumps += 1; curr = far
return jumps
# BFS equivalence: each level = one jump
from collections import deque
def jump_bfs(nums):
n = len(nums)
if n == 1: return 0
q, visited, level = deque([0]), {0}, 0
while q:
level += 1
for _ in range(len(q)):
pos = q.popleft()
for j in range(1, nums[pos]+1):
nxt = pos + j
if nxt >= n-1: return level
if nxt not in visited: visited.add(nxt); q.append(nxt)
return -1
nums = [2,3,1,1,4]
print(jump_greedy(nums), '==', jump_bfs(nums)) # both 2跳跃游戏复杂度总结
跳跃游戏各变体的复杂度总结：跳跃 I（可达性）：时间复杂度 O(n)，空间复杂度 O(1)。跳跃 II（最少跳跃次数，贪心）：时间复杂度 O(n)，空间复杂度 O(1)。跳跃 II（BFS）：时间复杂度 O(n)，空间复杂度 O(n)。跳跃 II（DP）：时间复杂度 O(n × max_jump)，空间复杂度 O(n)。跳跃 III（BFS/DFS）：时间复杂度 O(n)，已访问集合占用空间 O(n)。跳跃 VII（滑动窗口）：时间复杂度 O(n)，空间复杂度 O(n)。面试时，针对跳跃 I 和 II，始终给出时间复杂度 O(n)、空间复杂度 O(1) 的贪心解法。
# Comparison: all versions on the same input
nums = [2, 3, 1, 1, 4]
# Jump I
def can_jump(nums):
mr = 0
for i, j in enumerate(nums):
if i > mr: return False
mr = max(mr, i+j)
return True
# Jump II greedy O(n) O(1)
def jump_min(nums):
n, jumps, curr, far = len(nums), 0, 0, 0
for i in range(n-1):
far = max(far, i+nums[i])
if i == curr:
jumps += 1; curr = far
if curr >= n-1: break
return jumps
print('Can reach:', can_jump(nums)) # True
print('Min jumps:', jump_min(nums)) # 2
print('Complexity: O(n) time, O(1) space')快速检查
测试您对本课中数据结构与算法 & 编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：跳跃游戏 I 使用贪心方法跟踪 max_reach，以 O(n) 时间复杂度和 O(1) 空间复杂度判断可达性、跳跃游戏 II 使用 curr_end 和 farthest 进行范围扩展，以 O(n) 时间复杂度和 O(1) 空间复杂度统计最少跳跃次数，以及贪心范围扩展等价于逐层 BFS，只是没有队列开销。接下来我们将把贪心推理应用于任务调度器的冷却时间问题和加油站的环路可行性问题。
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「跳跃游戏 I 与 II」课时是免费的吗？
是的 — 「跳跃游戏 I 与 II」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「跳跃游戏 I 与 II」这节课中我会学到什么？
使用贪心的范围扩展方法确定可达性和最少跳跃次数，从而避免使用 DP。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「跳跃游戏 I 与 II」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 贪心算法与 DP：何时使用哪一种
- 区间调度与合并
- 跳跃游戏 I 与 II
- 任务调度器与加油站