Simple Accepted Python Solution


  • 0
    J

    Greedy strategy. From left to right, for a stop at i, it choose next stop j as:

    1. j must reachable from i, which means j is from position [i+1, i+ A[i]] .
    2. A[j] should be the largest one

    Namely, we choose the j that can help us reach as far as we can.

    class Solution:
        # @param A, a list of integers
        # @return an integer
        def jump(self, A):
            if not A or len(A) == 1:
                return 0
    
            cur = 0
            count = 0
            while(cur<len(A)):
                maxReach = -1
                idx = 0
                for i in range(1,A[cur]+1):
                    if cur+i >= len(A)-1:
                        return count+1
                    else:
                        if A[cur+i] + i > maxReach:
                            maxReach = A[cur+i] + i
                            idx = cur+i
                cur = idx
                count +=1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.