45.跳跃游戏II

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

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

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

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

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

思路

本题相对于55.跳跃游戏还是难了不少。

但思路是相似的,还是要看最大覆盖范围。

本题要计算最小步数,那么就要想清楚什么时候步数才一定要加一呢?

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

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

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

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

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

如图:

45.跳跃游戏II

图中覆盖范围的意义在于,只要红色的区域,最多两步一定可以到!(不用管具体怎么跳,反正一定可以跳到)

方法一

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

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

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

 

方法二

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

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

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

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

  • 如果移动下标等于当前覆盖最大距离下标, 需要再走一步(即ans++),因为最后一步一定是可以到的终点。(题目假设总是可以到达数组的最后一个位置),如图:

  •  45.跳跃游戏II

  • 如果移动下标不等于当前覆盖最大距离下标,说明当前覆盖最远距离就可以直接达到终点了,不需要再走一步。如图:

45.跳跃游戏II

 

可以看出版本二的代码相对于版本一简化了不少!

其精髓在于控制移动下标i只移动到nums.size() - 2的位置,所以移动下标只要遇到当前覆盖最远距离的下标,直接步数加一,不用考虑别的了。

总结

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

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

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

 

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int step=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){
                step++;
                break;
            }
            //走到当前覆盖的最大区域时,更新下一步可达的最大区域
            if (i==curDistance){
                curDistance = maxDistance;
                step++;
            }
        }
        return step;
    }
}

  

/**
假设我最多跳4次,最多拿跳多远,是看第三次能跳在哪个位置决定的
比如,第三次能跳的位置是:
x y z a b
i j k m n
那第四次跳的位置是:Math.max(i+x,j+y,k+z,m+a,n+b)
那第三次是由第二次决定的,
第二次是由第一次决定的,
第一次是由第0次决定的。

eg:
3 5 1 1 4 1 1 1 2 2
0 1 2 3 4 5 6 7 8 9
i

i=0
step=0 来到0这个位置是不用移动步数的
cur=0 0步的最远距离还是0
next=-1 
next=3 0步再跳一步能到达的最远距离是3

i=1
step=1 
cur=3
next=6

i=2
step=1
cur=3
next=6

i=3
step=1
cur=3
next=6

i=4
step=2
cur=6
next=8

i=5
step=2
cur=6
next=8

i=6
step=2
cur=6
next=8

i=7
step=3
cur=8
next=8

i=8
step=3
cur=8
next=10

i=9
step=4
cur=10
next=12



*/


class Solution {
    public int jump(int[] nums) {
        int step=0;//表示现在跳几步
        int cur=0;//表示在跳step情况下的最远距离
        int next=-1;//表示如果此时多跳一步,最远能到哪
        for(int i=0;i<nums.length;i++){
            if(i>cur){
                step++;
                cur=next;
            }
            next=Math.max(next,i+nums[i]);
        }
        return step;
    }
}

  

 

上一篇:MySQL实战45讲 (学习笔记三)


下一篇:【第3版emWin教程】第45章 emWin6.x窗口管理器之定时器使用