HHot 100C++ 图解

45. 跳跃游戏 II

一句话套路BFS 分层视角:走到边界才 +1 步

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说,如果你在索引 i 处,你可以跳转到任意 (i + j) 处:

  • 0 <= j <= nums[i] 且
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 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
  • 题目保证可以到达 n - 1

思路

时间O(n)
空间O(1)

思路

把「可达范围」看成 BFS 的分层:curEnd = 当前这一跳能到的最远处;farthest = 在 [.., curEnd] 里出发能到的最远处。

走到 curEnd 就必须再跳一次(步数 +1),并把边界推进到 farthest。

循环只跑到 n-2

走到终点不用再跳了,这是最常见的 off-by-one。

为什么贪心对

每一跳都尽可能延伸边界,等价于「一层最多覆盖多远」,而层数就是最少跳数 —— 和 BFS 求最短路同理。

图解

2 0 3 1 1 2 1 3 4 4
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/14_greedy.cpp18 行
namespace lc0045 {
class Solution {
 public:
  int jump(vector<int>& nums) {
    const int n = (int)nums.size();
    int steps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < n - 1; ++i) {  // 不处理最后一个元素
      farthest = max(farthest, i + nums[i]);
      if (i == curEnd) {  // 到边界了,必须跳
        ++steps;
        curEnd = farthest;
        if (curEnd >= n - 1) break;
      }
    }
    return steps;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q45_jump_game_ii11 行
lc0045::Solution s;
vector<int> a{2, 3, 1, 1, 4};
CHECK_EQ(s.jump(a), 2);  // 1 -> 4
vector<int> b{2, 3, 0, 1, 4};
CHECK_EQ(s.jump(b), 2);
vector<int> c{1, 2};
CHECK_EQ(s.jump(c), 1);
vector<int> d{0};  // 已在终点
CHECK_EQ(s.jump(d), 0);
vector<int> e{1, 1, 1, 1};  // 每次只能跳 1
CHECK_EQ(s.jump(e), 3);

↑↓ 选择↵ 打开/ 随时唤起