Leetcode 跳跃游戏 二

核心任务是找出从数组的起点跳到终点所需的最小跳跃次数。

这段代码解决的是“跳跃游戏 II”（Leetcode第45题），其核心任务是找出从数组的起点跳到终点所需的最小跳跃次数。

class Solution {
    public int jump(int[] nums) {
        //首先处理特殊情况
        if(nums.length <= 1) return 0;
        int maxReach = 0; //从起点开始所能达到的最远位置，它是随着遍历数组不断更新的
        int currentEnd = 0; //最近一次跳跃后，当前能够到达的最远末端位置。
        int jumpCount = 0; //跳跃次数
        for(int i = 0; i < nums.length; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if(i == currentEnd) {
                jumpCount++;
                currentEnd = maxReach;
            }
            if(currentEnd >= nums.length - 1) {
                break;//跳出循环，不需要再统计跳跃次数了，因为可以到达末尾元素。
            }
        }
        return jumpCount;
    }
}

算法思想

这个算法的核心是 贪心算法（Greedy Algorithm）。其思想是：每次选择当前能够跳跃的范围内最远的点来进行跳跃，从而保证用最少的跳跃次数到达数组的末尾。

代码讲解

1. 特殊情况处理：

   if (nums.length <= 1) {
       return 0; // 如果数组长度为1或更短，不需要跳跃，直接返回0。
   }
   

   这里是为了处理数组长度为1的情况，如果起点就是终点，自然不需要任何跳跃。

2. 定义变量：

   int jumps = 0; // 记录跳跃的次数
   int currentEnd = 0; // 当前这一次跳跃能够到达的最远位置
   int farthest = 0; // 从当前跳跃范围内能够到达的最远位置
   

   • jumps：记录跳跃的次数。
   • currentEnd：当前跳跃范围的终点，即在这一跳内能够到达的最远位置。
   • farthest：遍历当前范围内的点时，记录从这些点能够跳跃到的最远位置。

3. 遍历数组：

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

   • 对于数组中的每一个位置 i，计算从该位置能够跳跃到的最远位置，即 i + nums[i]。farthest 保存了当前范围内可以跳到的最远位置。

4. 判断是否需要增加跳跃次数：

   if (i == currentEnd) {
       jumps++; // 增加跳跃次数
       currentEnd = farthest; // 更新当前跳跃范围的终点
   }
   

   • 如果当前的索引 i 达到了 currentEnd，意味着当前这次跳跃的范围已经遍历完了，因此需要增加一次跳跃，并且将 currentEnd 更新为 farthest，即下一次跳跃可以到达的最远位置。

5. 提前结束判断：

   if (currentEnd >= nums.length - 1) {
       break; // 如果当前跳跃范围已经能够覆盖到数组的末尾，直接结束循环
   }
   

   • 如果 currentEnd 已经能够到达或超过数组的最后一个元素，则不需要继续遍历，跳出循环。

复杂度分析

• 时间复杂度：O(n)，因为我们只遍历数组一次，每个元素都会处理一次。
• 空间复杂度：O(1)，算法只用了常数空间来存储跳跃次数、当前范围的终点和最远位置。

总结

该算法每次选择能跳到的最远位置来进行跳跃，确保以最少的跳跃次数到达终点。通过遍历数组，在每一跳的过程中更新能够跳到的最远点，并在到达当前跳跃的边界时增加跳跃次数，直到覆盖整个数组。