跳跃游戏问题（算法村第十七关黄金挑战）

跳跃游戏

55. 跳跃���戏 - 力扣（LeetCode）

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

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

示例 1：

输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

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

解

其实不用关心跳几步，怎么跳，而是要关心最大的跳跃范围能不能覆盖到终点

public boolean canJump(int[] nums){    int coverage = 0;   //覆盖范围    for (int i = 0; i         //每遍历一个位置，覆盖范围要么不变，要么延伸。        coverage = Math.max(coverage, i + nums[i]);        //如果终点在当前覆盖范围内，那一定有办法跳到终点        if (coverage = nums.length - 1)            return true;    }    return false;}

跳跃游戏 Ⅱ

45. 跳跃游戏 II - 力扣（LeetCode）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。（意思是nums[0]所在的位置，即索引为0处，跟上一题一个意思）

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

• 0 //起点即终点，不需要跳 if (nums.length == 1) return 0; int maxBoundary = 0; int right = 0; int step = 0; //left负责寻找最大覆盖范围，right负责跳到覆盖边界，step负责记录right跳跃的步数 for (int left = 0; left