45.跳跃游戏 II

╰+攻爆jí腚メ 2023-10-16 15:03 23阅读 0赞

#### 45.跳跃游戏 II ####

*  题干分析
 *  解题思路
 *   *  方法一
     *  方法二
 *  总结
 *  代码实现
 *   *  版本一
     *  版本二

## 题干分析 ##

[力扣入口][Link 1]  
给定一个非负整数数组，你最初位于数组的第一个位置。

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

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

说明: 假设你总是可以到达数组的最后一个位置。

## 解题思路 ##

本题相对于**55.跳跃游戏**还是难了不少。但思路是相似的，还是要看最大覆盖范围。

本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

思路虽然是这样，但在写代码的时候还不能真的能跳多远就跳多远，那样就不知道下一步最远能跳到哪里了。

**所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！**

**这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。**

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

如图：  
![在这里插入图片描述][52c86cb36db142349b44c1cb3cb67ec8.png]  
**图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）**

### 方法一 ###

从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。

这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

*  如果当前覆盖最远距离下标不是集合终点，步数就加一，还需要继续走。
 *  如果当前覆盖最远距离下标就是集合终点，步数不用加一，因为不能再往后走了。

### 方法二 ###

依然是贪心，思路和方法一差不多，代码可以简洁一些。

**针对于方法一的特殊情况，可以统一处理**，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。

想要达到这样的效果，只要让移动下标，最大只能移动到 nums.size - 2 的地方就可以了。

因为当移动下标指向 nums.size - 2 时：

*  如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：  
    ![在这里插入图片描述][07534c16767d472d88906f41351b0abc.png]
 *  如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：  
    ![在这里插入图片描述][de5264c3d7d847bc80e4bec8a6160fdf.png]  
    其精髓在于控制移动下标 i 只移动到 nums.size() - 2 的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不用考虑别的了。

## 总结 ##

相信大家可以发现，这道题目相当于**55.跳跃游戏** 难了不止一点。

但代码又十分简单，贪心就是这么巧妙。

理解本题的关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最少步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。

## 代码实现 ##

### 版本一 ###

class Solution {
        
        // 45.跳跃游戏 II - 版本一
        public int jump(int[] nums){
        
            if(nums == null || nums.length == 0 || nums.length == 1){
        
                return 0;
            }
            // 记录跳跃的次数
            int count = 0;
            // 当前的覆盖最大区域
            int curDistance = 0;
            // 最大的覆盖区域
            int maxDistance = 0;
            for(int i = 0; i < nums.length; i++){
        
                // 在可覆盖区域内更新最大的覆盖区域
                maxDistance = Math.max(maxDistance, i+nums[i]);
                // 说明当前一步，再跳一步就到达了末尾
                if(maxDistance >= nums.length-1){
        
                    count++;
                    break;
                }
                // 走到当前覆盖的最大区域时，更新下一步可达的最大区域
                if(i==curDistance){
        
                    curDistance = maxDistance;
                    count++;
                }
            }
            return count;
        }
    }

### 版本二 ###

class Solution {
        
        // 45.跳跃游戏 II - 版本二
        public int jump(int[] nums) {
        
            int result = 0;
            // 当前覆盖的最远距离下标
            int end = 0;
            // 下一步覆盖的最远距离下标
            int temp = 0;
            for(int i = 0; i <= end && end <nums.length - 1; ++i){
        
                temp = Math.max(temp, i + nums[i]);
                // 可达位置的改变次数就是跳跃次数
                if (i == end) {
        
                    end = temp;
                    result++;
                }
            }
            return result;
        }
    }

**参考资料**：[代码随想录-45.跳跃游戏 II][-45._ II]

[Link 1]: https://leetcode.cn/problems/jump-game-ii/
[52c86cb36db142349b44c1cb3cb67ec8.png]: https://img-blog.csdnimg.cn/52c86cb36db142349b44c1cb3cb67ec8.png
[07534c16767d472d88906f41351b0abc.png]: https://img-blog.csdnimg.cn/07534c16767d472d88906f41351b0abc.png
[de5264c3d7d847bc80e4bec8a6160fdf.png]: https://img-blog.csdnimg.cn/de5264c3d7d847bc80e4bec8a6160fdf.png
[-45._ II]: https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE