leetcood学习笔记-55-跳跃游戏
题目描述:
第一次提交:
class Solution: def canJump(self, nums: List[int]) -> bool: if len(nums)<=1: return True for i,v in enumerate(nums): if i == 0 and v == 0: return False if v == 0 and i<len(nums)-1: r = False m = 1 for j in range(i-1,-1,-1): if nums[j]>m: r = True break m+=1 if not r:return False else: return True
方法二: O(N)
数组从后往前遍历:
- 如果该位置能跳跃到达最后一位:截断数组,置数组最后一位下标
end = i
- 该位置不能跳跃到达最后一位:继续向前遍历
遍历结束后判断 end
的位置,如果数组仅剩一位元素则返回 True
。
class Solution: def canJump(self, nums: List[int]) -> bool: length = len(nums) if length == 1: return True end = length - 1 for i in reversed(range(length - 1)): if i + nums[i] >= end: end = i if end == 0: return True else: return False
方法三:O(N)
class Solution: def canJump(self, nums: List[int]) -> bool: reach = 0 n = len(nums) for i in range(n): if i > reach or reach > n : break if i + nums[i] > reach: reach = i + nums[i] return reach >= n - 1