← 返回编程题库
coding-jump-game-can-reach简单免费版2000ms未尝试

跳跃游戏 — 能否到达终点

Jump Game — Can You Reach the Last Index

开始编码

在跑「最便宜的调仓节奏」这种重活之前,你想先做一次最低可行性检查:日历上一共 n 个交易日(tick),第 i 个交易日的风控预算允许把下一次调仓**至多推迟 nums[i] 天**。在花算力解「从第 0 天走到第 n − 1 天的最少调仓次数」(LC45 / min-jumps 那道题)之前,先快速判断一个 yes/no:这条日历在当前预算下到底走得通走不通?走不通就直接返回,根本不必启动优化器;走得通才进入下一步去数或规划具体步数。和 min-jumps 同样的输入形状,但代价更小、返回更简单。

请实现 solution(nums: list[int]) -> bool。函数判断能否从下标 0 通过一连串向前的跳跃到达下标 n − 1,可达返回 True、不可达返回 False。每一步从下标 i 可落到 [i + 1, i + nums[i]] 内的任意下标(被数组边界截断)。约定:(a)n == 1 时返回 True(起点即终点);(b)n ≥ 2nums[0] == 0 时返回 False(无法跨出第 0 步);(c)从下标 i 可走任意 [1, nums[i]] 步,不限于走满——只关心是否存在一条合法路径。

示例solution([2, 3, 1, 1, 4]) 返回 True——可行路径很多,如 0 → 1 → 4 或 0 → 2 → 3 → 4。solution([3, 2, 1, 0, 4]) 返回 False——从下标 0 可达 {1, 2, 3},但下标 3 处值为 0(哪儿也去不了),下标 1、2 的可达边界也只到下标 3,下标 4 永远摸不到。solution([0]) 返回 True——唯一的下标就是终点。

贪心 O(N) 扫描只盯一个标量「目前可达的最远下标」,靠单次比较 i > farthest 判定可达性。不用 DP 表、不递归、不分层 BFS。这种「单个标量维护可达上界」的写法是很多排程/容量类问题里只问 yes/no 时的标准动作——状态机塌缩成一个标量。这道题也正好是它「数跳数」表亲(LC45)的最低可行性前置检查:先用它把不可解的输入挡在外面,再让那个更贵的优化器去算具体步数。

约束条件

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

样例

Case 1 · classic LC55 example one reachable

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

期望: true

经典 LeetCode 55 例 1。从下标 0 出发可以一步跳到下标 1,再从下标 1(值 3)一步跳到下标 4(终点)。可达,返回 True。

Case 2 · classic LC55 example two blocked at zero

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

期望: false

经典 LeetCode 55 例 2。从下标 0 可达 {1,2,3},但下标 3 的值为 0 哪儿也去不了;下标 1、2 的可达边界也只到下标 3。下标 4 永远无法到达,返回 False。

Case 3 · single element already at target

输入: [[0]]

期望: true

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

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · classic LC55 example one reachable

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

期望: true

经典 LeetCode 55 例 1。从下标 0 出发可以一步跳到下标 1,再从下标 1(值 3)一步跳到下标 4(终点)。可达,返回 True。

Case 2 · classic LC55 example two blocked at zero

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

期望: false

经典 LeetCode 55 例 2。从下标 0 可达 {1,2,3},但下标 3 的值为 0 哪儿也去不了;下标 1、2 的可达边界也只到下标 3。下标 4 永远无法到达,返回 False。

Case 3 · single element already at target

输入: [[0]]

期望: true

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