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，然后對于能到的地方再看他能到的最遠。

更簡單的方法是意識到，到達的最遠其實就行了，因為他是一步步跳的，所以最遠的前面所有各自都能跳。