算法通关村第十七关-黄金挑战跳跃问题

大家好我是苏麟 , 今天说说跳跃问题 .

跳跃游戏

描述 :

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

题目 :

LeetCode 55.跳跃游戏 :

55. 跳跃游戏

分析 :

这里给个视频 : LeetCode力扣 55. 跳跃游戏 Jump Game_哔哩哔哩_bilibili

解析 :

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

跳跃游戏二

描述 :

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

题目 :

LeetCode 45.跳跃游戏

45. 跳跃游戏 II

分析 :

思路 :   贪心 + 双指针 

我们重新观察一下结构图，为了便于分析，我们修改一下元素序列，我们需要四个变量:

• left用来一步步遍历数组
• steps用来记录到达当前位置的最少步数
• right表示当前步数下能够覆盖到的最大范围
• 我们还需要一个临时变量conver，假如left到达right时才更新right

在这个图中，开始的元素是 2，如果只走一步，step=1，可跳的范围是{3,1}。也就是如果只走一步，最远只能到达1，此时conver=nums[0]=2，因此我们用right=nums[2]来保存这个位置，这表示的就是走一步最远只能到nums[2]

接下来，我们必须再走一步，step=2，如下图，此时可选元素是{3,1}，3能让我们到达的距离是left+nums[left]=1+3=4，而1能让我们到达的位置是left+nums[left]=2+1=3，而所以我们获得最远覆盖距离conver=4

然后用 left 和 right 将 step = 2 的范围标记一下

此时还没有到终点，我们要继续走，在这里我们可选择的元素是{2,4}，如果选择2，则可以到达left + nums[leftl=3+2=5,如果选择4则是left+nums[left]=4+4=8，已经超越边界了，所以此时一定将未尾覆盖了。

这样我们就知道最少需要走3次

解析 :

class Solution {
    public int jump(int[] nums) {
        int count = 0;
        int right = 0;
        int max = 0;
        for(int left = 0;left < nums.length - 1;left++){
            max = Math.max(nums[left] + left,max);
            if(left == right){
                right = max;
                count++;
            }
            if(right >= nums.length - 1){
                break;
            }
        }
        return count;
    }
}

这期就到这里 , 下期见!