2014年2月14日星期五

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.

public class Solution {
    public boolean canJump(int[] A) {
        if(A==null || A.length==0) {
            return false;
        }
        int maxLeft = A[0];
        for(int i=1;i<A.length;i++) {
            maxLeft = Math.max(maxLeft, A[i-1]) - 1;
            if(maxLeft<0) {
                return false;
            }
        }
        return maxLeft>=0;
    }
}


============

public class Solution {
    public boolean canJump(int[] nums) {
        int maxCover = 0;
        for (int i = 0; i < nums.length; i++) {
            maxCover = Math.max(maxCover, i + nums[i]);
            if (maxCover >= nums.length - 1) {
                return true;
            }
            if (maxCover == i) {
                return false;
            }
        }
        return true;
    }
}

没有评论:

发表评论