Leetcode55:跳跃游戏——贪心
目录
题目
https://leetcode-cn.com/problems/jump-game/
题解
所谓贪心算法，我个人浅薄的理解就是每一步找局部最优解，最终找到整体最优解。
那么这道题可以有这样的思路：从前往后遍历nums的元素，实时维护最远可以到达的位置 far。
对于当前遍历的位置i，先判断i<=far，再有far = max(far, i+nums[i])
直到far>=len(nums)，则返回True，否则返回False。
代码：
class Solution:
def canJump(self, nums: List[int]) -> bool:
far = nums[0]
size = len(nums)
for i in range(size):
if i > far:
return False
far = max(far, nums[i]+i)
if far >= size-1:
return True
return False
ps:因为前面做了几题递归，所以本来想用递归做，尝试一下代码不太会写，但我觉得思路上应该是行得通的。看来我的技术还有很大的提升空间呀！