Thursday, January 8, 2015

LeetCode 55: 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) {
        // Note: The array may have number 0.
        // If the array doesn't have 0, return true;
        // If the array has 0, you should check if the number before 0 can privide with steps to pass 0
        // We don't need consider the last number even though it is 0
        // If the first number is 0, return false.
        int n = A.length;
        
        if (n == 0)
            return false;
            
        if (n == 1)
            return true;
            
        // If the first number is 0, return false.    
        if (A[0] == 0)
            return false;            
        
        // All of the zero numbers index (Note: don't consider the last element)
        List<Integer> zeroIndex = new LinkedList<>();
        
        for (int i = 1; i < n-1; i++)
            if (A[i] == 0)
                zeroIndex.add(i);
        
        // If no 0 number        
        if (zeroIndex.isEmpty())
            return true;
        
        boolean pass; // If there is any qualified element, pass = true.
        
        for (int id : zeroIndex)
        {
            pass = false;
            
            for (int i = 0; i < id; i++)
                // i + A[i] represents the position that skipped to.
                if (i+A[i] > id)
                    pass = true;
            
            // If there isn't any qualified elements before 0, return false.        
            if (!pass)
                return false;
        }
        
        return true;
    }
}

No comments:

Post a Comment