Leetcode[数组] 跳跃游戏 -

发布于:2021-07-20 04:49:10

0 题目描述

leetcode原题链接:跳跃游戏


1 贪心算法

思路:尽可能到达最远位置(贪心)
如果能到达某个位置,那一定能到达它前面的所有位置。
方法:初始化最远位置为 0,然后遍历数组,如果当前位置能到达,并且当前位置+跳数>最远位置,就更新最远位置。如果当前位置比最远位置还要远,直接返回False。


class Solution:
def canJump(self, nums: List[int]) -> bool:
# 最远到达位置
reach = 0
for i in range(len(nums)):
if i > reach: return False
reach = max(reach, i + nums[i])
return True

复杂度分析:
时间复杂度




O


(


n


)



O(n)


O(n),空间复杂度




O


(


1


)



O(1)


O(1)。


参考资料

Python击败97%,看不懂你锤我

相关推荐

最新更新

猜你喜欢