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