LeetCode 题解工作台
跳跃游戏 III
这里有一个非负整数数组 arr ，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i] 。 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。 注意，不管是什么情况下，你都无法跳到数组之外。 示例 1： 输入： …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以使用 BFS 来判断是否能够到达值为 的下标。 定义一个队列 ，用于存储当前能够到达的下标。初始时，将 下标入队。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
示例 1：
输入：arr = [4,2,3,0,3,1,2], start = 5 输出：true 解释： 到达值为 0 的下标 3 有以下可能方案： 下标 5 -> 下标 4 -> 下标 1 -> 下标 3 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
示例 2：
输入：arr = [4,2,3,0,3,1,2], start = 0 输出：true 解释： 到达值为 0 的下标 3 有以下可能方案： 下标 0 -> 下标 4 -> 下标 1 -> 下标 3
示例 3：
输入：arr = [3,0,2,1,2], start = 2 输出：false 解释：无法到达值为 0 的下标 1 处。
提示：
1 <= arr.length <= 5 * 10^40 <= arr[i] < arr.length0 <= start < arr.length
解题思路
方法一：BFS
我们可以使用 BFS 来判断是否能够到达值为 的下标。
定义一个队列 ，用于存储当前能够到达的下标。初始时，将 下标入队。
当队列不为空时，取出队首下标 ，如果 ，则返回 true。否则，我们将下标 标记为已访问，如果 和 在数组范围内且未被访问过，则将其入队，继续搜索。
最后，如果队列为空，说明无法到达值为 的下标，返回 false。
时间复杂度 ，空间复杂度 。其中 为数组长度。
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
q = deque([start])
while q:
i = q.popleft()
if arr[i] == 0:
return True
x = arr[i]
arr[i] = -1
for j in (i + x, i - x):
if 0 <= j < len(arr) and arr[j] >= 0:
q.append(j)
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each index is visited at most once. Space complexity is O(n) due to the visited set and the recursion stack for DFS or the queue for BFS. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on array traversal patterns using DFS/BFS.
- question_mark
Check for cycles to avoid infinite loops.
- question_mark
Consider edge cases where start index is already zero.
常见陷阱
外企场景- error
Not marking visited indices leading to infinite loops.
- error
Assuming jumps can go outside the array bounds.
- error
Forgetting to check both forward and backward jumps at each index.
进阶变体
外企场景- arrow_right_alt
Use a weighted jump array where arr[i] is the maximum jump length.
- arrow_right_alt
Allow multiple start indices instead of a single start.
- arrow_right_alt
Determine the minimum number of jumps to reach zero instead of just reachability.