2014年5月11日星期日

Loop Solution - Jump Game

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

没有评论: