LeetCode 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]。

示例 1:

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

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 跳跃游戏II（LeetCode 45）：https://leetcode.cn/problems/jump-game-ii/
class Solution {
    public int jump(int[] nums) {
        // 当前的位置，索引
        int nowPos = 0 ;

        // 最小的跳跃次数
        int step = 0;

        // nowPos 不断的调整位置
        // 由于题目明确说明可以达到最后一个位置
        // 因此，当 nowPos 超过或者等于 nums.length - 1 时
        // 即跳出 while 循环，也就得到结果了
        while( nowPos < nums.length - 1){
            
            // nowPos 对应的元素 nums[nowPos] 表示可以向后跳转的最大距离
            // nowPos + nums[nowPos] 表示从 nowPos 跳跃一次，可以来到的最远的一个位置
            // 这个位置也就是选择跳跃时的一个右边界
            // 但不一定会选择跳到 nowPos + nums[nowPos] 这个位置
            int right = nowPos + nums[nowPos];

            // 除非发现 right 可以到达末尾位置或者超过末尾位置
            // 那么只需要在原来的 step 基础上跳跃一次即得到答案
            if( right >= nums.length - 1) return step + 1;

            // 否则就需要开始考虑下一次跳跃应该跳到 [ nowPos + 1 , right ] 之间的哪个位置
            // 而选择的依据就是在上述区间选择的位置点，可以使得它的最大距离是所有选择中最大的
            
            // 于是初始化两个变量

            // nextRight 表示来到下一个跳跃点后，它的最大距离
            int nextRight = right ;

            // nextPos 表示下一个跳跃点的位置
            int nextPos = nowPos;

            // 访问  [ nowPos + 1 , right ] 之间的元素
            for ( int i = nowPos + 1 ; i <= right ; i++){

                // 不断更新最大距离
                if( i + nums[i] > nextRight){
                    
                    // 不断更新最大距离
                    nextRight = i + nums[i];
                    // 不断更新跳跃点的位置
                    nextPos = i;

                }
            }

            // 跳出循环后，nextPos 就是跳跃的新位置
            // nowPos 来到 nextPos 的位置
            nowPos = nextPos;

            // 完成一次跳跃，setp 进行更新
            step++;
        }

        // 返回结果
        return step;

    }
}

2、 C++ 代码

class Solution {
public:
    int jump(vector<int>& nums) {
        // 当前的位置，索引
        int nowPos = 0 ;

        // 最小的跳跃次数
        int step = 0;

        // nowPos 不断的调整位置
        // 由于题目明确说明可以达到最后一个位置
        // 因此，当 nowPos 超过或者等于 nums.length - 1 时
        // 即跳出 while 循环，也就得到结果了
        while( nowPos < nums.size() - 1){
            
            // nowPos 对应的元素 nums[nowPos] 表示可以向后跳转的最大距离
            // nowPos + nums[nowPos] 表示从 nowPos 跳跃一次，可以来到的最远的一个位置
            // 这个位置也就是选择跳跃时的一个右边界
            // 但不一定会选择跳到 nowPos + nums[nowPos] 这个位置
            int right = nowPos + nums[nowPos];

            // 除非发现 right 可以到达末尾位置或者超过末尾位置
            // 那么只需要在原来的 step 基础上跳跃一次即得到答案
            if( right >= nums.size() - 1) return step + 1;

            // 否则就需要开始考虑下一次跳跃应该跳到 [ nowPos + 1 , right ] 之间的哪个位置
            // 而选择的依据就是在上述区间选择的位置点，可以使得它的最大距离是所有选择中最大的
            
            // 于是初始化两个变量

            // nextRight 表示来到下一个跳跃点后，它的最大距离
            int nextRight = right ;

            // nextPos 表示下一个跳跃点的位置
            int nextPos = nowPos;

            // 访问  [ nowPos + 1 , right ] 之间的元素
            for ( int i = nowPos + 1 ; i <= right ; i++){

                // 不断更新最大距离
                if( i + nums[i] > nextRight){
                    
                    // 不断更新最大距离
                    nextRight = i + nums[i];
                    // 不断更新跳跃点的位置
                    nextPos = i;

                }
            }

            // 跳出循环后，nextPos 就是跳跃的新位置
            // nowPos 来到 nextPos 的位置
            nowPos = nextPos;

            // 完成一次跳跃，setp 进行更新
            step++;
        }

        // 返回结果
        return step;

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 添加微信 278166530 获取最新课程
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 跳跃游戏II（LeetCode 45）：https://leetcode.cn/problems/jump-game-ii/
class Solution:
    def jump(self, nums: List[int]) -> int:
        # 当前的位置，索引
        nowPos = 0 

        # 最小的跳跃次数
        step = 0

        # nowPos 不断的调整位置
        # 由于题目明确说明可以达到最后一个位置
        # 因此，当 nowPos 超过或者等于 nums.length - 1 时
        # 即跳出 while 循环，也就得到结果了
        while nowPos < len(nums) - 1 :
            
            # nowPos 对应的元素 nums[nowPos] 表示可以向后跳转的最大距离
            # nowPos + nums[nowPos] 表示从 nowPos 跳跃一次，可以来到的最远的一个位置
            # 这个位置也就是选择跳跃时的一个右边界
            # 但不一定会选择跳到 nowPos + nums[nowPos] 这个位置
            right = nowPos + nums[nowPos]

            # 除非发现 right 可以到达末尾位置或者超过末尾位置
            # 那么只需要在原来的 step 基础上跳跃一次即得到答案
            if right >=len(nums) - 1 : return step + 1

            # 否则就需要开始考虑下一次跳跃应该跳到 [ nowPos + 1 , right ] 之间的哪个位置
            # 而选择的依据就是在上述区间选择的位置点，可以使得它的最大距离是所有选择中最大的
            
            # 于是初始化两个变量

            # nextRight 表示来到下一个跳跃点后，它的最大距离
            nextRight = right 

            # nextPos 表示下一个跳跃点的位置
            nextPos = nowPos

            # 访问  [ nowPos + 1 , right ] 之间的元素
            for  i in range( nowPos + 1 , right + 1) : 

                # 不断更新最大距离
                if i + nums[i] > nextRight : 
                    
                    # 不断更新最大距离
                    nextRight = i + nums[i]
                    # 不断更新跳跃点的位置
                    nextPos = i

         

            # 跳出循环后，nextPos 就是跳跃的新位置
            # nowPos 来到 nextPos 的位置
            nowPos = nextPos

            # 完成一次跳跃，setp 进行更新
            step += 1
        

        # 返回结果
        return step