Jupm Game II

45. 跳跃游戏II

算法

核心思想：使用贪心算法模拟跳跃过程，按层次遍历的思想解决问题
- 当前位置的覆盖范围：表示当前跳跃次数能够到达的最远位置
- 下一次跳跃的覆盖范围：表示增加一次跳跃后能够到达的最远位置
关键变量：
- cur：当前处理的位置。
- dist：当前跳跃次数能够到达的最远位置。
- next：下一跳能够到达的最远位置。
跳跃过程：
- 初始化跳跃次数 res = 0，起点为 cur = 0
- 在当前跳跃的范围内（从 cur 到 dist），计算下一跳的最远位置 next
- 当 dist 超过或等于数组最后一个位置时，结束跳跃。
步数增加：
- 每遍历完当前跳跃的范围时，更新到下一跳的最远位置 dist = next，并增加跳跃次数 res

复杂度分析

每个位置最多访问一次，因此时间复杂度为 O(n)
空间复杂度为 O(1)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    int jump(vector<int>& nums)
    {
        int res = 0;       // 跳跃次数
        int cur = 0;       // 当前处理的位置
        int dist = 0;      // 当前跳跃的覆盖范围
        while (dist < nums.size() - 1)
        {
            int next = 0;  // 下一跳的覆盖范围
            // 遍历当前跳跃范围
            while (cur <= dist)
            {
                next = std::max(next, cur + nums[cur]);  // 更新下一跳的最远范围
                ++cur;
            }
            dist = next;   // 更新跳跃范围
            ++res;         // 跳跃次数加一
        }
        return res;
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def jump(self, nums: List[int]) -> int:
      res = 0
      dist, cur = 0, 0
      while dist < len(nums) - 1:
        next_dist = 0
        while cur <= dist:
          next_dist = max(next_dist, cur + nums[cur])
          cur += 1
        dist = next_dist
        res += 1
      return res

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func jump(nums []int) int {
  res := 0
  dist, cur := 0, 0
  for dist < len(nums) - 1 {
    next := 0
    for cur <= dist {
      next = max(next, cur + nums[cur])
      cur += 1
    }
    dist = next
    res += 1
  }
  return res
}