[Leetcode] Jump Game 跳跃游戏

venmos 发布于2019-08-14 12:24 / 1803人阅读

摘要：代码记录下当前区域的上界，以便待会更新下一个区域的上界更新下一个区域的上界更新下一个区域的下界后续如果要求返回最短跳跃路径，如何实现可以使用，并根据一个全局最短步数维护一个全局最短路径，当搜索完所有可能后返回这个全局最短路径。

Jump Game I 最新解法请见：https://yanjia.me/zh/2019/01/...

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.

贪心法 复杂度

时间 O(N) 空间 O(1)

思路

如果只是判断能否跳到终点，我们只要在遍历数组的过程中，更新每个点能跳到最远的范围就行了，如果最后这个范围大于等于终点，就是可以跳到。

代码

public class Solution {
    public boolean canJump(int[] nums) {
        int max = 0, i = 0;
        for(i = 0; i <= max && i < nums.length; i++){
            max = Math.max(max, nums[i] + i);
        }
        return i == nums.length;
    }
}

Jump Game II

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.)

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

如果要计算最短的步数，就不能贪心每次都找最远距离了，因为有可能一开始跳的远的路径，后面反而更慢。所以我们要探索所有的可能性，这里用快慢指针分出一块当前结点能跳的一块区域，然后再对这块区域遍历，找出这块区域能跳到的下一块区域的上下边界，每块区域都对应一步，直到上界超过终点时为之。

代码

public class Solution {
    public int jump(int[] nums) {
        int high = 0, low = 0, preHigh = 0, step = 0;
        while(high < nums.length - 1){
            step++;
            //记录下当前区域的上界，以便待会更新下一个区域的上界
            preHigh = high;
            for(int i = low; i <= preHigh; i++){
                //更新下一个区域的上界
                high = Math.max(high, i + nums[i]);
            }
            //更新下一个区域的下界
            low = preHigh + 1;
        }
        return step;
    }
}

后续 Follow Up

Q：如果要求返回最短跳跃路径，如何实现？
A：可以使用DFS，并根据一个全局最短步数维护一个全局最短路径，当搜索完所有可能后返回这个全局最短路径。

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

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

Chrome 小恐龙游戏源码探究八 -- 奔跑的小恐龙

摘要：例如，将函数修改为小恐龙眨眼这样小恐龙会不停的眨眼睛。小恐龙的开场动画下面来实现小恐龙对键盘按键的响应。接下来还需要更新动画帧才能实现小恐龙的奔跑动画。文章首发于我的 GitHub 博客前言上一篇文章：《Chrome 小恐龙游戏源码探究七 -- 昼夜模式交替》实现了游戏昼夜模式的交替，这一篇文章中，将实现：1、小恐龙的绘制 2、键盘对小恐龙的控制 3、页面失焦后，重新聚焦会重置...

paulquei 2019-08-23 17:09 评论0 收藏0
揭密微信跳一跳小游戏那些外挂

摘要：所以，我们这个小游戏发布以后，我们就开始花了很多很多时间来打击外挂。二距离判断像素点判断该方法采用自目前最火的跳一跳小游戏辅助程序。作者：Hahn，腾讯高级UI工程师商业转载请联系腾讯WeTest获得授权，非商业转载请注明出处。原文链接：http://wetest.qq.com/lab/view/364.html WeTest 导读张小龙：这个游戏发布以后，其实它的效果有点超...

lyning 2019-06-21 16:40 评论0 收藏0
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