算法练习21:跳格子(leetcode 55)
2021-05-08 本文已影响0人
miao8862
题目
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
解题
遍历这个数组里的格子数,更新其能跳到的最远距离,当能跳到的最远距离大于等于最后一个下标时,代表着可以跳到。
[2,3,1,1,4]
- 第1步,下标0,数字2,能跳到的最远距离
arrDes = 0+2 = 2
- 第2步,下标1 < arrDes,说明这个格子是能跳到的,所以计算这个格子能跳的最远距离
arrDes1 = 1 + 3 = 4
,明显,这个距离比上个arrDes
大,即arrDes1 > arrDes
,所以更新arrDes = Math.max(arrDes, arrDes1) = 4
,发现arrDes = 数组最后一个下标4
,说明它能跳到最后,返回true,结束 - 如果发现当前遍历的下标,大于能跳到的最远距离时,说明永远无法跳到最后了
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
// 代表当前可跳到的最远可达点
let arriveDes = 0;
for(let i = 0; i < nums.length; i++) {
// 如果当前格子数下标数,小于等于能跳到的最远距离,就继续遍历计算最远距离
if(i <= arriveDes) {
arriveDes = Math.max(arriveDes, i + nums[i])
if(arriveDes >= nums.length - 1) return true;
// 否则,当格子下标数超过可跳到的最远距离,代表着永远不可能到最远距离了
}else{
return false;
}
}
};
console.log(canJump([2,3,1,1,4])) // true