leetcode55 Jump Game

AlanKeene 发布于2019-08-14 18:44 / 1130人阅读

摘要：当前起点为数组中下标为零的位置，要走到数组的最后一个下标。其中，数组中每一个元素代表当前下标下可以前进的最大步数。如果最终的终点就是起始节点，那么肯定可以从其实节点找到一条路径到达终点，否则失败。

题目要求

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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

翻译过来就是，假设有一个数组，该数组中的元素全部都是非负整数。当前起点为数组中下标为零的位置，要走到数组的最后一个下标。其中，数组中每一个元素代表当前下标下可以前进的最大步数。如果可以从起点走向终点，那么返回true，否则返回false

思路一：递归backtracking

最直接想法，就是通过递归遍历当前点作为起始点是否可以走到终点。这种思路的结果是代码超时。细想一下，前一个节点的遍历可能和后一个节点的遍历出现路径上的重复，但是这些重复的结果并没有被重复利用。所以这种方法虽然直观但是效率低下。
代码如下

    public boolean canJump(int[] nums) {
        int lastIndex= nums.length - 1;
        if(lastIndex < 0){
            return false;
        } 
        return canJump(nums, 0, lastIndex);
    }
    
    public boolean canJump(int[] nums, int currentIndex, int lastIndex){
        int remainSteps = nums[currentIndex];
        if(currentIndex + remainSteps >= lastIndex){
            return true;
        }
        
        while(remainSteps-- > 0){
            boolean canJump = canJump(nums, ++currentIndex, lastIndex);
            if(canJump){
                return true;
            }
        }
        return false;
    }

思路二：逆转遍历

其实通过对上一种思路的观察，可以知道，如果某一个节点可以通过某种路径到达终点，那么所有可以到达这一个节点的其他节点也一定可以到达终点。如果从终点向起点遍历，已知终点本身肯定可以到达自己，那么可以依次向前遍历，判断当前节点是否能够达到终点。如果能够找到这么一个节点，就将该节点设为新的终点，并按照之前的思路继续遍历，直到起始节点。如果最终的终点就是起始节点，那么肯定可以从其实节点找到一条路径到达终点，否则失败。
代码如下：

    boolean canJump2(int A[]) {
        int last=A.length-1,i;
        for(i=last-1;i>=0;i--){
            if(i+A[i]>=last)last=i;
        }
        return last==0;
    }

其实，这道题的官方也给出了明确的循序渐进的思路，可以进行参考

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

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

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

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

leetcode45. Jump Game II

摘要：转换为广度优先算法即为我们只需要找到每一步的开始节点和结束下标，找到下一轮遍历的最大下标，如果该下标超过了数组长度，那么结束遍历，返回步数，否则将上一轮的最终节点加一作为起始节点，并将下一轮最大下标最为结束节点，继续遍历。题目要求 Given an array of non-negative integers, you are initially positioned at the ...

shiguibiao 2019-08-15 10:50 评论0 收藏0
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
[leetcode] 403. Frog Jump

摘要：还有一个石头可能由之前的多个石头到达，这又是可以优化的地方。当前结果可由之前的结果得出，且有重复的搜索方法，就需要用。 [链接描述]leetcode 题目。有点类似于jump game，只不过这里对步数有了隐形的要求，当前步数和之前步数有关。如果我们用brute force的方法来解，每一步有三种可能，一共n个石头，时间复杂度就是O(3^n)。这其中有很多步数是多余的，第i个石头...

mo0n1andin 2019-08-14 16:52 评论0 收藏0