算法
End of Array Reachable
numbers[i] 表示从 i 位置最多能跳多远,问能否从 0 跳到最后一个下标。
初解
function arrayReachableEnd(numbers: number[]): boolean {
const n = numbers.length;
let sum = 0;
if (numbers[0] === 0) return false;
for (const num of numbers) {
sum += num;
}
return sum >= n;
}部分用例无法通过:
[1, 0, 100]
[2, 0, 0]
sum 小,不代表跳不到;sum 大,也不代表跳得到。
思路
贪心
只需要维护一个变量 maxReach,表示目前能到达的最远下标。
步骤
- 初始化
maxReach = 0 - 遍历数组
i,从 0 到最后:- 如果
i > maxReach,说明已经无法走到i,更不可能走到终点,直接返回false - 更新
maxReach = max(maxReach, i + numbers[i])
- 如果
- 如果遍历完成没有中断,则一定能到达终点,返回 true
代码
function canJump(numbers: number[]): boolean {
let maxReach = 0;
for (let i = 0; i < numbers.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + numbers[i]);
}
return true;
}- 因为
maxReach始终记录从前面所有可达点能跳到的最远距离 - 如果某个
i无法到达,则i之后的位置更不可能到达 - 只要你遍历到最后一个
index,就说明中间没有断层
时间复杂度: 空间复杂度:
在 GitHub 上编辑
上次更新于