leetcode45. Jump Game II

shiguibiao 发布于2019-08-15 10:50 / 2592人阅读

摘要：转换为广度优先算法即为我们只需要找到每一步的开始节点和结束下标，找到下一轮遍历的最大下标，如果该下标超过了数组长度，那么结束遍历，返回步数，否则将上一轮的最终节点加一作为起始节点，并将下一轮最大下标最为结束节点，继续遍历。

题目要求

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

对于类似体型Jump Game I，请参考这篇博客。
这题相对于I，差别在于已知一定可以到达终点，找到一条最短路径所需要的步数。

思路一：递归超时

通过递归的方式找到一条到达终点的路径。通过和当前最短路径比较来省去一些不必要的遍历。但是存在缺点。其实同一个节点到达最终节点的最短步数是一定的，而每一次递归都造成无法省略的重复遍历。

    public int jump(int[] nums) {
        jump(nums, 0, 0);
        return minimumSteps;
    }
    
    public void jump(int[] nums, int currentStep, int currentIndex){
        if(currentIndex + nums[currentIndex] >= nums.length){
            minimumSteps = Math.min(minimumSteps, currentStep+1);
            return;
        }
        if(minimumSteps!=0 && currentStep >= minimumSteps){
            return;
        }
        for(int i = 1; i<=nums[currentIndex] ; i++){
            jump(nums, currentStep+1, currentIndex+i);
        }
    }

思路二：反向动态编程超时

如果我们从终点往起点寻找，先找可以直接到达终点的最小下标，然后将该下标作为终点，继续查找到达该终点的最小下标，并将step加一。这种代码在大多数情况下，效率正常，但是如果出现极端情况，比如数据量很大，且到达当前终点的最小下标即为当前终点的前一个节点。就会造成非常严重的无用遍历。在最好的情况下的时间复杂度为O(n),但是最差的时间复杂度为O(n^2）

    public int jump2(int[] nums){
        int minimumSteps = 0;
        int last = nums.length - 1;
        while(last != 0){
            int nextLast = last;
            for(int i =last-1 ; i>=0 ; i--){
                if(nums[i] + i >= last){
                    nextLast = i;
                }
            }
            last = nextLast;
            minimumSteps++;
        }
        
        return minimumSteps;
    }

思路三：BFS 广度优先算法

再回到正序遍历，举个例子，输入的数组为[2,3,1,1,4],这时候我们知道0步时的下标为0，1步可以走到的下标包括1，2，2步可以走到的下标为3，4，而4即为我们的终点。
转换为广度优先算法即为：

2   step 0
31  step 1
14  step 2

我们只需要找到每一步的开始节点和结束下标，找到下一轮遍历的最大下标，如果该下标超过了数组长度，那么结束遍历，返回步数，否则将上一轮的最终节点加一作为起始节点，并将下一轮最大下标最为结束节点，继续遍历。

  public int jump3(int[] nums){
        int length = nums.length ; 
        if(length<2) return 0;
        int currentMax = 0, i = 0, nextMax = 0, level = 0;;
        while(currentMax-i+1 > 0){
            level++;
            for( ; i <= currentMax ; i++){
                nextMax = Math.max(nextMax, nums[i]+i);
                if(nextMax>=length-1) return level;
            }
            currentMax = nextMax;
        }
        //说明无法到达终点
        return nextMax>=length-1? level : -1;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云 GPU服务器 Jump jump.php Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67380.html

LeetCode[45] Jump Game II

摘要：复杂度思路每次设置一个窗口，观察在这一步下能到达的最远距离，不断的移动这个窗口。计数，需要移动几次，才能覆盖到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...

keelii 2019-08-14 15:02 评论0 收藏0
[LintCode/LeetCode] Jump Game I & II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0
[Leetcode] Jump Game 跳跃游戏

摘要：代码记录下当前区域的上界，以便待会更新下一个区域的上界更新下一个区域的上界更新下一个区域的下界后续如果要求返回最短跳跃路径，如何实现可以使用，并根据一个全局最短步数维护一个全局最短路径，当搜索完所有可能后返回这个全局最短路径。 Jump Game I 最新解法请见：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

venmos 2019-08-14 12:24 评论0 收藏0
leetcode55 Jump Game

摘要：当前起点为数组中下标为零的位置，要走到数组的最后一个下标。其中，数组中每一个元素代表当前下标下可以前进的最大步数。如果最终的终点就是起始节点，那么肯定可以从其实节点找到一条路径到达终点，否则失败。题目要求 Given an array of non-negative integers, you are initially positioned at the first index o...

AlanKeene 2019-08-14 18:44 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0