45.跳跃游戏II

LeetCode LeetCode 数组 贪心 动态规划
发布时间 :
字数:2.7k 阅读 : 评论:
  1. 45.跳跃游戏II
    1. 45.1 题目
    2. 45.2 题解
      1. 贪心算法
      2. 动态规划
    3. 45.3 代码
    4. 45.4 运行结果

45.跳跃游戏II

45.1 题目

给定一个长度为 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
  • 题目保证可以到达 nums[n-1]

45.2 题解

贪心算法

// 方法一：贪心算法
// 每个阶段会产生一次跳跃
// 遍历数组元素，更新当前遍历过的位置能够到达的最远位置
// 如果当前遍历到的位置是上一阶段能够到达的最远位置，说明当前阶段结束，进行跳跃并更新成当前阶段能够到达的最远位置
static int Jump1(int[] nums)
{
    int jumpCount = 0; // 记录跳跃次数
    int currentFarthest = 0; // 当前阶段能够到达的最远位置 或者说是当前切断索引边界 当前阶段的索引无论如何都要从小于等于这个索引边界汇总取了
    int farthest = 0; // 当前遍历过的位置能够到达的最远位置

    // 遍历数组，因为最后一个元素已经是终点，不需要跳跃，所以遍历的范围是数组的长度减去1。
    for (int i = 0; i < nums.Length - 1; i++)
    {
        // i + nums[i] 代表当前索引能到达的最远位置
        farthest = Math.Max(farthest, i + nums[i]); // 更新当前能够到达的最远位置 

        // 如果当前遍历到的位置是当前能够到达的最远位置
        if (i == currentFarthest)
        {
            jumpCount++; // 进行一次跳跃
            currentFarthest = farthest; // 更新下一次能够到达的最远位置

            // 如果当前能够到达的最远位置已经超过或等于终点位置
            if (currentFarthest >= nums.Length - 1)
            {
                break; // 跳出循环，无需继续跳跃
            }
        }
    }

    return jumpCount; // 返回最小跳跃次数
}

动态规划

// 方法二：动态规划
// 创建一个数组用于存储到达每个位置的最小跳跃次数，除了首元素，初始化为一个较大的值
// 遍历跳跃数组，再遍历当前元素能够跳跃的范围的元素，更新他们的最小跳跃次数
static int Jump2(int[] nums)
{
    int[] dp = new int[nums.Length]; // 创建一个数组用于存储到达每个位置的最小跳跃次数
    for (int i = 1; i < nums.Length; i++)
    {
        dp[i] = int.MaxValue; // 除了首元素，初始化为一个较大的值
    }

    // 遍历跳跃数组，currentPos 为当前要动态规划的元素
    for (int currentPos = 0; currentPos < nums.Length - 1; currentPos++)
    {
        // 在当前位置，遍历能够跳跃的范围，更新能够到达的位置的最小跳跃次数
        for (int jumpLength = 1;
                jumpLength <= nums[currentPos] && currentPos + jumpLength < nums.Length;
                jumpLength++)
        {
            // 能够跳跃的元素中，最小跳跃次数是 之前的最小跳跃次数 和 当前元素最小跳跃次数 + 1（当前元素跳一次） 的最小值
            dp[currentPos + jumpLength] = Math.Min(dp[currentPos + jumpLength], dp[currentPos] + 1);
        }
    }

    return dp[nums.Length - 1]; // 返回到达数组末尾的最小跳跃次数
}

// 初始状态：
// nums = [2, 3, 1, 1, 4]
// dp = [0, ∞, ∞, ∞, ∞] （除了首元素，其他位置初始化为 int.MaxValue）


// 外层循环 - i = 0：

// 内层循环：

// j = 1:
// 更新 dp[0 + 1]:
// dp[1] = Math.Min(dp[1], dp[0] + 1) = Math.Min(∞, 0 + 1) = 1
// dp = [0, 1, ∞, ∞, ∞]

// j = 2:
// 更新 dp[0 + 2]:
// dp[2] = Math.Min(dp[2], dp[0] + 1) = Math.Min(∞, 0 + 1) = 1
// dp = [0, 1, 1, ∞, ∞]


// 外层循环 - i = 1：

// 内层循环：

// j = 1:
// 更新 dp[1 + 1]:
// dp[2] = Math.Min(dp[2], dp[1] + 1) = Math.Min(1, 1 + 1) = 1（保持不变）
// dp = [0, 1, 1, ∞, ∞]

// j = 2:
// 更新 dp[1 + 2]:
// dp[3] = Math.Min(dp[3], dp[1] + 1) = Math.Min(∞, 1 + 1) = 2
// dp = [0, 1, 1, 2, ∞]

// j = 3:
// 更新 dp[1 + 3]:
// dp[4] = Math.Min(dp[4], dp[1] + 1) = Math.Min(∞, 1 + 1) = 2
// dp = [0, 1, 1, 2, 2]


// 外层循环 - i = 2：

// 内层循环：

// j = 1:
// 更新 dp[2 + 1]:
// dp[3] = Math.Min(dp[3], dp[2] + 1) = Math.Min(2, 1 + 1) = 2（保持不变）
// dp = [0, 1, 1, 2, 2]


// 外层循环 - i = 3：

// 内层循环：

// j = 1:
// 更新 dp[3 + 1]:
// dp[4] = Math.Min(dp[4], dp[3] + 1) = Math.Min(2, 2 + 1) = 2（保持不变）
// dp = [0, 1, 1, 2, 2]
// 外层循环 - i = 4：
// 因为 i 已经是倒数第二个元素，不需要进一步处理。


// 最终结果：
// 返回 dp[nums.Length - 1] = dp[4] = 2
// 解释：根据动态规划数组 dp 的计算过程，可以看出，从起点到达末尾最少需要2次跳跃：


// 从索引 0 跳到索引 1 或 2。
// 从索引 1 或 2 再跳到索引 4。
// 因此，Jump2([2, 3, 1, 1, 4]) 的返回值是 2。

45.3 代码

using System;
using System.Collections.Generic;

class JumpGame
{
    static void Main()
    {
        #region 题目

        // 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
        // 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。
        // 返回到达 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 <= 104
        // 0 <= nums[i] <= 1000
        // 题目保证可以到达 nums[n-1]

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 2, 3, 1, 1, 4 };
        int result1_1 = Jump1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = Jump2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 2, 3, 0, 1, 4 };
        int result2_1 = Jump1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = Jump2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：贪心算法
    // 每个阶段会产生一次跳跃
    // 遍历数组元素，更新当前遍历过的位置能够到达的最远位置
    // 如果当前遍历到的位置是上一阶段能够到达的最远位置，说明当前阶段结束，进行跳跃并更新成当前阶段能够到达的最远位置
    static int Jump1(int[] nums)
    {
        int jumpCount = 0; // 记录跳跃次数
        int currentFarthest = 0; // 当前阶段能够到达的最远位置 或者说是当前切断索引边界 当前阶段的索引无论如何都要从小于等于这个索引边界汇总取了
        int farthest = 0; // 当前遍历过的位置能够到达的最远位置

        // 遍历数组，因为最后一个元素已经是终点，不需要跳跃，所以遍历的范围是数组的长度减去1。
        for (int i = 0; i < nums.Length - 1; i++)
        {
            // i + nums[i] 代表当前索引能到达的最远位置
            farthest = Math.Max(farthest, i + nums[i]); // 更新当前能够到达的最远位置 

            // 如果当前遍历到的位置是当前能够到达的最远位置
            if (i == currentFarthest)
            {
                jumpCount++; // 进行一次跳跃
                currentFarthest = farthest; // 更新下一次能够到达的最远位置

                // 如果当前能够到达的最远位置已经超过或等于终点位置
                if (currentFarthest >= nums.Length - 1)
                {
                    break; // 跳出循环，无需继续跳跃
                }
            }
        }

        return jumpCount; // 返回最小跳跃次数
    }


    // 方法二：动态规划
    // 创建一个数组用于存储到达每个位置的最小跳跃次数，除了首元素，初始化为一个较大的值
    // 遍历跳跃数组，再遍历当前元素能够跳跃的范围的元素，更新他们的最小跳跃次数
    static int Jump2(int[] nums)
    {
        int[] dp = new int[nums.Length]; // 创建一个数组用于存储到达每个位置的最小跳跃次数
        for (int i = 1; i < nums.Length; i++)
        {
            dp[i] = int.MaxValue; // 除了首元素，初始化为一个较大的值
        }

        // 遍历跳跃数组，currentPos 为当前要动态规划的元素
        for (int currentPos = 0; currentPos < nums.Length - 1; currentPos++)
        {
            // 在当前位置，遍历能够跳跃的范围，更新能够到达的位置的最小跳跃次数
            for (int jumpLength = 1;
                 jumpLength <= nums[currentPos] && currentPos + jumpLength < nums.Length;
                 jumpLength++)
            {
                // 能够跳跃的元素中，最小跳跃次数是 之前的最小跳跃次数 和 当前元素最小跳跃次数 + 1（当前元素跳一次） 的最小值
                dp[currentPos + jumpLength] = Math.Min(dp[currentPos + jumpLength], dp[currentPos] + 1);
            }
        }

        return dp[nums.Length - 1]; // 返回到达数组末尾的最小跳跃次数
    }

    // 初始状态：
    // nums = [2, 3, 1, 1, 4]
    // dp = [0, ∞, ∞, ∞, ∞] （除了首元素，其他位置初始化为 int.MaxValue）


    // 外层循环 - i = 0：

    // 内层循环：

    // j = 1:
    // 更新 dp[0 + 1]:
    // dp[1] = Math.Min(dp[1], dp[0] + 1) = Math.Min(∞, 0 + 1) = 1
    // dp = [0, 1, ∞, ∞, ∞]

    // j = 2:
    // 更新 dp[0 + 2]:
    // dp[2] = Math.Min(dp[2], dp[0] + 1) = Math.Min(∞, 0 + 1) = 1
    // dp = [0, 1, 1, ∞, ∞]


    // 外层循环 - i = 1：

    // 内层循环：

    // j = 1:
    // 更新 dp[1 + 1]:
    // dp[2] = Math.Min(dp[2], dp[1] + 1) = Math.Min(1, 1 + 1) = 1（保持不变）
    // dp = [0, 1, 1, ∞, ∞]

    // j = 2:
    // 更新 dp[1 + 2]:
    // dp[3] = Math.Min(dp[3], dp[1] + 1) = Math.Min(∞, 1 + 1) = 2
    // dp = [0, 1, 1, 2, ∞]

    // j = 3:
    // 更新 dp[1 + 3]:
    // dp[4] = Math.Min(dp[4], dp[1] + 1) = Math.Min(∞, 1 + 1) = 2
    // dp = [0, 1, 1, 2, 2]


    // 外层循环 - i = 2：

    // 内层循环：

    // j = 1:
    // 更新 dp[2 + 1]:
    // dp[3] = Math.Min(dp[3], dp[2] + 1) = Math.Min(2, 1 + 1) = 2（保持不变）
    // dp = [0, 1, 1, 2, 2]


    // 外层循环 - i = 3：

    // 内层循环：

    // j = 1:
    // 更新 dp[3 + 1]:
    // dp[4] = Math.Min(dp[4], dp[3] + 1) = Math.Min(2, 2 + 1) = 2（保持不变）
    // dp = [0, 1, 1, 2, 2]
    // 外层循环 - i = 4：
    // 因为 i 已经是倒数第二个元素，不需要进一步处理。


    // 最终结果：
    // 返回 dp[nums.Length - 1] = dp[4] = 2
    // 解释：根据动态规划数组 dp 的计算过程，可以看出，从起点到达末尾最少需要2次跳跃：


    // 从索引 0 跳到索引 1 或 2。
    // 从索引 1 或 2 再跳到索引 4。
    // 因此，Jump2([2, 3, 1, 1, 4]) 的返回值是 2。


    #endregion
}

45.4 运行结果

示例1 方法1 输出：2
示例1 方法2 输出：2
示例2 方法1 输出：2
示例2 方法2 输出：2
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏