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 <= 1040 <= nums[i] <= 1000- 题目保证可以到达
n - 1
思路
时间
O(n)空间
O(1)思路
把「可达范围」看成 BFS 的分层:curEnd = 当前这一跳能到的最远处;farthest = 在 [.., curEnd] 里出发能到的最远处。
走到 curEnd 就必须再跳一次(步数 +1),并把边界推进到 farthest。
循环只跑到 n-2
走到终点不用再跳了,这是最常见的 off-by-one。
为什么贪心对
每一跳都尽可能延伸边界,等价于「一层最多覆盖多远」,而层数就是最少跳数 —— 和 BFS 求最短路同理。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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);