#55 Jump Game——Top 100 Liked Questions-蒲公英云

#55 Jump Game——Top 100 Liked Questions

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.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

“””
第一次：num[i]+i为i位置所等到达的最大距离，遍历后如果最大距离小于L-1，说明不能到达末尾，如果>=L-1，说明肯定能到达末尾。同时在每次遍历时，应使dist>=i，这是为了避免元素为零的特例
“””
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        L = len(nums)
        dist = 0
        for i in range(L-1):
            if dist >= i:
                dist = max(dist, i + nums[i])
        if dist < L - 1:
            return False
        return True
“””

Runtime: 72 ms, faster than 58.03% of Python online submissions for Jump Game.

Memory Usage: 13.3 MB, less than 33.52% of Python online submissions for Jump Game.

“””