当前位置：首页 > article >正文

LeetCode hot100-79

article 2025/2/1 3:07:59

https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&envId=top-100-liked

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

这题看着官方解法一大坨分析，直接用gpt帮忙写的。能打败99%通过。不过贪心的就是看着简单实际自己写起来似懂非懂。

这道题目属于贪心算法类型。其核心思想是：

每次尽量跳得最远，以减少跳跃次数。
从当前位置开始，选择下一个跳跃的目标是能跳到的最远位置。
通过维护 end 来表示当前跳跃的最远位置，并通过 farthest 来表示我们能到达的最远位置。
每当 end 到达当前跳跃范围的最远位置时，我们增加跳跃次数，并更新跳跃范围的最远位置。

这一部分核心代码的含义是

if (i == end) {
    jumps++;           // 跳跃次数 +1
    end = farthest;    // 更新当前跳跃范围的最远位置
}

我们希望通过最少的跳跃次数从 nums[0] 到达 nums[n-1]。
farthest 记录了当前跳跃能够到达的最远位置。
end 记录了当前跳跃范围的最远位置，即到达此位置后，我们必须增加跳跃次数。
核心逻辑：
farthest：每次我们遍历 nums[i] 时，farthest 会更新为当前可以跳到的最远位置，即 farthest = Math.max(farthest, i + nums[i])。这意味着从当前的 i 位置，我们最多能跳到 i + nums[i] 这个位置。

例如，假设我们处在索引 2，nums[2] = 3，那么我们可以跳到索引 2 + 3 = 5，也就是我们最远能跳到的位置是 5。

end：end 记录了当前跳跃所能到达的最远位置。假设在某次跳跃中，我们通过 farthest 计算得到了一个新的最远位置。如果 i == end，表示我们已经到达了当前跳跃范围的边界，也就是说，我们跳跃到这个位置时，已经不能再继续前进，而是需要再进行一次跳跃。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        
        // 如果数组长度小于等于1，则无需跳跃
        if (n <= 1) {
            return 0;
        }

        int jumps = 0;         // 记录跳跃次数
        int farthest = 0;      // 记录当前能跳到的最远位置
        int end = 0;           // 记录当前跳跃的最远位置

        for (int i = 0; i < n; i++) {
            // 更新最远位置
            farthest = Math.max(farthest, i + nums[i]);

            // 如果到达当前跳跃范围的最远位置，增加跳跃次数，并更新 end 为 farthest
            if (i == end) {
                jumps++;
                end = farthest;
                
                // 如果到达最后一个位置，直接返回跳跃次数
                if (end >= n - 1) {
                    break;
                }
            }
        }

        return jumps;
    
    }
}