欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode 45. 跳跃游戏 II | Python

程序员文章站 2022-06-27 20:38:51
45. 跳跃游戏 II 题目来源: "https://leetcode cn.com/problems/jump game ii" 题目 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例 ......

45. 跳跃游戏 ii


题目来源:

题目


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

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

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

示例:

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

说明:

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

解题思路


思路:贪婪算法

首先,先注意题意的说明部分【假设你总是可以到达数组的最后一个位置】。这里只需要考虑,题目中所给出的数组,是一定能够到达数组的最后一个位置。

这题要求与之前 并不相同,55 题要求的返回是否能够到达最后一个位置。如果用 55 题的反例来论证本题意义不大,若觉得有必要,也可以在无法到达时返回特定的值用以标记,例如 0。

现在考虑如何去求得到达最后位置的最小跳跃次数?

在这里,我们考虑使用正向去找可到达的最远位置。这里以示例 1 为例,[2,3,1,1,4],索引为 0 的位置,这里元素值为 2,表示该位置能够跳跃到达的位置为后续两个位置,如下图所示红色部分:

LeetCode 45. 跳跃游戏 II | Python

在这里,索引为 1 的位置中,元素值值为 3,表示能够后续三个位置,能到达最远的位置为索引 4,这里已经到达末尾位置。而索引 2 的位置中,值为 1,这里只能跳跃到索引为 3 的位置。这里显然从索引 1 的位置跳跃能到达更远的位置。

假设数组后续还未到达末尾,,现在选择先跳到索引 1 的位置,上面说能够在该位置能跳跃到后续三个位置,这里如何选择落脚的地方?跟上面讨论的一样,在每个可到达的位置,判断各自能够跳跃的最远的位置。

现在位置在索引 1 的位置上面,如下图所示,3 个红色部分就是索引 1 这个位置能够跳跃的选择,而跳到索引 4 的位置,能够跳跃更远的位置,所以此处是当前最好的落脚点。

LeetCode 45. 跳跃游戏 II | Python

现在考虑如何实现?我们可以维护这个可到达的最远位置,作为边界。当我们正向遍历的时候,当到达边界时,就更新这个边界,相应的跳跃次数加 1。

这里需要注意一点,我们从正向遍历的时候,不用遍历最后一个位置。根据上面的说明知道,这里一定会到达最后一个位置。那么前面所述的需要维护的这个边界,一定是大于或等于最后那个位置的。如果边界刚好就在最后的位置时,按照前所述的到达边界时,更新边界,跳跃次数加 1 的逻辑,这里会增加不必要的跳跃次数。所以不考虑访问这个最后的位置。

具体的代码实现如下。

代码实现


class solution:
    def jump(self, nums: list[int]) -> int:
        # 定义最远位置,边界,步数
        max_pos = 0
        end = 0
        steps = 0
        for i in range(len(nums) - 1):
            # 获取最远可到达位置
            max_pos = max(max_pos, i + nums[i])
            # 到达边界时,更新边界
            # 同时跳跃次数加 1
            if i == end:
                end = max_pos
                steps += 1
        
        return steps

实现结果


LeetCode 45. 跳跃游戏 II | Python


以上就是使用贪心算法,从数组开始正向遍历,维护可跳跃最远的位置,确定边界,到达边界时,更新边界,增加跳跃次数,进而解决《45. 跳跃游戏 ii》问题的主要内容。


欢迎关注微信公众号《书所集录》