leetcode hot 100 跳跃游戏2
45. 跳跃游戏 II
已解答
中等
相关标签
相关企业
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_t = 1
count=0
queue = [0]
queue_next=[]
while max_t<len(nums):
for tmp in queue:
if tmp + nums[tmp]+1>max_t:
end = min(len(nums),tmp+nums[tmp]+1)
for i in range(max_t,end):
queue_next.append(i)
max_t = end
count+=1
queue = queue_next
queue_next=[]保存一个队列，是上一次能到达的最远距离