首页 > itarticle > leetcode_jump game

leetcode_jump game

admin 11月 13, 2020 0

Jump Game

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. 贪心算法

遍历数组，求得可到达的最远 index。若index > n-1，则可以到达最后。具体实现方法如下：

class :
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        max_index = 0
        n = len(nums)
        if n <= 1:
            return True
        
        for i in range(n-1):
            if max_index >= i:
                max_index = max(max_index, i + nums[i])
            if max_index >= n-1:
                return True 
        return False