（贪心算法）Java 求解跳跃游戏 II

Love The Way You Lie 2023-01-21 09:23 15阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、贪心分析
     *  三、代码
     *  四、总结

## 一、题目 ##

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

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

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

![在这里插入图片描述][20210410202735177.png]

> 假设你总是可以到达数组的最后一个位置

## 二、贪心分析 ##

思路类似：[跳跃游戏][Link 1]

在每次可以跳跃的范围内，选一个覆盖区域最大的下标继续开始，也就是选一个覆盖区域最大的下标当做下一步

> 比如：2,3,1,1,4  
> 第一步是2，覆盖范围是3,1，3的覆盖范围最大，所以下一步从3开始

## 三、代码 ##

class Solution { 
        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;
        }
    }

## 四、总结 ##

该题和上一题类似，都是每次选取覆盖的最大区域，只是上一题需要考虑覆盖不到的情况，本题已经说明了已经可以覆盖到，让求最少的步数

[20210410202735177.png]: /images/20221020/d1058b329a374181b4b4b0e8423ee382.png
[Link 1]: https://blog.csdn.net/nanhuaibeian/article/details/115547332