LeetCode 55 - Jump Game

作者 QIFAN 日期 2017-01-17
LeetCode 55 - Jump Game

原题链接: 55. Jump Game


题干

给定一个数字数组 S ,每个元素代表从该位置可以向前的最大步数,若从起点 0 开始,返回能否到达数组最后。

举例
输入: S = [2,3,1,1,4]
输出: true

思路

首先有一个问题提出:能不能反复跳?假设不能。

第一想法是动态规划,从倒数第二个点开始判断,如果能跳到下一个点,则检查前一个点直到起点,若不能则直接返回 true 。这显然不行。因为没有考虑到中间可能有 0 但是可以隔着跳的情况。比如[2,0,0]。

于是我换了一种思路。对于每个位置 i ,设 nums[i] = x 。那下一步有 x 种可能 nums[i + 1] 到 nums[i + x] 。用树?我觉得用递归好一些。因为直接用 primitive type ,空间会小一些。

但是我 TLE 了,然后就卡住了。

去看 discussion ,特别简单。核心思想就是:如果位置 i 可以跳到上次确认可以跳到最后的点 j ,那就可以从位置 i 跳到最后,另 j = i 。

时间复杂度为 $O(N)$ ,一口老血吐出来。

代码:

public boolean canJump(int A[]) {
int last = nums.length - 1;
int i, j;
for(i = nums.length - 2; i >= 0; i--){
if(i + A[i] >= last) {
last=i;
}
}
return last <= 0;
}