Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 45 - 跳跃游戏 II (Jump Game II)

Posted on Edited on In , ,
Symbols count in article: 3.7k Reading time ≈ 3 mins.
详解LeetCode第45题跳跃游戏II，通过贪心算法、动态规划和BFS三种方法分析如何高效求解最少跳跃次数问题，重点探讨贪心算法的实现技巧及优化思路

问题描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。

示例

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
1
2
输入: nums = [2,3,0,1,4]
输出: 2

约束条件

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

解题思路

这道题要求计算到达数组最后位置的最小跳跃次数。有多种方法可以解决这个问题，下面我们将介绍三种主要的解法：贪心算法、动态规划和 BFS。

方法一：贪心算法（最优解）

核心思想：在每一步中，我们都贪心地选择能跳得最远的位置，将跳跃过程划分为多个区间。

具体思路：

  1. 维护当前能够到达的最远位置 maxReach
  2. 维护当前跳跃区间的边界 end
  3. 当到达当前区间边界时，更新边界并增加跳跃步数

这个贪心策略之所以有效，是因为在每个区间内，我们总是选择能使下一步跳得最远的位置，这样可以最小化跳跃次数。

方法二：动态规划

核心思想：使用数组 dp[i] 表示到达位置 i 的最小跳跃次数。

具体思路：

  1. 创建一个长度为 n 的数组 dp，初始值设为 infinity（表示无法到达）
  2. 设置 dp[0] = 0（起始位置不需要跳跃）
  3. 对于每个位置 i，尝试更新 dp[i+1] 到 dp[i+nums[i]]

方法三：广度优先搜索（BFS）

核心思想：将数组视为一个图，每次可以从当前位置跳到可达的范围内的任意位置。

具体思路：

  1. 使用队列存储当前层级（相同跳跃次数）能到达的位置
  2. 每层代表一次跳跃，直到找到最后一个位置
  3. 层数即为最小跳跃次数

实现细节

贪心算法实现

贪心算法维护三个关键变量：

  • steps：记录跳跃次数
  • end：当前跳跃能到达的边界
  • maxReach：下一步能够到达的最远位置

算法的关键在于区间的划分：

  1. 我们将问题分解为若干个区间
  2. 在当前区间 [i, end] 内，计算能够到达的最远位置 maxReach
  3. 当遍历到当前区间的边界 end 时，我们知道必须进行一次跳跃
  4. 此时，将 end 更新为 maxReach，表示新的区间边界
  5. steps 自增，表示进行了一次跳跃

注意点：循环条件是 i < len(nums)-1 而不是 i < len(nums)，这是因为：

  1. 我们只需要能够到达最后一个位置，而不需要从最后一个位置再跳
  2. 当到达最后一个位置时，不需要再计算可以跳到的最远距离

关键代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func jump(nums []int) int {
	steps := 0  // 跳跃次数
	end := 0    // 当前区间的终点
	maxReach := 0  // 当前能到达的最远位置

	for i := 0; i < len(nums)-1; i++ {
		// 更新最远可达位置
		if i+nums[i] > maxReach {
			maxReach = i + nums[i]
		}

		// 到达当前区间的终点，必须跳跃一次
		if i == end {
			steps++   // 增加跳跃次数
			end = maxReach  // 更新区间终点为能到达的最远位置
		}
	}

	return steps
}

执行流程分析：以 [2,3,1,1,4] 为例

  1. 初始状态：steps=0, end=0, maxReach=0
  2. i=0: nums[0]=2，更新 maxReach=0+2=2，i==end，所以 steps=1，end=2
  3. i=1: nums[1]=3，更新 maxReach=1+3=4，i!=end，所以 steps 不变
  4. i=2: nums[2]=1，maxReach 已经是 4，不更新，i==end，所以 steps=2，end=4
  5. i=3: nums[3]=1，maxReach 已经是 4，不更新，i!=end，所以 steps 不变
  6. 循环结束，返回 steps=2

代码实现

方法一：贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func jump(nums []int) int {
	steps := 0
	end := 0
	maxReach := 0
	for i := 0; i < len(nums)-1; i++ {
		if i+nums[i] > maxReach {
			maxReach = i + nums[i]
		}
		if i == end {
			steps++
			end = maxReach
		}
	}
	return steps
}

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func jumpDP(nums []int) int {
	n := len(nums)
	dp := make([]int, n)

	// 初始化dp数组，设置为最大值
	for i := 1; i < n; i++ {
		dp[i] = n // 使用n作为"无穷大"
	}
	dp[0] = 0 // 起始位置不需要跳跃

	// 动态规划填表
	for i := 0; i < n; i++ {
		// 从位置i能跳到的所有位置
		for j := 1; j <= nums[i] && i+j < n; j++ {
			dp[i+j] = min(dp[i+j], dp[i]+1)
		}
	}

	return dp[n-1]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

方法三：广度优先搜索（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func jumpBFS(nums []int) int {
	n := len(nums)
	if n == 1 {
		return 0
	}

	// 已访问的位置
	visited := make([]bool, n)
	visited[0] = true

	// 队列记录当前层级的位置
	queue := []int{0}
	steps := 0

	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			curr := queue[0]
			queue = queue[1:] // 出队

			// 从当前位置能跳到的所有位置
			for j := 1; j <= nums[curr] && curr+j < n; j++ {
				next := curr + j

				// 如果到达终点，直接返回步数+1
				if next == n-1 {
					return steps + 1
				}

				// 如果该位置未访问过，加入队列
				if !visited[next] {
					visited[next] = true
					queue = append(queue, next)
				}
			}
		}
		steps++ // 增加层级
	}

	return -1 // 不会执行到这里，因为题目保证可以到达
}

方法比较

方面 贪心算法 动态规划 BFS
时间复杂度 O(n) O(n²) O(n)
空间复杂度 O(1) O(n) O(n)
优点 最高效，空间占用小 思路清晰，容易理解 适用于最短路径问题
缺点 实现技巧性较高 时间复杂度较高 需要额外空间
适用场景 需要最优性能 需要求解更复杂的变种 图的最短路径问题
推荐度 ★★★★★ ★★★☆☆ ★★★★☆

复杂度分析

贪心算法

  • 时间复杂度：O(n)，只需要遍历数组一次
  • 空间复杂度：O(1)，只使用了几个变量，没有额外的数据结构

动态规划

  • 时间复杂度：O(n²)，最坏情况下，对于每个位置 i，我们需要尝试 nums[i] 种跳跃方式
  • 空间复杂度：O(n)，需要一个长度为 n 的 dp 数组

BFS

  • 时间复杂度：O(n)，每个位置最多入队一次
  • 空间复杂度：O(n)，需要队列和访问标记数组

关键收获

  1. 贪心算法的巧妙应用：

    • 在这个问题中，贪心算法不是直接选择能跳得最远的位置，而是在能跳到的范围内选择能使下一步跳得最远的位置
    • 使用区间划分的思想来优化解法

  2. 边界处理的重要性：

    • 循环条件 i < len(nums)-1 而不是 i < len(nums)，避免了不必要的计算
    • 这个细节很容易被忽略，但对正确性至关重要

  3. 算法选择的权衡：

    • 贪心算法在这个问题上效率最高，但实现较为技巧性
    • 动态规划思路清晰但效率较低
    • BFS 适用于求解最短路径问题，但需要额外空间

  4. 变量命名的含义：

    • end 表示当前跳跃区间的边界，是一个关键的概念
    • maxReach 记录当前能到达的最远位置
    • 清晰的变量命名使算法更易理解

相关题目

  • LeetCode 55: 跳跃游戏（判断是否能到达最后一个位置）
  • LeetCode 1306: 跳跃游戏 III（能否到达值为 0 的元素）
  • LeetCode 1340: 跳跃游戏 V（从更高的柱子向两边跳跃）