目录
核心:数组遍历 最远可以到达的位置的维护
技巧:实际数组例子带入 抽象写代码
1,题目
给你一个非负整数数组 nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true
;否则,返回 false
。
2,代码
贪心算法
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
let maxDis = 0;
const len = nums.length;
for(let i=0;i<len;i++){
if(i <= maxDis){
maxDis = Math.max(i+nums[i],maxDis);
if(maxDis >= len -1){
return true;
}
}else{
return false;
}
}
};
3,学习与总结
3.1 解题思路巩固
题意抽取:
只要存在一个位置x,它本身可以到达,并且它跳跃的最大长度为x+nums[x];
对于一个可以到达的位置x,它使得x+1 x+2 x+3......x+nums[x]都可以到达;
解题思路:
- 遍历数组,实时维护最远可以抵达的位置。对于当前遍历的位置x,如果在最远可以抵达的位置范围内,则我们可以从起点到达该x位置,因此我们需要判断更新最新的最远可以抵达的位置;
- 如果最远可以抵达的位置大于等于数组中的最后一个位置,则数组最后位置是可达的,返回true;
- 如果遇到位置x 大于最远可以抵达的位置,则说明数组跳跃中断,返回false;
3.2 记录错误
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
let maxDis = nums[0];
const len = nums.length;
for(let i=1;i<len;i++){
if(i <= maxDis){
maxDis = Math.max(i+nums[i],maxDis);
if(maxDis >= len -1){
return true;
}
}else{
return false;
}
}
};
报错内容:
原因分析:
没有考虑到数组长度仅为1的情况