LeetCode 1306. 跳跃游戏 III
字数 2219 2025-10-26 19:15:22

LeetCode 1306. 跳跃游戏 III

题目描述

这里有一个非负整数数组 arr，你一开始位于数组的起始下标 start 处。当你位于下标 i 时，你可以跳到 i + arr[i] 或者 i - arr[i]。请你判断自己是否能够跳到任意一个对应元素值为 0 的任意位置。

注意：

  1. 任何时候你都不能跳到数组之外。
  2. 1 <= arr.length <= 5 * 10^4
  3. 0 <= arr[i] < arr.length
  4. 0 <= start < arr.length

示例 1：
输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
从下标 5 处出发，可以跳 5 - arr[5] = 5 - 2 = 3 到下标 3，或者跳 5 + arr[5] = 5 + 2 = 7（但 7 超出数组范围，不可行）。到达下标 3 后，其值为 0，所以成功。

示例 2：
输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：从下标 2 出发，可以跳到下标 2 + 2 = 4 或者下标 2 - 2 = 0。无论哪种跳法，都无法到达值为 0 的下标 1。并且从下标 0 或 4 出发，也无法到达下标 1（从0跳到3，从4跳到2，陷入循环）。

解题过程

这个问题本质上是图的遍历。我们可以将每个数组下标看作图中的一个节点。对于节点 i，它有两条边分别指向节点 i + arr[i] 和 i - arr[i]（前提是这些节点在数组范围内）。我们的目标就是从 start 节点开始，通过遍历（搜索）这张图，判断是否能到达某个值为 0 的节点。

由于存在循环跳跃的可能性（比如示例2），我们需要记录已经访问过的节点，避免陷入无限循环。深度优先搜索（DFS）和广度优先搜索（BFS）是两种可行的策略。这里我们使用更符合“跳跃”直觉的 BFS 进行讲解，它会一层一层地探索所有可能的跳跃路径。

步骤 1：初始化
我们需要一个队列（Queue）来存储待探索的节点（下标），以及一个集合（Set）或布尔数组来记录已经访问过的节点，防止重复访问。

  • 将起始位置 start 加入队列。
  • 将 start 标记为已访问。

步骤 2：开始广度优先搜索（BFS）
只要队列不为空，我们就持续进行搜索。

  1. 从队列中取出当前层的某个节点（下标）currentIndex。
  2. 检查这个节点的值 arr[currentIndex] 是否为 0。
    • 如果为 0：恭喜！我们已经找到了一个值为 0 的位置，直接返回 true。
  3. 如果当前节点值不为 0，我们需要探索从它这里能跳到哪里去。有两个方向：
    • 向右跳：nextIndexRight = currentIndex + arr[currentIndex]
    • 向左跳：nextIndexLeft = currentIndex - arr[currentIndex]
  4. 对于每一个可能的跳跃方向（右或左），我们需要判断：
    • 这个新下标是否在数组的有效范围内？（即 0 <= nextIndex < arr.length）
    • 这个新下标我们是否已经访问过？（通过查询我们的已访问记录）
  5. 如果这个新下标是有效的（在数组内）并且是未被访问过的，那么：
    • 将它标记为已访问。
    • 将它加入队列，等待下一轮的探索。

步骤 3：搜索结束后的判断
如果我们的 BFS 过程结束了（队列为空），意味着我们从 start 开始，所有能到达的位置都探索完毕了，但始终没有遇到一个值为 0 的节点。此时，我们返回 false。

让我们用示例 1 来详细走一遍流程
arr = [4,2,3,0,3,1,2], start = 5

  1. 初始化：队列 = [5], 已访问 = {5}
  2. 第一轮循环：
    • 取出 5。arr[5] = 2，不为 0。
    • 计算跳跃点：向右 5+2=7（无效，越界），向左 5-2=3（有效且未访问）。
    • 将 3 加入队列并标记已访问。队列 = [3], 已访问 = {5, 3}
  3. 第二轮循环：
    • 取出 3。arr[3] = 0。
    • 找到 0！ 立即返回 true。

再简要看示例 2 为何返回 false
arr = [3,0,2,1,2], start = 2

  1. 从 2 开始，可以跳到 4 和 0。队列 = [4, 0]，已访问 {2, 4, 0}。
  2. 从 4 开始，可以跳到 2（已访问）和 6（无效）。无可达新节点。
  3. 从 0 开始，可以跳到 3（0+3）和 -3（无效）。队列 = [3]，已访问 {2,4,0,3}。
  4. 从 3 开始，可以跳到 4（已访问）和 2（已访问）。无可达新节点。
  5. 队列空，返回 false。目标节点 1（值为0）始终无法被访问到。

关键点总结

  • 核心思想：将问题转化为图的遍历（BFS/DFS）。
  • 避免循环：使用一个数据结构记录已访问节点至关重要。
  • 终止条件：在遍历过程中，一旦遇到值为 0 的节点，立即返回成功。如果遍历完所有可达节点仍未找到，则返回失败。
  • 复杂度分析：每个节点最多被访问一次，每次访问处理常数时间操作。因此时间复杂度为 O(N)，空间复杂度为 O(N)（用于队列和已访问集合）。
LeetCode 1306. 跳跃游戏 III 题目描述 这里有一个非负整数数组 arr ，你一开始位于数组的起始下标 start 处。当你位于下标 i 时，你可以跳到 i + arr[i] 或者 i - arr[i] 。请你判断自己是否能够跳到 任意 一个对应元素值为 0 的 任意 位置。 注意： 任何时候你都不能跳到数组之外。 1 <= arr.length <= 5 * 10^4 0 <= arr[i] < arr.length 0 <= start < arr.length 示例 1： 输入：arr = [ 4,2,3,0,3,1,2 ], start = 5 输出：true 解释： 从下标 5 处出发，可以跳 5 - arr[ 5] = 5 - 2 = 3 到下标 3，或者跳 5 + arr[ 5 ] = 5 + 2 = 7（但 7 超出数组范围，不可行）。到达下标 3 后，其值为 0，所以成功。 示例 2： 输入：arr = [ 3,0,2,1,2 ], start = 2 输出：false 解释：从下标 2 出发，可以跳到下标 2 + 2 = 4 或者下标 2 - 2 = 0。无论哪种跳法，都无法到达值为 0 的下标 1。并且从下标 0 或 4 出发，也无法到达下标 1（从0跳到3，从4跳到2，陷入循环）。 解题过程 这个问题本质上是 图的遍历 。我们可以将每个数组下标看作图中的一个节点。对于节点 i ，它有两条边分别指向节点 i + arr[i] 和 i - arr[i] （前提是这些节点在数组范围内）。我们的目标就是从 start 节点开始，通过遍历（搜索）这张图，判断是否能到达某个值为 0 的节点。 由于存在循环跳跃的可能性（比如示例2），我们需要记录已经访问过的节点，避免陷入无限循环。深度优先搜索（DFS）和广度优先搜索（BFS）是两种可行的策略。这里我们使用更符合“跳跃”直觉的 BFS 进行讲解，它会一层一层地探索所有可能的跳跃路径。 步骤 1：初始化 我们需要一个队列（Queue）来存储待探索的节点（下标），以及一个集合（Set）或布尔数组来记录已经访问过的节点，防止重复访问。 将起始位置 start 加入队列。 将 start 标记为已访问。 步骤 2：开始广度优先搜索（BFS） 只要队列不为空，我们就持续进行搜索。 从队列中取出当前层的某个节点（下标） currentIndex 。 检查这个节点的值 arr[currentIndex] 是否为 0。 如果为 0 ：恭喜！我们已经找到了一个值为 0 的位置，直接返回 true 。 如果当前节点值不为 0，我们需要探索从它这里能跳到哪里去。有两个方向： 向右跳： nextIndexRight = currentIndex + arr[currentIndex] 向左跳： nextIndexLeft = currentIndex - arr[currentIndex] 对于每一个可能的跳跃方向（右或左），我们需要判断： 这个新下标是否在数组的有效范围内？（即 0 <= nextIndex < arr.length ） 这个新下标我们是否已经访问过？（通过查询我们的已访问记录） 如果这个新下标是有效的（在数组内）并且是未被访问过的，那么： 将它标记为已访问。 将它加入队列，等待下一轮的探索。 步骤 3：搜索结束后的判断 如果我们的 BFS 过程结束了（队列为空），意味着我们从 start 开始，所有能到达的位置都探索完毕了，但始终没有遇到一个值为 0 的节点。此时，我们返回 false 。 让我们用示例 1 来详细走一遍流程 arr = [ 4,2,3,0,3,1,2 ], start = 5 初始化：队列 = [ 5 ], 已访问 = {5} 第一轮循环： 取出 5。 arr[5] = 2 ，不为 0。 计算跳跃点：向右 5+2=7（无效，越界），向左 5-2=3（有效且未访问）。 将 3 加入队列并标记已访问。队列 = [ 3 ], 已访问 = {5, 3} 第二轮循环： 取出 3。 arr[3] = 0 。 找到 0！ 立即返回 true 。 再简要看示例 2 为何返回 false arr = [ 3,0,2,1,2 ], start = 2 从 2 开始，可以跳到 4 和 0。队列 = [ 4, 0 ]，已访问 {2, 4, 0}。 从 4 开始，可以跳到 2（已访问）和 6（无效）。无可达新节点。 从 0 开始，可以跳到 3（0+3）和 -3（无效）。队列 = [ 3 ]，已访问 {2,4,0,3}。 从 3 开始，可以跳到 4（已访问）和 2（已访问）。无可达新节点。 队列空，返回 false 。目标节点 1（值为0）始终无法被访问到。 关键点总结 核心思想 ：将问题转化为图的遍历（BFS/DFS）。 避免循环 ：使用一个数据结构记录已访问节点至关重要。 终止条件 ：在遍历过程中，一旦遇到值为 0 的节点，立即返回成功。如果遍历完所有可达节点仍未找到，则返回失败。 复杂度分析 ：每个节点最多被访问一次，每次访问处理常数时间操作。因此时间复杂度为 O(N)，空间复杂度为 O(N)（用于队列和已访问集合）。