05 August 2008
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
1
2
3
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
1
2
3
4
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
这道题首先可以用DP， 维护一个一位数组dp，其中dp[i]表示达到i位置时剩余的步数，到达当前位置跟上一个位置（不是前一个位置）的剩余步数和数字（能达到的最远位置）有关，下一个位置的剩余步数（dp值）就等于当前的这个较大值减去1，因为需要花一个跳力到达下一个位置，所以状态转移方程：dp[i] = max(dp[i - 1], nums[i - 1]) - 1，如果当某一个时刻dp数组的值为负了，说明无法抵达当前位置，则直接返回false，最后判断数组最后一位是否为非负数即可知道是否能抵达该位置。
Greedy的做法会更优，因为其实没有必要用维护一维数组的方式来对每一步的剩余步数进行关注，只知道是否能到达末尾就行了，只需维护一个变量reach，来记录当前步最远能到达的位置坐标，初始为0，遍历整个数组，如果当前的坐标大于reach或者reach已经到达最后一个位置或超出，就跳出循环；否则就更更新reach为当前reach的值和i + nums[i]中的较大值。
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
// dp[i] = max(dp[i - 1], nums[i - 1]) - 1，
// 当前状态等于上一个状态和选择当前的数中的最大值，同时减去当前跳的一步
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return true;
}
int len = nums.length;
int[] dp = new int[len];
// Arrays.fill(dp, 0);
// dp[0] = 0; // 表示总是处在第一个位置，0表示刚好达到
for (int i = 1; i < len; i++) {
dp[i] = Math.max(dp[i - 1], nums[i - 1]) - 1;
if (dp[i] < 0) {
return false;
}
}
return true; // return dp[len - 1] >= 0; //到这里总是true
}
}
考虑状态压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
// dp[i] = max(dp[i - 1], nums[i - 1]) - 1
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return true;
}
int len = nums.length;
int prev = 0, curr = 0;
for (int i = 1; i < len; i++) {
curr = Math.max(prev, nums[i - 1]) - 1;
if (curr < 0) {
return false;
}
prev = curr;
}
return curr >= 0;
}
}
Greedy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
int reach = 0;
for (int i = 0; i < len; i++) {
if (i > reach || reach >= len - 1) {
break;
}
// 寻找最远跳力
reach = Math.max(reach, i + nums[i]);
}
return reach >= len - 1;
}
}