文章

[LeetCode] 每日一题 45. 跳跃游戏 II

题目链接

https://leetcode.cn/problems/jump-game-ii

题目描述

给定一个长度为 n0 索引整数数组 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]

解题思路

对于这类最小跳跃次数的问题,通常可以使用 动态规划 来求解。我们可以通过构建一个 dp 数组,其中 dp[i] 表示从起点跳到位置 i 所需的最小跳跃次数。使用这种方式可以确保获得正确的最小跳跃次数,尽管它的时间复杂度是 O(n²),对于大规模的输入数据可能会比较慢

动态规划解法(O(n²)):

  • 初始化

    • 创建一个 dp 数组,dp[i] 表示从起点到达 i 位置所需的最小跳跃次数

    • 初始时,dp[0] 为 0(起点不需要跳跃),其他位置初始化为无穷大(表示无法到达)

  • 更新过程

    • 对于每个位置 i,根据 nums[i] 计算它能跳到的位置范围 [i+1, i+nums[i]],然后更新这些位置的 dp

    • 通过比较当前位置的跳跃次数和跳跃到某个后续位置的跳跃次数来更新最小跳跃次数

  • 结束条件

    • 当遍历到 dp[n-1] 时,就找到了从起点到终点的最小跳跃次数

这个动态规划解法的时间复杂度是 O(n²),适合用来解决这一类问题,但在处理较大规模输入时可能会遇到性能瓶颈

贪心算法解法(O(n)):

不过,针对这道题,实际上我们可以通过 贪心算法 来优化解法,将复杂度降低到 O(n)。贪心算法的核心思想是:每次跳跃时尽可能选择能够跳得最远的点。我们通过一次遍历,动态更新当前跳跃的最远位置来确保能够以最少的步数到达终点

  1. 初始化

    • index:当前跳跃的位置,最初为 0

    • ans:跳跃次数,初始为 0

    • canJump:记录当前跳跃范围的最远位置,最初为 nums[0]

  2. 遍历过程

    • 每次遍历时,尝试从当前位置 indexcanJump 范围内的所有索引,更新 canJump 为该范围内能跳到的最远位置(即 i + nums[i]

    • 一旦更新了 canJump,就把 index 设置为 next(即 canJump),并且增加跳跃次数 ans++

    • 继续直到 index 达到或超过目标位置 nums.length - 1

通过这种贪心的方式,我们能够在一次遍历中完成最优解的求解,不需要像动态规划那样进行复杂的嵌套循环

代码实现

class Solution {
    public int jump(int[] nums) {
        int index = 0;
        int ans = 0;
        int canJump = nums[0];
        while (index < nums.length - 1) {
            int next = canJump;
            for (int i = index; i <= next && i < nums.length; i++) {
                canJump = Math.max(canJump, i + nums[i]);
            }
            index = next;
            ans++;
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度:只需要对数组进行单次遍历,因此时间复杂度是 O(N)

  • 空间复杂度:只需要维护常数大小的额外空间,因此空间复杂度是 O(1)

总结

这道题的贪心算法通过每次选择能够跳得最远的点来保证最小跳跃次数,且在一次遍历中就能得出最优解。贪心策略比动态规划的 O(n²) 复杂度要高效得多,适合这类求解最小步数或最优路径问题的场景

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0