leetcode hot 100 跳跃游戏
55. 跳跃游戏
已解答
中等
相关标签
相关企业
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
flag = [False]*(len(nums)-1)
flag = [True] + flag
max_t = 0
for index, i in enumerate(nums):
if flag[index] == True and index+nums[index]+1>max_t:
end = min(len(nums),index+nums[index]+1)
for x in range(max_t,end):
flag[x] = True
max_t = index+nums[index]+1
else:
continue
return flag[-1]这里实际上很简单，就是遍历一遍，然后把能够到达的地方设为true，然后对于能到的地方再看他能到的最远。
更简单的方法是意识到，到达的最远其实就行了，因为他是一步步跳的，所以最远的前面所有各自都能跳。