1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 55. 跳跃游戏

55. 跳跃游戏

链接:https://leetcode-cn.com/problems/jump-game/
难度:中等

题目

思路

这题很容易想到从后面开始往前面跳。如果倒数第一可以达到,那最后就可以达到。

其实我们可以换一种想法,如果某一个作为起跳点的格子可以跳跃的距离是3,那么表示后面3个格子都可以作为起跳点。我们可以对每一个能作为起跳点的格子都尝试跳一次,把能跳到最远的距离不断更新。如果可以一直跳到最后,就成功了。

为什么要保持跳到最远距离,这是因为我们认为,如果能跳到这个点,那其实左边的任何点其实都可以跳到。

代码见解决方案。

方案代码

解决方案:

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

        current = 0

        for i in range(len(nums)):
            if i > current:
                return False 
            current = max(current, i+nums[i])

        return True

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/333.html