[LeetCode] Jump Game II

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.

Your goal is to reach the last index in the minimum number of jumps.

Actually I got no trick for this problem, I just find forward, and see for each node of array, what is the current maximum place we can reach, and every time we reach a local maximum, we add counter by 1, if we can reach the terminal, just return the counter.

For example, A = [2,3,1,1,4]

At beginning, we set counter to be 0, during first counter cycle, we check A[0], which is 2, and so far we are able to reach A[0 + 2].

So during the second counter cycle, we check everything before the most far place we can reach, so let’s check A[1] and A[2], A[1] is 3, so we are now able to reach A[1 + 3], and it is the terminal, so we return 2.

Here is the code.

    int jump(int A[], int n) {
        int start = 0;  
        int end = 0;  
        int count =0;  
        if(n == 1) return 0;  
        while(end < n)  
        {  
            int max = 0;  
            count ++;  
            for(int i = start; i <= end ; i ++ ){   
                if(A[i] + i >= n-1){            
                    return count;  
                }  
                if(A[i] + i > max){
                    max = A[i] + i;  
                }
            }  
           start = end + 1;  
           end = max;        
        }         
    }

 

:p

This entry was posted in Algorithm, LeetCode and tagged , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

One Comment

  1. pipikaqiu
    Posted January 28, 2014 at 4:33 pm | Permalink

    I strongly recommend you to add the complexity analysis to your algorithms.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*