Leetcode - Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
[분석] 폭력 방법은 모든 위치에서 i,nums[i]걸음으로 뛰어서 마지막에 도달할 수 있는지, 타당하고 시간을 초과하는 것이다.시간을 초과한case는 바로 무수한 1이다. 만약에 수조 중의 원소가 모두 정수라면 반드시 끝까지 뛸 수 있다는 것을 생각하게 한다. 따라서 관건은 수조 중의 0이 뛰어넘을 수 있는지 확인하는 것이다. 그래서 방법 2가 생겼고 틀림없이 더 좋은 것이 있을 것이라고 생각한다.자신의 역사 기록을 뒤져보면 코드가 자신보다 간소화되고 더 화가 나는 것은 이해하지 못하는 것이다,orz.인터넷에서 대신들의 해석을 찾았고 이해했다. 그리고 자신이 이전에 Accept를 받은 3가지 방법이 1가지밖에 남지 않았는데 지금도 Accept를 받을 수 있다는 것을 발견했다. 나머지는
http://blog.csdn.net/kenden23/article/details/17242835 이 블로그가 지적한 leetcode 오래된 테스트 케이스의 그물 빠진 물고기 중 하나는 귀속적인 실현으로 statck overflow를 초래하는 것이다.이 블로그가 지적한 이 문제에 찬성하는 관건은 명확한 종료 조건이다. 방법 2의 종료 조건은 모든 0이 건너뛸 수 있는지 판단하는 것이다. 효율은 O(n^2)이고 두 참고 블로그의 방법은 모두 O(n)이다. 방법 4의 종료 조건은 다음과 같다.
lastJump의 위치를 기록하고 i에서 lastJump, 모든 위치로 순환하여 그 중의 최대치를 찾아냅니다. maxJump =max {i+A[i]};만약 이 구간 내의 최대치 maxJump <=lastJump라면, 이 위치에서 벗어날 수 있는 위치가 하나도 없기 때문에 가짜로 돌아갑니다.이런 위치가 없으면 끝까지 뛸 수 있다면 진짜로 돌아간다.
방법3, 나의 이해, 탐욕스럽게 앞으로 뛰기, 순환이 끝나는 조건은 마지막이 되거나 계속 앞으로 뛰지 못하는 것이다.
[PS] ref2 블로거 Code_Ganker는 이 문제가 DP에 속한다고 생각하고 각종 알고리즘 사상에 대한 이해가 끊임없이 연습하는 과정에서 깊어지기를 바란다.교묘한 해법을 발견하는 것은 사람을 즐겁게 하는 일이다.
[ref]
http://blog.csdn.net/kenden23/article/details/17242835
http://blog.csdn.net/linhuanmars/article/details/21314059

public class Solution {
    // Method 4: O(n)
    // http://blog.csdn.net/kenden23/article/details/17242835
    public boolean canJump (int[] nums) {
        int lastJump = 0, maxJump = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxJump = Math.max(maxJump, i + nums[i]);
            if (i == lastJump) {
                if (maxJump == lastJump) return false;
                lastJump = maxJump;
            }
        }
        return true;
    }
    // Method 3: O(n), DP
    // http://blog.csdn.net/linhuanmars/article/details/21314059
    public boolean canJump3(int[] nums) {
        if (nums == null || nums.length == 0)
            return true;
        int maxJump = 0;
        int last = nums.length - 1;
        for (int i = 0; i <= maxJump && i < last; i++) {
            maxJump = Math.max(maxJump, i + nums[i]);
        }
        if (maxJump < last)
            return false;
        else
            return true;
    }
    
    // Method 2: O(n^2),  0 
    public boolean canJump2(int[] nums) {
        int lastZero = -1, currZero = -1;
        int i = 0;
        int N = nums.length;
        while (i < N) {
            int j = 0; // index which is expected to jump pass currZero
            while ( j < currZero) {
                if ((currZero != N - 1 && nums[j] > (currZero - j))
                    || (currZero == N - 1 && nums[j] >= (currZero - j))) { // currZero can be skipped
                    lastZero = currZero;
                    break;
                } else {
                    j++;
                }
            }
            
            if (j == currZero) return false;
            // search the next zero position
            while (i < N) {
                if (nums[i] == 0) {
                    currZero = i;
                    break;
                } else {
                    i++;
                }
            }
            i++;
        }
        return true;
    }
    // Method 1: time out
    public boolean canJump1(int[] nums) {
        return jump(nums, 0, nums.length - 1);
    }
    private boolean jump(int[] nums, int pos, int last) {
        if (pos >= last)
            return true;
        for (int step = 1; step <= nums[pos]; step++) {
            if (jump(nums, pos + step, last))
                return true;
        }
        return false;
    }
}