题目链接
https://leetcode.com/problems/jump-game/
题目描述
给定非负整数数组nums,你最初位于数组的第一个下标。数组中的每个元素表示你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。如果能,返回true,否则返回false。
示例
输入:[2,3,1,1,4]
输出:true
可以先跳一步,从位置0到达位置1,然后从位置1跳3步到达最后一个位置。
解题思路
这道题目可以理解为“按照给定的规则跳跃,最远可以到达哪里”。如果最远可以到达的位置越过了数组的最后一个位置,那么数组的最后一个位置自然是可以达到的。nums[i]为从位置i可以跳跃的最大长度,因此如果位置i可以到达,那么i+1,.....,i+nums[i]都可以到达。
这道题可以由贪心来解,贪心的策略为“找尽可能到达最远的位置”。在遍历数组时,我们维护一个变量t表示“从起点开始跳跃,最远可以到达的位置”。那么对于当前遍历到的位置x,如果x<=t,则表示x可以从起点跳跃若干次到达。既然x能够到达, 那么我们就再更新“最远可以到达的位置”t为max(t,x+nums[x])。遍历完后判断最远可以到达的位置是否大于等于最后一个位置。如果是,则表示最后一个位置可达,返回True;否则返回False。
Python实现
我们设定位置和索引一致,即数组各个元素的位置范围为0,...,len(nums)-1。
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
n = len(nums)
for i in range(n):
if(farthest >= i): #i可以达到
farthest = max(i+nums[i],farthest)#更新farthest
return farthest >= n-1
扩展
【leetcode-Python】-动态规划&贪心-45. Jump Game II