← 返回编程题库
coding-jump-game-min-jumps中等免费版2000ms未尝试

跳跃游戏 II — 到达终点的最少跳数

Jump Game II — Minimum Jumps to Reach Last Index

开始编码

某组合管理团队要规划「调仓节奏」:日历上一共 n 个交易日(tick),第 i 个交易日的风控预算允许把下一次调仓**至多推迟 nums[i] 天**。从第 0 天出发、必须在第 n − 1 天前把账户清空——每次调仓都要付一笔固定的交易成本,所以调仓次数才是要优化的目标,不在乎单次调仓跨越多少天。请算出从第 0 天走到第 n − 1 天所需的最少调仓次数;若约束让你卡在某天走不下去(即所有可达的前驱都没法把可达边界推过 n − 1),返回 −1

请实现 solution(nums: list[int]) -> int。函数返回从下标 0 到下标 n − 1 的最少跳数,若不可达则返回 −1。约定:(a)n == 1 时返回 0(起点即终点);(b)从下标 i 一跳可落到 [i + 1, i + nums[i]] 内的任意下标(被数组边界截断);(c)若 n ≥ 2nums[0] == 0,根本无法跨出第 0 步,返回 −1;(d)相同步数的方案不必区分先后,函数只返回数量。

示例solution([2, 3, 1, 1, 4]) 返回 2(从下标 0 走 1 步到下标 1,再从下标 1 走 3 步到下标 4——共 2 跳;如果从下标 0 直接走 2 步到下标 2,就会被困住,因为 nums[2] = 1 只能再走一步,结果反而是 3 跳)。solution([0]) 返回 0,因为唯一的元素就是终点,无需跳跃。solution([3, 2, 1, 0, 4]) 返回 −1:从下标 0 可达 {1, 2, 3},但下标 3 的 nums[3] = 0 哪儿也去不了,下标 1、2 也接不到下标 4,所以终点不可达。

朴素的 O(N²) DP——dp[j] = min{dp[i] + 1 : i < j 且 i + nums[i] >= j}——可以做对,但会做无用功:BFS 隐含的每一层都是连续区间,根本不必为每个目标下标各自枚举前驱。贪心 O(N) 扫描只维护当前层的右端点 current_end 和层内的最远可达 farthest,扫到 current_end 时再把层往前推一格——这等价于 BFS,但只用 O(1) 额外空间。这种「按层 BFS 折叠成一遍标量更新」的套路在很多带步数计数的区间问题上都很顺手——调仓节奏规划、容忍间隙的排程、广播半径覆盖——任何朴素逐点 DP 会重复劳动的场景。

约束条件

  • 1 ≤ len(nums) ≤ 10^4
  • 0 ≤ nums[i] ≤ 1000
  • `nums[i]` 表示从下标 `i` 出发的最大步长(实际可走任意 `[0, nums[i]]` 步)
  • 起点固定为下标 0,终点固定为最后一个下标 `n − 1`
  • 返回到达终点所需的最少跳数;若无法到达,返回 `−1`
  • 当 `n == 1` 时直接返回 `0`(起点即终点,无需跳跃)
  • 当 `n ≥ 2` 且 `nums[0] == 0` 时返回 `−1`(从下标 0 根本走不出)

样例

Case 1 · classic LC45 example one

输入: [[2,3,1,1,4]]

期望: 2

经典 LeetCode 45 例 1。最短路径:从下标 0(值 2)跳到下标 1(值 3),再从下标 1 直接跳到末端下标 4。共 2 跳。注意虽然下标 0 也能直接跳到下标 2,但那条路在下标 2 处只能再走一步,反而拖到 3 跳。

Case 2 · classic LC45 example two with internal zero

输入: [[2,3,0,1,4]]

期望: 2

LeetCode 45 例 2。下标 2 处值为 0 是陷阱——必须从下标 1 直接越过它。最优:0 → 1 → 4,共 2 跳。

Case 3 · single element already at target

输入: [[0]]

期望: 0

唯一元素就是终点,无需任何跳跃,返回 0。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · classic LC45 example one

输入: [[2,3,1,1,4]]

期望: 2

经典 LeetCode 45 例 1。最短路径:从下标 0(值 2)跳到下标 1(值 3),再从下标 1 直接跳到末端下标 4。共 2 跳。注意虽然下标 0 也能直接跳到下标 2,但那条路在下标 2 处只能再走一步,反而拖到 3 跳。

Case 2 · classic LC45 example two with internal zero

输入: [[2,3,0,1,4]]

期望: 2

LeetCode 45 例 2。下标 2 处值为 0 是陷阱——必须从下标 1 直接越过它。最优:0 → 1 → 4,共 2 跳。

Case 3 · single element already at target

输入: [[0]]

期望: 0

唯一元素就是终点,无需任何跳跃,返回 0。