X

LEETCODE 45. Jump Game II 解题思路分析

题目大意:

跳跃游戏 II

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

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

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

示例:

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

说明:

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


这道题需要使用贪心算法。试想,如果想使用最少步数跳跃到最后一位,那么我们每一步都需要尽量跳的远一些。如果想要保证每一步都要跳的尽量远,那么必将需要牺牲一些局部利益来保障全局利益最大化。我们先看当前位置能够跳到的范围,比如当前位置是i,那么从第i位能跳到的范围应该是[i+1, i+nums[i]]。显然,这个范围越大,我们下一步的选择就越多,并且我们距离终点也就越近,因此,当范围右端不是终点的前提下,下一步的最优解应该是范围内能跳到最远距离的点。注意能跳到最远距离的点不仅取决于nums[i],也取决于i。比如区间范围是[10, 15],其中nums[10]=5, nums[14]=4,虽然nums[10]大于nums[14],但从位置10我们最多能跳到15,而从位置14我们可以跳到18,因此下一步跳跃到14更好一些(相对10来说,实际解题时我们还需查看下标11,12和15的值)。

实现代码:

public int jump(int[] nums) {
    int res=0; // 步数
    int index=0; // 当前位置
    while(index<nums.length-1){
        int n=nums[index]; // 当前可跳跃的距离
        int left=index+1; // 跳跃范围的左边界
        int right=index+n; // 跳跃范围的右边界
        int max=0; // 跳跃范围内的所有点中,能够跳跃最远的点
        // 如果有边界已经超越了终点,返回
        if(right>=nums.length-1) return res+1;
        // 查看范围内每一个点
        for(int i=left;i<=right;i++){
            // 如果当前位置加上跳跃距离能够到达更远的距离
            if(i+nums[i]>=max){
                max=i+nums[i]; // 更新最远距离
                index=i; // 更新下一步为该坐标
            } 
        }
        res++;
    }
    return res;
}

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

Runtime: 2 ms, faster than 44.46% of Java online submissions for Jump Game II.

Memory Usage: 42.1 MB, less than 5.77% of Java online submissions for Jump Game II.

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