好的,我们来详细地解答“跳跃游戏 II”这道经典的算法题。
题目描述
给定一个非负整数数组 `nums`,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大距离。你的目标是使你能够到达最后一个位置。你的目标是使你能够到达最后一个位置,并使跳跃次数最少。你可以假设你总是可以到达最后一个位置。
示例
输入: `nums = [2,3,1,1,4]`
输出: `2`
解释: 从第一个位置(索引 0)跳 1 步到第二个位置(索引 1),然后从第二个位置跳 3 步到最后一个位置(索引 4)。
题目分析与解题思路
这道题的目的是在最少次数内到达数组的最后一个位置。这隐含着我们不仅要考虑如何跳到更远的位置,还要在每一步跳跃中做出最优的选择,以期用更少的步数覆盖整个数组。
1. 贪心算法 (Greedy Approach)
最直观且高效的解法是采用贪心算法。贪心算法的核心思想是:在每一步决策时,都选择当前情况下最优的选项,希望通过局部最优推导出全局最优。
对于“跳跃游戏 II”,我们的目标是在每一步跳跃中,尽量跳得更远,从而最快地接近甚至到达终点。
具体来说,我们可以维护一个当前可达范围的边界。当我们在这个范围内进行跳跃时,我们需要确定下一步的最佳跳跃位置,这个位置应该能够让我们在下一次跳跃时 reach 到最远的位置。
算法步骤 (贪心法):
1. 初始化:
`jumps = 0`: 用于记录跳跃的次数。
`current_reach = 0`: 表示当前跳跃可以达到的最远位置。
`max_reach = 0`: 表示从当前位置开始,下一步可以达到的最远位置。
2. 遍历数组: 从数组的第一个位置 (索引 0) 开始遍历,直到倒数第二个位置 (因为到达最后一个位置后就不需要再跳了)。
3. 更新 `max_reach`: 在遍历过程中,对于当前位置 `i`,我们计算从 `i` 可以达到的最远位置:`i + nums[i]`。我们将 `max_reach` 更新为当前 `max_reach` 和 `i + nums[i]` 中的较大值。
`max_reach = max(max_reach, i + nums[i])`
这意味着在当前这一步跳跃,我可以在 `[0, current_reach]` 这个范围内选择任何一个位置 `i` 进行跳跃,并且从 `i` 出发,能够达到的最远位置是 `i + nums[i]`。我们要在所有可能的 `i` 中找到那个能让我们跳得最远的点,并将其记录在 `max_reach` 中。
4. 触发下一次跳跃: 当我们到达了当前跳跃所能达到的最远位置(即 `i == current_reach`)时,我们就必须进行一次跳跃。
增加跳跃次数: `jumps += 1`
更新当前可达范围的边界: `current_reach = max_reach`
检查是否到达终点: 如果 `current_reach` 已经大于或等于数组的最后一个索引 (`n 1`),那么我们已经到达了终点,可以直接返回 `jumps`。
5. 返回结果: 循环结束后,返回 `jumps`。
为什么这样做是正确的 (贪心证明的直观理解):
我们每次在 `current_reach` 边界进行跳跃时,都选择了能够将 `max_reach` 推到最远的位置。假设我们当前能跳到的最远位置是 `current_reach`。在这个 `[0, current_reach]` 的范围内,我们遍历每一个 `i`,计算出 `i + nums[i]` 的最大值,并将其存储在 `max_reach` 中。 当我们遍历完 `current_reach` 的所有位置时,`max_reach` 就代表了我们从当前跳跃所能达到的最远位置。
我们必须在 `current_reach` 处进行一次跳跃,将我们的活动范围推进到 `max_reach`。因为我们选择的是能够跳到最远的点,这保证了我们能以最快的速度接近终点。如果我们不选择那个能跳到最远的点,而是选择一个次优的点,那么下一次跳跃能到达的范围就会更小,最终可能需要更多的跳跃次数才能到达终点。
示例 walkthrough:
假设 `nums = [2,3,1,1,4]`, `n = 5`
初始化: `jumps = 0`, `current_reach = 0`, `max_reach = 0`
i = 0:
`nums[0] = 2`
`max_reach = max(0, 0 + 2) = 2`
`i == current_reach` (0 == 0) 是 true。
触发一次跳跃:
`jumps = 1`
`current_reach = max_reach = 2`
`current_reach` (2) < `n 1` (4)。
i = 1:
`nums[1] = 3`
`max_reach = max(2, 1 + 3) = 4`
`i == current_reach` (1 == 2) 是 false。
i = 2:
`nums[2] = 1`
`max_reach = max(4, 2 + 1) = 4`
`i == current_reach` (2 == 2) 是 true。
触发一次跳跃:
`jumps = 2`
`current_reach = max_reach = 4`
`current_reach` (4) >= `n 1` (4) 是 true。
到达终点,返回 `jumps = 2`。
代码实现 (Python)
```python
def jump(nums: list[int]) > int:
"""
跳跃游戏 II 的贪心算法实现。
Args:
nums: 一个非负整数数组,表示每个位置的最大跳跃距离。
Returns:
到达最后一个位置所需的最少跳跃次数。
"""
n = len(nums)
if n <= 1:
return 0 如果数组只有一个元素或为空,则无需跳跃
jumps = 0 已进行的跳跃次数
current_reach = 0 当前跳跃能到达的最远位置
max_reach = 0 下一步跳跃能到达的最远位置
遍历数组,直到倒数第二个位置。因为最后一个位置到达后就不需要再跳了。
for i in range(n 1):
更新下一步可以达到的最远位置
max_reach = max(max_reach, i + nums[i])
如果当前位置 i 已经达到了上一次跳跃的边界 current_reach
这意味着我们必须进行一次跳跃来推进到 max_reach
if i == current_reach:
jumps += 1 增加跳跃次数
current_reach = max_reach 更新当前跳跃的最新边界
如果新的 current_reach 已经能够到达或超过终点
if current_reach >= n 1:
return jumps 提前返回,因为我们已经到达终点
return jumps 正常情况下,循环会完成,并返回最终的跳跃次数
```
时间复杂度和空间复杂度
时间复杂度:O(n)
我们只需要遍历一次数组。在循环内部,所有的操作都是常数时间。因此,时间复杂度是线性的。
空间复杂度:O(1)
我们只使用了几个额外的变量 (`jumps`, `current_reach`, `max_reach`) 来存储状态,它们不随输入数组的大小而改变。因此,空间复杂度是常数级的。
2. 广度优先搜索 (BFS) 的思路
虽然贪心算法是最佳解法,但理解 BFS 的思路也有助于掌握这类“最短路径”问题。
可以将这个问题看作一个图搜索问题:
节点: 数组的索引。
边: 从索引 `i` 可以跳跃到 `i + 1`, `i + 2`, ..., `i + nums[i]` 这些索引。
我们希望找到从起始节点 (索引 0) 到目标节点 (索引 `n1`) 的最短路径。BFS 天然适合解决最短路径问题(在无权图或单位权图上)。
BFS 实现思路:
1. 队列: 使用一个队列来存储待访问的节点,以及到达该节点所需的跳跃次数。可以将每个元素存储为 `(当前位置, 跳跃次数)`。
2. visited 集合: 使用一个集合来记录已经访问过的位置,防止重复访问和死循环。
3. 起始: 将 `(0, 0)` 加入队列,并将 `0` 加入 visited 集合。
4. BFS 循环:
当队列不为空时,从队列头部取出一个元素 `(current_pos, current_jumps)`。
如果 `current_pos` 是终点 `n 1`,则返回 `current_jumps`。
计算从 `current_pos` 可以跳到的所有下一个位置 `next_pos` (即 `current_pos + 1` 到 `current_pos + nums[current_pos]`)。
对于每一个 `next_pos`:
如果 `next_pos` 没有被访问过:
将其加入 visited 集合。
将其加入队列,作为 `(next_pos, current_jumps + 1)`。
BFS 的缺点:
时间复杂度可能更高: 在最坏情况下,BFS 可能需要访问所有可能的路径。如果每次跳跃都能跳很远,那么层的数量会很少,BFS 也可能很快。但如果数组中的值都比较小,BFS 可能需要生成很多中间节点。
空间复杂度更高: 需要额外的队列和 visited 集合,空间复杂度可能达到 O(n)。
为什么贪心优于 BFS (在这种特定问题下):
题目中明确要求的是最少跳跃次数。贪心算法通过在每一步最大化“跳跃距离”,直接朝着目标前进,并且是全局最优的。BFS 实际上是在“层层递进”地探索,找到最短路径,而贪心算法直接“跳”到了离终点最近的点,效率更高。
总结
“跳跃游戏 II”是一道典型的可以使用贪心算法解决的最短路径问题。通过维护当前可达的最远边界和下一步能达到的最远边界,我们可以用 O(n) 的时间和 O(1) 的空间高效地找到最少跳跃次数。理解贪心算法背后的逻辑,即在每一步都做出能最快接近目标的决策,是解决这类问题的关键。