题目描述
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例1
- 输入：nums = [2,3,1,1,4]
- 输出：true
- 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例2
- 输入：nums = [3,2,1,0,4]
- 输出：false
- 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示
- 1 <= nums.length <= 3 * 104
- 0 <= nums[i] <= 105
解法
思路一：贪心算法（尽可能去最远的位置）
如果能够到达最远的地方，那一定能到到最远前面的任意地方。
- 遍历数组，把每个位置都作为起始点，设置最远能够到达位置为0
- 更新最远能够到达的位置，能够到达的最远的位置为当前位置索引+当前元素的值
- 如果每个位置都能够到达，则可以成功，否则失败
AC代码
var canJump = function(nums) {
let k = 0;
for (let i = 0; i < nums.length; i++) {
// 判断能否到达i位置，不能则也不能够到达终点，终止，直接返回结果false
if (i > k) return false;
// 更新能够到达的最远位置
k = Math.max(k, nums[i] + i);
// 如果能够到达的最远位置超过终点，则提前跳出循环
if (k > nums.length) {
return true
}
}
return true;
};
思路二：只要最后一步前所有的元素都大于0,就可以到达
从后往前遍历,只要0前面的元素存在nums[i] > (0的索引 - i) 就能够到达
AC代码
var canJump = function(nums) {
// 如果nums只有一个元素，则一定可以到达
if (nums.length === 1) return true;
let cover = 0;
for (let i = 0; i < nums.length; i++) {
cover = Math.max(cover, i + nums[i])
if(cover == i && nums[i] == 0 && i !== nums.length - 1) {
return false;
}
if (cover >= nums.length - 1) return true;
}
};
总结
主要是能够理解，最远能到达某个位置，就一定能到达它前面的任何位置。
