大纲
判断给定数组从第一个元素开始,能否跳动到最后个位置
示例
nums = [2,3,1,1,4]
true
可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
nums = [3,2,1,0,4]
false
无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
思路
- 最大跳跃数如果大于等于数组长度,就代表能够跳跃,并不是一定要到数组的最后个位置
- 每次跳跃的时候,都是当前位置加上可跳跃的长度记录下来
- 每次跳跃的时候,都比较下当前位置是否超过了记录的跳跃长度,如果跳跃长度小于当前位置,代表跳到了无法到达的位置
- 每次记录长度的时候都要与上次跳跃记录下的长度取最长,然后再数组长度进行比较,(1)的逻辑
解释
```javascript arr = [1,3,1,1,4]; // 当前的跳跃长度是0 distance = 0; // 进行第一次跳跃的时候,来到了下标0的地方,跳跃长度为1 distance = 0 + 1; // 记录下了跳跃长度为1
// 第二次跳跃时,下标1,跳跃长度为3 // 进行一次判断,当前的下标 i = 1;distance = 1; // 跳跃的距离没有超出可跳(distance)长度 if (i > distance) { // 如果超出范围,就表明不可跳到数组结束 return false; }
// 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长 // distance = Math.max(1, 3 + 1) distance = Math.max(distance, arr[i] + i);
// 当前可跳到4的位置,所以当前直接就可以判定,能够跳到数组结尾 if (distance >= arr.length) { return true; }
```javascript
arr = [3,2,1,0,4]
distance = 0;
// 进行第一次跳跃的时候,来到了下标0的地方,跳跃长度为3
distance = 0 + 3; // 记录下了跳跃长度为3
// 第二次跳跃时,下标1,跳跃长度为2
// 进行一次判断,当前的下标 i = 1;distance = 3;
// 跳跃的距离没有超出可跳(distance)长度
if (i > distance) {
// 如果超出范围,就表明不可跳到数组结束
return false;
}
// 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长
// distance = Math.max(3, 1 + 2),没有变化
distance = Math.max(distance, arr[i] + i);
// 第三次跳跃时,下标2,跳跃长度为1
// 进行一次判断,当前的下标 i = 2;distance = 3;
// 跳跃的距离没有超出可跳(distance)长度
if (i > distance) {
// 如果超出范围,就表明不可跳到数组结束
return false;
}
// 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长
// distance = Math.max(3, 2 + 1), 没有变化
distance = Math.max(distance, arr[i] + i);
// 第四次跳跃时,下标3,跳跃长度为0
// 进行一次判断,当前的下标 i = 3;distance = 3;
// 跳跃的距离没有超出可跳(distance)长度
if (i > distance) {
// 如果超出范围,就表明不可跳到数组结束
return false;
}
// 比较当前的位置提供的跳跃长度,是不是比上次记录的跳跃长度长
// distance = Math.max(3, 3 + 0), 没有变化
if (i > distance) {
// 如果超出范围,就表明不可跳到数组结束
return false;
}
// 第五次跳跃时,下标4,跳跃长度为4
// 进行一次判断,当前的下标 i = 4;distance = 3;
// 跳跃的距离超出可跳(distance)长度
// 4 > 3
if (i > distance) {
// 如果超出范围,就表明不可跳到数组结束
return false;
}
// 结束了循环,已经跳到了不可能到达的下标位置
实现
function canJump(nums) {
let distance = 0;
const len = nums.length;
for (let i = 0; i < len; i++) {
if (i > distance) {
return false;
}
distance = Math.max(distance, nums[i] + i);
if (distance >= len) {
return true;
}
}
return true;
}