2014年5月11日星期日

Loop Solution - Jump Game II

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;
    }
}

没有评论: