贪心---跳跃游戏(II) Posted on 2021-08-10 00:00:00 2021-08-10 00:00:00 by Author 摘要 给你一个数组,其中每个元素表示你能够从该位置到达下个位置的步数,那么从开始位置起,你能用更少的步数到达终点吗(可以保证无论如何都可以到达终点的)???? # 贪心---跳跃游戏(II) 1. 题目描述 - 给你一个非负整数数组 nums ,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。 - **提示:** - `1 <= nums.length <= 104` - `0 <= nums[i] <= 1000` 2. 示例描述 - 示例一 ```java 输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 ``` - 示例二 ```java 输入: nums = [2,3,0,1,4] 输出: 2 解释:第一步跳到下标为一的位置,然后第二步跳到最后一个位置 ``` 3. 解题思路 - 本题又是跳跃游戏(I)道题的变种类型,[跳跃游戏(I)](http://www.geticsen.cn/view/articles/detail/06721434-0552-47be-b3ab-b1b246a00f57)这道题已经掌握了怎么能够判断是否可以到达终点,但是本题已经可以保证总是可以到达最后的一个位置,那么我们就可以不用纠结如果跳到中间一办的时候,跳不动的情况了。本题最主要的是判断跳的步数最少的问题。 - 那么在保证跳的步数最少,那么就使得每一步跳的更远,那么就使总体的步数最少。那么我们怎么保证每一步跳的更远尼,上一道体中已经知道当前位置的距离肯定小于或者等于之前跳的最远距离。所以如果当前位置还在上一次跳的最远距离内,那么可以持续更新上次跳的最远之内中所能达到更远的距离,以便下次就能直接跳到更远的位置。如果当前位置和上次跳的最远距离位置相等的时候,还没有到达终点的话,那说明上一次要跳的步数还不能到达终点,还得往前走(题目说了总会到达终点的),直到上一步距离中最远距离大于或者等于终点的位置时候,就不用在跳了。 - 具体逻辑见如下代码。 4. 代码示例 ```java public int jump(int[] nums) { //上次最远的距离为lastMaxDistance开始值为0 //上次最远距离与当前位置元素中还能到达的更远距离即为:nextMaxDistance //result 最终要走的步数 int lastMaxDistance = 0, nextMaxDistance = 0,result=0; for (int i = 0; i < nums.length; i++) { //下次最远距离就是当前位置元素与上次最远距离最大值 //因为当前元素位置肯定小于或者等于上次最远的距离 nextMaxDistance = Math.max(nums[i] + i, nextMaxDistance); //如果上次最远距离与当前元素距离相等的时候 //说明上次最远距离就只能到达此位置 //其之间的元素不能到达更远的位置了 if (lastMaxDistance == i) { //如果本位置还没到达终点的时候 if (lastMaxDistance < nums.length - 1) { //需要往前走一步 result++; //同时上一步走的最远距离换成它接下来将要走的最远距离了 //以保证可以到达终点 lastMaxDistance = nextMaxDistance; } else { //如果当前位置元素与终点相等,那么说明上一步已经能够可以到达终点,就不用在跳了,直接返回最小的步数即可 break; } } } return result; } ```
{{ item.content }}
{{ child.content }}