leetcode刷题-55跳跃游戏

题目

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

思路

贪心算法：记录每一个位置能够跳跃到的最远距离，如果超过前者的距离则更新，如果不能则保留原距离。注意，在跳跃的时候，要确保当前位置是可达的，即是在最远距离内的。

实现

class Solution:

    def canJump(self, nums: List[int]) -> bool:

        maxjump = 0

        for i in range(len(nums)):

            if maxjump < i + nums[i] and maxjump >=i:

                maxjump = i + nums[i]

            if maxjump >= len(nums)-1:

                return True

        return False