LeetCode 1306. 跳跃游戏 III

2021-04-13 HGNULB 约 6 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1306. 跳跃游戏 III

题意分析

给定一个非负整数数组 arr 和一个起始下标 start。站在下标 i 上时，可以跳到 i + arr[i] 或 i - arr[i]，前提是落点没有越出数组。问能否跳到任意一个值为 0 的下标上，只要求返回布尔值。

注意题目问的是「能不能到」，不是「最少几步到」。这一点决定了不需要记录步数、层数或路径，只需要判断可达性——把这句话在开头讲清楚，能直接砍掉一半的实现负担。

每个下标的跳跃距离是固定的 arr[i]，所以从任一下标出发最多只有两个去处：往右 i + arr[i]、往左 i - arr[i]。这是很强的结构信号：下标之间的转移关系是固定的、出度不超过 2 的有向关系，规模与 arr 长度同阶，而不是随步数膨胀。

约束里 arr.length 可达 $5 \times 10^4$，元素非负且不超过数组长度。非负是关键：arr[i] == 0 时两个落点都等于 i 自己，会原地不动；如果不做去重，这种自环会让朴素的搜索直接死循环。

边界要留意四点：start 本身可能就是 0，此时立即返回 true；数组里可能一个 0 都没有，此时答案必然是 false；跳跃可能来回穿梭形成环，必须防止无限循环；落点越界只是「这一步不能走」，不是错误，跳过即可。

解法：BFS/DFS 可达性

核心思路

把每个下标看成图节点，下标 i 向两个合法落点 i+arr[i]、i-arr[i] 连边。问题就是从 start 出发，能否到达某个值为 0 的节点。

使用 BFS 搜索可达集合。visited[i] 在下标入队时立即设为真，使每个节点最多入队一次；这既去掉重复工作，也截断 arr[i]=0 的自环和不同下标之间的环。题目只问可达性，不需要记录层数。

不变量：队列中是已经发现但尚未展开的下标，visited 恰好记录所有已经发现的下标。每次展开一个下标后，它的全部合法出边都已检查。

正确性：初始只发现 start。若一个下标可由已发现节点一步到达，算法会沿对应出边将其发现；按路径长度归纳，所有从 start 可达的下标最终都会被访问。若访问到 0 返回真；队列耗尽仍未命中，则完整可达集合中不存在 0，只能返回假。

解题步骤

将 start 入队并立即标记已访问。

反复取出队首；若当前位置值为 0，立即返回 true。

计算左右两个落点，对界内且未访问的落点执行“标记后入队”。

队列耗尽后返回 false。

样例 [4,2,3,0,3,1,2]、start=5 可沿 5 -> 4 -> 1 -> 3 到达 0，返回真。

反例 [3,0,2,1,2]、start=2 中虽然数组含有 0，但下标 1 不可达，应返回假。[2,0,2]、start=0 会在 0 与 2 之间成环，能检验是否正确使用 visited。

代码实现

import java.util.ArrayDeque;

class Solution {
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int idx = queue.poll();
            if (arr[idx] == 0) {
                return true;
            }
            int next1 = idx + arr[idx];
            int next2 = idx - arr[idx];
            if (next1 >= 0 && next1 < n && !visited[next1]) {
                visited[next1] = true;
                queue.offer(next1);
            }
            if (next2 >= 0 && next2 < n && !visited[next2]) {
                visited[next2] = true;
                queue.offer(next2);
            }
        }
        return false;
    }
}

func canReach(arr []int, start int) bool {
	n := len(arr)
	visited := make([]bool, n)
	queue := make([]int, 0)
	queue = append(queue, start)
	visited[start] = true

	for head := 0; head < len(queue); head++ {
		idx := queue[head]
		if arr[idx] == 0 {
			return true
		}
		next1 := idx + arr[idx]
		next2 := idx - arr[idx]
		if next1 >= 0 && next1 < n && !visited[next1] {
			visited[next1] = true
			queue = append(queue, next1)
		}
		if next2 >= 0 && next2 < n && !visited[next2] {
			visited[next2] = true
			queue = append(queue, next2)
		}
	}
	return false
}

复杂度分析

时间复杂度：$O(n)$，每个下标最多出队一次，每次检查两条边。

空间复杂度：$O(n)$，用于访问标记和队列。

关键点总结

数组下标是节点，两种跳法是至多两条有向边。

只问可达性，不需要 BFS 分层或步数状态。

入队即标记使每个下标只处理一次，并保证自环、普通环都能终止。

单个落点越界只表示该边不存在，不能据此返回整体失败。

迭代 BFS 避免了最长可达链达到数组长度时的递归栈风险。

易错点总结

不使用 visited：[2,0,2] 从 0 出发会在下标 0、2 之间无限循环。

只尝试右跳：样例从 5 出发必须经过左跳 4 -> 1，会被误判不可达。

某个落点越界就立即返回假：另一条边仍可能通向 0。

越界检查漏掉负下标：1-arr[1] 可能小于 0 并造成数组越界。

只检查数组是否含 0：[3,0,2,1,2] 从 2 出发无法到达下标 1。

只在生成邻居时检查 0：起点本身为 0 的 [0] 会被漏掉。

相似题目

题目	难度	考察点
55. 跳跃游戏	中等	只能向右且步长可小于 `arr[i]`，贪心维护最远可达位置即可，无需搜索
45. 跳跃游戏 II	中等	求最少跳跃次数，贪心按「当前层右边界」分层，是最短路的 $O(n)$ 特化
1345. 跳跃游戏 IV	困难	多出「跳到任意同值下标」的边，必须按值建索引并在用完后清空，否则边数爆炸
403. 青蛙过河	困难	状态是「下标 + 上一步步长」二元组，可达性判断要开哈希集合而非布尔数组
909. 蛇梯棋	中等	编号与行列的蛇形映射是主要坑点，求最短步数需要标准的按层 BFS
994. 腐烂的橘子	中等	多源 BFS，起点是所有腐烂橘子，还要在结束后校验是否有格子未被覆盖
1091. 二进制矩阵中的最短路径	中等	八方向网格最短路，需按层计数，起点终点被堵是必查边界
1926. 迷宫中离入口最近的出口	中等	终点不唯一，判定条件是「位于边界且不是入口」，容易漏掉排除入口
752. 打开转盘锁	中等	状态是四位字符串，需要额外的死亡列表当作不可访问标记，起点即死锁要特判
433. 最小基因变化	中等	邻接关系由「与库中串差一位」隐式给出，扩展时要现场枚举而非预建图
127. 单词接龙	困难	同为隐式图最短路，用通配符桶建索引可把邻居枚举从 $O(n)$ 降到 $O(L)$
200. 岛屿数量	中等	需要对所有未访问格子反复发起遍历并计数连通块，而本题只从单一起点出发
847. 访问所有节点的最短路径	困难	状态要加上「已访问集合」的位掩码，同一节点可以合法地重复经过
LCP 09. 最小跳跃次数	困难	左跳是「退到任意更小下标」，需要用前缀最优值把批量转移压成均摊 $O(1)$