The idea is to loop the array, update the loop index by find the furthest distance within its range: i + [cur + i], by a inner loop. Before the inner loop, the next index candidate is initialized to be cur, and after the loop, if still next == cur, return false, otherwise next = new index. At the outer loop, each iteration verify if its capacity/value can reach the end. Outer loop to end - 1 (< A.length - 1) is enough, since if code reach here and is able exit the code, means that it has already reached the end. return true then.
public class Solution {
public boolean canJump(int[] A) {
if(A == null || A.length == 0){
return true;
}
int cur = 0;
while(cur < A.length - 1){
if(A[cur] >= A.length - 1 - cur){
return true;
}
int nextIndex = cur;
int distance = A[cur];
for(int i = 1; i <= A[cur]; i++){
if(A[cur + i] + i > distance) {
distance = A[cur + i] + i;
nextIndex = cur + i;
}
}
if(cur == nextIndex) return false;
cur = nextIndex;
}
return true;
}
}
没有评论:
发表评论