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] + flagmax_t = 0for 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] = Truemax_t = index+nums[index]+1else:continue     return flag[-1]

这里实际上很简单，就是遍历一遍，然后把能够到达的地方设为true，然后对于能到的地方再看他能到的最远。

更简单的方法是意识到，到达的最远其实就行了，因为他是一步步跳的，所以最远的前面所有各自都能跳。