0045. 跳跃游戏 II

0045. 跳跃游戏 II #

  • 标签:贪心、数组、动态规划
  • 难度:中等

题目大意 #

给定一个非负整数数组 nums,数组中每个元素代表在该位置可以跳跃的最大长度。

开始位置为数组的第一个下标处,目的是用最少的跳跃次数到达最后一个下标处。

假设你总能到达数组的最后一个下标处。

解题思路 #

第 i 个位置所能跳到的位置为 [i + 1, i + nums[i]],第 0 个位置所能跳到的位置就是 [0 + 1, 0 + nums[0]],即 [1, nums[0]],第 1 个位置所能跳到的位置就是 [1 + 1, 1 + nums[1]],即 [2, 1 + nums[1]] ,等等。

对于每一个位置 i 来说,所能跳到的所有位置都可以作为下一个起跳点,为了尽可能使用最少的跳跃次数,所以我们应该使得下一次起跳所能达到的位置尽可能的远。简单来说,就是每次在「可跳范围」内选择可以使下一次跳的更远的位置。

在实现中,我们维护当前所能达到的最远位置 end,下一步所能跳到的最远位置 max_pos,最少跳跃次数 setps。

  • 遍历 nums 的前 len(nums) - 1 个元素,更新 end 位置上下一步所能跳到的最远位置 max_pos。
    • max_pos 为 [i + 1, i + nums[i]] 范围内,所能跳到最远位置。
  • 如果索引 i 到达了 end 边界,则:
    • 更新 end 为新的当前位置,并令步数 setps + 1。
  • 最终返回跳跃次数 steps。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def jump(self, nums: List[int]) -> int:
        end, max_pos = 0, 0
        steps = 0
        for i in range(len(nums) - 1):
            max_pos = max(max_pos, nums[i] + i)
            if i == end:
                end = max_pos
                steps += 1
        return steps
本站总访问量  次  |  您是本站第  位访问者