Comment on page

55.Jump-Game

55. Jump Game

题目地址

题目描述

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.

代码

Approach #1: Dynamic Programming

public class Solution {
public boolean canJump(int[] A) {
boolean[] f = new boolean[A.length];
f[0] = true;
​
for (int i = 1; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (f[j] && j + A[j] >= i) {
f[i] = true;
break;
}
}
}
return f[A.length - 1];
}
}

Approach #2: Greedy

public class Solution {
public boolean canJump(int[] A) {
if (A == null || A.length == 0) {
return false;
}
​
int farthest = A[0];
for (int i = 1; i < A.length; i++) {
if (i <= farthest && A[i] + i >= farthest) {
farthest = A[i] + i;
}
}
​
return farthest >= A.length - 1;
}
}
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int maxPos = nums[0];
​
for (int i = 1; i < n; i++) {
if (maxPos < i) {
return false;
}
maxPos = Math.max(maxPos, nums[i] + i);
}
return true;
}
}