Monday, March 4, 2013

[LeetCode] Jump Game II

Thought:
start: the starting index, inclusive.
end: the ending index, exclusive.
max: the max index that could be reached.
steps: the steps used.
We start from [start, end) to reach out, update the [start, end) to [end, max + 1)
if end = A.length(Or max >= A.length - 1), return the result.

Code:
public class Solution {
    public int jump(int[] A) {
        int start = 0, end = 1, max = 0, steps = 0;
        while (end < A.length) {
            steps++;
            for (int i = start; i < end; i++) {
                if (A[i] + i >= A.length - 1) return steps;
                max = Math.max(A[i] + i, max);
            }
            start = end;
            end = max + 1;
        }
        return steps;
    }
}

No comments:

Post a Comment