Leetcode 55. 跳跃游戏

力扣传送门(opens new window)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

• 输入: [2,3,1,1,4]
• 输出: true
• 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

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

解题思路：

这道题目是一个典型的跳跃游戏问题，我们可以使用贪心算法来解决。

刚开始可能会想到：我是跳一步还是两步呢?我从位置1跳还是从位置2开始跳呢？

其实这些都不需要考虑，我们每一步都只需要选择最大的跳跃方式就行，直到到达或者超过最后一个位置，我们就胜利了！

我们从数组的第一个位置开始，不断计算当前位置能够跳跃到的最远位置（最远能够到达的位置），并更新最远位置。如果最远位置大于等于数组的最后一个位置，说明我们可以到达最后一个位置，返回 true；否则，我们无法到达最后一个位置，返回 false。

算法的思路如下：

1. 初始化最远位置 maxReach 为 0，表示当前能够到达的最远位置。
2. 从数组的第一个位置开始遍历：
   • 如果当前位置大于最远位置 maxReach，说明无法到达当前位置，直接返回 false。
   • 计算当前位置能够跳跃到的最远位置 i + nums[i]，其中 i 是当前位置。
   • 如果最远位置大于等于数组的最后一个位置，返回 true。
   • 更新最远位置 maxReach 为当前位置能够跳跃到的最远位置和当前最远位置 maxReach 中的较大值。
3. 遍历完数组后，如果最远位置大于等于数组的最后一个位置，返回 true；否则，返回 false。

下面是使用示例 [2, 3, 1, 1, 4] 来具体演示算法的执行过程：

1. 初始化最远位置 maxReach 为 0。
2. 当前位置为 0，最远位置为 2，更新 maxReach 为 2。
3. 当前位置为 1，最远位置为 2，可以到达当前位置，计算当前位置能够跳跃到的最远位置为 1 + 3 = 4，更新 maxReach 为 4。此时已经可以到达最后一个位置了！！！

贪心算法的关键在于每次只考虑当前能够跳跃到的最远位置，通过不断更新最远位置，判断是否能够到达最后一个位置。由于题目中给出的是非负整数数组，因此我们可以确保每一步都是向前跳跃的，不会出现往回跳的情况，从而可以应用贪心算法解决该问题。

代码实现：

class Solution {
    public boolean canJump(int[] nums) {
        if(nums == null){
            return false;
        }
        if(nums.length == 1){
            return true;
        }
        int len = nums.length - 1;
        int maxReach = 0;
        // 注意这里是小于等于maxReach
        for(int i = 0;  i <= maxReach; i++){
            if(maxReach >= nums.length-1){
                return true;
            }
            maxReach = Math.max(maxReach,i+nums[i]);
  
        }
        return false;
    }
}