X

LEETCODE 55. Jump Game 解题思路分析

题目大意:

跳跃游戏

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

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

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=55

解题思路分析:

由于数组中当前元素代表你在该位置可以跳跃的最大长度,因此为了能够跳到大于等于末尾位置,我们需要找到尽量跳跃长度远的点。初始时,位于index为0的位置,它能跳跃到最远的位置为nums[0],接下来我们在[1, nums[0]]区间找到一个最大值max,max代表了下一步能跳到的最远距离,如果该距离小于等于nums[0]的话,说明我们在当前可访问区间内任意一点都无法超越nums[0],则我们一定无法到达终点,返回false。反之,我们能到达的最远处更新为max,此时再在[nums[0] +1,max]范围内找到一个更远的max,重复上述逻辑,直到max大于等于终点位置时,返回true。

实现代码:

public boolean canJump(int[] nums) {
    int maxIndex=nums[0]; // 当前能够跳跃的最远位置
    int current=0; // 当前位置
    // 当最远位置小于终点位置时循环
    while(maxIndex<nums.length-1){
        // 下一步能够跳的最远位置
        int max=maxIndex;
        // 循环当前位置能都跳跃的区间,找到区间内能够到达的最远位置
        for(int i=current+1;i<=maxIndex;i++){
            max=Math.max(max, i+nums[i]);
        }
        // 如果下一步的最远位置不能超越当前位置最远位置,返回false
        if(max==maxIndex) return false;
        // 当前位置更新为原先能到达的最远位置
        current=maxIndex;
        // 最远位置更新为下一步最远位置
        maxIndex=max;
    }
    return true;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 96.88% of Java online submissions for Jump Game.

Memory Usage: 47.2 MB, less than 5.13% of Java online submissions for Jump Game.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-55-jump-game-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)