Same idea as Jump Game I, with more details and count each iteration until reach the end.
public class Solution {
public int jump(int[] A) {
if(A == null || A.length < 2){
return 0;
}
int jump = 0;
int index = 0;
while(index < A.length){
int insideLoop = 0;
int dist = A[index] + index;
int nextIndex = -1;
while(insideLoop <= A[index]){ //index overflow?already excluded
if(A[index + insideLoop] >= A.length - 1 - index - insideLoop){
return jump + 1 + ((insideLoop == 0) ? 0 : 1);
}else{
if(A[index + insideLoop] + index + insideLoop > dist){
dist = A[index + insideLoop] + index + insideLoop;
nextIndex = index + insideLoop;
}
insideLoop++;
}
}
jump++;
if(nextIndex == -1){
return 0;
}
index = nextIndex;
}
return Integer.MAX_VALUE;
}
}
没有评论:
发表评论