难度: Medium
原题连接
内容描述
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
我们可以用一个辅助函数helper(idx)，其返回值是我们是否能够到达index为idx的位置
递归, 超时
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
def helper(idx):
if idx == 0:
return True
for i in range(idx):
if nums[i] >= idx - i:
if helper(i):
return True
return False
return helper(len(nums)-1)
思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
仔细一想，我们会发现只有一个点的最大跳跃距离nums[i] == 0且我们不能跳得比这个点更远的时候，我们才无法到达最后
beats 100%
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums or len(nums) <= 1:
return True
for i in range(len(nums)-2, -1, -1):
if nums[i] == 0:
possible = False
for j in range(0, i):
if nums[j] + j > i:
possible = True
break
if not possible:
return False
return True思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******
我们可以从头到尾遍历，始终维护一个当前能跳的最大长度max_jump，
- 一旦max_jump小于等于0了，说明我们无法走的更远了，立刻返回False
- 一旦max_jump+当前index >= last index了，立刻返回True
beats 70.35%
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if not nums or len(nums) <= 1:
return True
max_jump = 0
for i in range(len(nums)):
max_jump = max(max_jump-1, nums[i])
if max_jump + i >= len(nums) - 1:
return True
if max_jump <= 0:
return False