[leetcode]55.跳跃游戏

[MagicalBridge]

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

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

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

示例一：

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

示例二:

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

这道题目说的是有一个非负整数数组，每个数字表示在当前位置的最大跳力（这里的跳力指的是在当前位置为基础上能到达的最远位置），求判断能不能达到最后一个位置，其实刚开始理解的时候我以为必须刚好达到最后一个位置，超过了不算，其实这种理解是有问题的，因为每个位置上的数字表示的是最大的跳力，而不是像大富翁游戏上表示的骰子摇出来是几就只能挑几格。

这道题目使用贪婪算法比较合适，因为这里并不是很关心每一个位置上的剩余步数，而只是希望知道能否达到末尾，也就是说，我们只对最远能够达到的位置感兴趣，所以维护一个变量reach,表示最远能够达到的位置，初始化为0，遍历数组中的每一个数字，如果当前坐标大于reach或者reach已经抵达最最后一个位置则跳出循环，佛否则就更新react的值为其和i+nums[i]中较大的值,其中i+nums[i]表示当前位置能够到达的最大位置。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
 let n = nums.length;
 let reach = 0;
 for (let i = 0; i < n; i++) {
 if (i > reach || reach >= n-1) {
 break;
 }
 reach = Math.max(reach, i + nums[i]);
 }
 return reach >= n-1
};

第二种解题思路:

• 如果某一个作为起跳点的格子可以跳跃的距离是3，那么表示后面的3个格子都可以作为。
• 可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
• 如果可以一直跳到最后，就成功了。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
 // reach 代表跳到的最远的距离
 let reach = 0;
 for (let i = 0; i < nums.length; i++) {
 // 如果遍历的到的索引已经比最远能到到的距离还要大 说明根本没有机会再继续走下去
 if (i > reach) {
 return false;
 }
 reach = Math.max(i + nums[i]);
 }
 return true;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
• 空间复杂度：O(1)，不需要额外的空间开销。