Simple code of Python 100ms


  • 0
    R
    def jump(self, A):
        if len(A) == 1:
            return 0
        i = 0
        result = 0
        while i < len(A):
            if A[i] + i >= len(A)-1:
                return result + 1
            max_inc = 0
            max_j = 0
            for j in xrange(A[i]):
                inc = A[i+j+1] + j + 1
                if inc > max_inc:
                    max_inc = inc
                    max_j = j+1
            i = i+max_j
            result += 1
    

    The key is to calculate the maximum jump length every time. This is the core concept of greedy algorithm.
    But how to calculate that? Suppose you are positioned at index n . A[n] is the maximum length you can jump. However, this number may not be the length you want. Because you may get 1 after jumping the maximum length and get 100 after jumping only 1 length. So what you should calculate is the maximum of sum of A[n+k] and k . And k is the length you want


Log in to reply
 

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