力扣经典150题第十题：跳跃游戏二

本文主要是介绍力扣经典150题第十题：跳跃游戏二，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 简介

本篇博客将讨论力扣经典150题中的跳跃游戏 II 问题。给定一个长度为 n 的整数数组 nums，数组中的每个元素表示从当前位置最多可以跳跃的步数，求到达数组末尾的最小跳跃次数。

2. 问题描述

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

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

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

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

输入: nums = [2,3,0,1,4]
输出: 2

提示:

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

3. 解题思路

方法一：贪心算法

使用贪心算法解决，维护一个变量 maxReach 表示当前能够达到的最远位置，同时维护两个边界 currentEnd 和 farthest。遍历数组，对于每个位置 i，更新 farthest 为 i + nums[i]，当遍历到 currentEnd 时更新跳跃次数并更新 currentEnd 为 farthest。

4. 算法实现

方法一：贪心算法

public int jump(int[] nums) {int jumps = 0;int farthest = 0;int currentEnd = 0;for (int i = 0; i < nums.length - 1; i++) {farthest = Math.max(farthest, i + nums[i]);if (i == currentEnd) {jumps++;currentEnd = farthest;}}return jumps;
}

1. 解决方案二：动态规划

思路

使用动态规划来解决该问题。定义一个数组 dp，其中 dp[i] 表示到达位置 i 的最小跳跃次数。初始时，将 dp[0] 设置为 0，对于其他位置 i，初始化为一个较大的数（比如数组长度 n）。然后遍历数组 nums，对于每个位置 i，更新能够到达的位置的最小跳跃次数。

实现

public int jump(int[] nums) {int n = nums.length;int[] dp = new int[n];Arrays.fill(dp, n); // 初始化为较大的数dp[0] = 0;for (int i = 0; i < n; i++) {for (int j = 1; j <= nums[i] && i + j < n; j++) {dp[i + j] = Math.min(dp[i + j], dp[i] + 1);}}return dp[n - 1];
}

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。两层循环嵌套，每个位置都需要遍历一定范围内的位置。
• 空间复杂度：O(n)，需要额外的数组 dp 存储跳跃次数。

2. 解决方案三：反向贪心算法

思路

使用反向贪心算法来解决该问题。从数组的最后一个位置向前遍历，维护一个变量 position 表示当前需要到达的位置。对于每个位置 i，如果 i + nums[i] >= position，则更新 position 为 i，并增加跳跃次数。

实现

public int jump(int[] nums) {int jumps = 0;int position = nums.length - 1;while (position > 0) {for (int i = 0; i < position; i++) {if (i + nums[i] >= position) {position = i;jumps++;break;}}}return jumps;
}

复杂度分析

• 时间复杂度：O(n^2)，最坏情况下需要遍历整个数组。
• 空间复杂度：O(1)，只需要常数级别的额外空间。

测试示例

使用相同的测试示例进行验证：

int[] nums1 = {2, 3, 1, 1, 4};
int[] nums2 = {2, 3, 0, 1, 4};System.out.println("Test Case 1:");
System.out.println("Expected Result: 2");
System.out.println("Actual Result (Solution 2): " + jump(nums1));
System.out.println("Actual Result (Solution 3): " + jump(nums1));System.out.println("Test Case 2:");
System.out.println("Expected Result: 2");
System.out.println("Actual Result (Solution 2): " + jump(nums2));
System.out.println("Actual Result (Solution 3): " + jump(nums2));

输出结果为：

Test Case 1:
Expected Result: 2
Actual Result (Solution 2): 2
Actual Result (Solution 3): 2Test Case 2:
Expected Result: 2
Actual Result (Solution 2): 2
Actual Result (Solution 3): 2

以上就是针对力扣经典150题中跳跃游戏 II 的三种解决方案。读者可以根据需求和实际场景选择合适的方法进行应用和实现。

5. 示例与测试

我们使用示例输入进行测试，并验证算法的正确性：

int[] nums1 = {2, 3, 1, 1, 4};
int[] nums2 = {2, 3, 0, 1, 4};System.out.println("Test Case 1:");
System.out.println("Expected Result: 2");
System.out.println("Actual Result: " + jump(nums1));System.out.println("Test Case 2:");
System.out.println("Expected Result: 2");
System.out.println("Actual Result: " + jump(nums2));

输出结果为：

Test Case 1:
Expected Result: 2
Actual Result: 2Test Case 2:
Expected Result: 2
Actual Result: 2

6. 总结与展望

通过本篇博客，我们详细讨论了力扣经典150题中的跳跃游戏 II 问题，并提供了贪心算法的实现方法。这种方法具有高效性和简洁性，在实际应用中具有广泛的适用性。

7. 结语

希望本文能够帮助读者更好地理解和掌握跳跃游戏 II 的解题思路和实现方法，欢迎提出您的宝贵意见和建议。

这篇关于力扣经典150题第十题：跳跃游戏二的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---