跳跃游戏2

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
  从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jump-game-ii

解题思路,按照位置依次跳,按照贪心的原则,每次存储该段的最大值,我们可以把这个列表中的值看成一段一段的,比如第一个数为2,则以这是为起始点后面的两个数都属于这个段,每过一个段则相加一次step,在每一段中比较最大距离max_bound,将最大距离存储在max_bound中,依次与i+num[i]作比较。这里所存储的最大值,也可以理解为最优的一次路径。

class Solution:
    def jump(self, nums: List[int]) -> int:
        step=0
        end=0
        max_bound=0
        for i in range(len(nums)-1):
            max_bound=max(max_bound,nums[i]+i)
            if(i==end):
                step+=1
                end=max_bound
        return step
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00