55. Jump Game
55. Jump Game
问能不能跳到最后，可以maxIndex记录能跳到的最远位置，如果maxIndex<i，返回False，如果maxIndex>=len(nums)-1，返回True。
时间复杂度：O(n)
代码如下
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
maxIndex = 0
for i in range(len(nums)):
if i > maxIndex:
return False
if i + nums[i] > maxIndex:
maxIndex = i + nums[i]
if maxIndex >= len(nums) - 1:
return True
return True
45. Jump Game II
45. Jump Game II
进阶版，问最少几步可以跳到最后，可以maxIndex记录能跳到的最远位置，lastIndex记录目前能到的最远位置，如果lastIndex<i，step++。
时间复杂度：O(n)
代码如下
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
maxIndex = lastIndex = step = 0
for i in range(len(nums)):
if i > lastIndex:
step += 1
lastIndex = maxIndex
maxIndex = max(maxIndex, i + nums[i])
return step
