当前位置：首页 > java >正文

LeetCode 55. 跳跃游戏（中等）

java 2025/5/15 9:43:21

题目描述

给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true；否则，返回 false。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 10^4

0 <= nums[i] <= 10^5

问题分析

这是一个经典的贪心算法问题。问题的关键在于判断是否能从起点跳到终点，而不是求解具体的跳跃路径。

当我们站在某个位置时，可以选择跳1步、2步...直到该位置的最大跳跃长度。但实际上，我们不需要考虑具体跳几步，而是关注能否覆盖到终点。

解题思路

贪心算法

贪心算法的核心思想是：每一步都计算能跳到的最远距离，只要能覆盖到最后一个位置，就说明可以到达。

具体步骤如下：

维护一个变量 maxReach，表示当前能到达的最远位置
遍历数组中的每个元素，如果当前位置已经超过了能到达的最远位置，说明无法到达该位置，返回 false
否则，更新 maxReach 为当前位置能到达的最远位置和已记录的最远位置中的较大值
如果 maxReach 已经覆盖了最后一个位置，可以直接返回 true

动态规划方法

虽然贪心算法是解决此问题的最优解，但我们也可以使用动态规划来理解这个问题：

创建一个布尔数组 dp，其中 dp[i] 表示是否能到达位置 i
初始条件：dp[0] = true（起点总是可以到达的）
对于每个可达位置 i，标记从该位置可以跳到的所有位置 j 为可达（dp[j] = true）
最终检查 dp[n-1] 是否为 true

算法过程

以示例1为例：nums = [2,3,1,1,4]

使用贪心算法的执行过程：

初始位置：i = 0，maxReach = 0
遍历位置0：nums[0] = 2，更新 maxReach = max(0, 0+2) = 2
遍历位置1：nums[1] = 3，更新 maxReach = max(2, 1+3) = 4（已覆盖终点，可返回true）
实际上已经可以确定能到达终点了，但我们继续遍历以展示完整过程
遍历位置2：nums[2] = 1，更新 maxReach = max(4, 2+1) = 4
遍历位置3：nums[3] = 1，更新 maxReach = max(4, 3+1) = 4
遍历位置4：nums[4] = 4，更新 maxReach = max(4, 4+4) = 8

最终 maxReach = 8 大于等于 nums.length - 1 = 4，返回 true。

详细代码实现

Java 实现 - 贪心算法

class Solution {public boolean canJump(int[] nums) {// 当前能到达的最远位置int maxReach = 0;// 遍历数组for (int i = 0; i < nums.length; i++) {// 如果当前位置已经超过了能到达的最远位置，说明无法到达该位置if (i > maxReach) {return false;}// 更新最远可以到达的位置maxReach = Math.max(maxReach, i + nums[i]);// 如果最远位置已经覆盖了最后一个位置，可以直接返回trueif (maxReach >= nums.length - 1) {return true;}}// 如果能够遍历完整个数组，说明最后一个位置是可达的return true;}
}

C# 实现 - 贪心算法

public class Solution {public bool CanJump(int[] nums) {// 当前能到达的最远位置int maxReach = 0;// 遍历数组for (int i = 0; i < nums.Length; i++) {// 如果当前位置已经超过了能到达的最远位置，说明无法到达该位置if (i > maxReach) {return false;}// 更新最远可以到达的位置maxReach = Math.Max(maxReach, i + nums[i]);// 如果最远位置已经覆盖了最后一个位置，可以直接返回trueif (maxReach >= nums.Length - 1) {return true;}}// 如果能够遍历完整个数组，说明最后一个位置是可达的return true;}
}

Java 实现 - 动态规划

class Solution {public boolean canJump(int[] nums) {int n = nums.length;// dp[i]表示是否能到达位置iboolean[] dp = new boolean[n];// 起点总是可达的dp[0] = true;for (int i = 0; i < n; i++) {// 如果当前位置不可达，跳过if (!dp[i]) {continue;}// 从当前位置可以跳到的所有位置for (int j = 1; j <= nums[i] && i + j < n; j++) {dp[i + j] = true;}// 如果最后一个位置已经标记为可达，可以提前返回if (dp[n - 1]) {return true;}}return dp[n - 1];}
}

C# 实现 - 动态规划

public class Solution {public bool CanJump(int[] nums) {int n = nums.Length;// dp[i]表示是否能到达位置ibool[] dp = new bool[n];// 起点总是可达的dp[0] = true;for (int i = 0; i < n; i++) {// 如果当前位置不可达，跳过if (!dp[i]) {continue;}// 从当前位置可以跳到的所有位置for (int j = 1; j <= nums[i] && i + j < n; j++) {dp[i + j] = true;}// 如果最后一个位置已经标记为可达，可以提前返回if (dp[n - 1]) {return true;}}return dp[n - 1];}
}