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.
For example:Given array A =[2,3,1,1,4]
The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index.)
This is also a greedy problem the difference between this one and the jump game is this time we need to count how many step we need to go from the start to the end.
we need to go through the whole array for once. The complexity if O(n).
we need two extra pointers "last" to track last element and count to track how many step we need to go.
code is as follow:
class Solution:# @param A, a list of integers# @return an integerdef jump(self, A):index=0count=0last=0reach=0while reach>=index and index<len(A):if last<index:count+=1last=reachreach=max(reach,A[index]+index)index+=1if reach<len(A)-1:return 0else:return count
，到尽头，也许快乐，或有时孤独，如果心在远方，
