页面启动中 . . .

Leetcode 55：跳跃游戏

贪心算法

Leetcode

发布日期: 2023-07-08

更新日期: 2023-09-24

文章字数: 602

阅读时长: 2 分

阅读次数:

Leetcode 55：跳跃游戏（贪心）

1. 题目说明

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标

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

2. 解答分析

分析：
- 本题的关键是对于每一步的把控，例如当处于nums[0]时，此时的值为2，也就是可以跳跃一步或者两步，这样下去对应数组中的每个数字都可以由不同的跳跃方法。
- 但是我们要注意：每个位置跳多少步不是关键，而是最后的跳跃范围是否可以覆盖到最后一个数（也就是终点） 那么我们可以尝试每次移动取最大的跳跃步数（目的是得到最大的范围），依次更新覆盖的范围。
- 本题的贪心算法的关键是：局部最优解，每次取最大的跳跃步数（取最大的覆盖范围）；整体最优解：最后得到整体的最大覆盖范围，看看能否到达最后一个数（终点）

代码：

class Solution{
    public boolean canJump(int[] nums){
        if(nums.length==1){
            return true;//特例：第一个数字自己就是终点
        }
        //开始覆盖范围
        int cover=nums[0];//初始值
        //在第一个数的覆盖范围内继续不断地更新最大覆盖范围
        for(int i=0;i<=cover;i++){
        //这里之所以可以取等，因为我们要求的相当于是每个位置的数值，那当然可以取等，如nums[0]==3,那么我们可以跳跃三次到nums[3],再更新最大范围;
    	cover=Math.max(cover,i+nums[i]);//当前的编号，加上可跳跃的数值，即为范围
        if(cover>=nums.length-1){//覆盖范围可以到达最后一个数字的下标（终点）
            return true;
        	}  
        }
        return false;
    }
}