LeetCode 1306. 跳跃游戏 III（中等）
题目描述
这里有一个非负整数数组 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
问题分析
这个问题与之前的跳跃游戏有一些不同：
- 我们可以向前或向后跳跃（双向跳跃）
- 目标是到达任何一个值为0的下标，而不是数组的末尾
- 跳跃的距离是固定的，等于当前位置的值
这个问题本质上是一个图搜索问题，我们可以将数组中的每个下标视为图中的节点，从一个下标可以跳到的位置就是它的相邻节点。我们需要从起始节点出发，判断是否能到达任何一个值为0的节点。
解题思路
对于这类问题，我们有两种典型的搜索策略：
- 广度优先搜索（BFS）：逐层探索，找到最短路径
- 深度优先搜索（DFS）：沿着一条路径一直探索到底，然后回溯
由于题目只要求判断是否能到达值为0的下标，而不要求找到最短路径，所以两种方法都可以使用。这里我们将分别展示BFS和DFS的解法。
解法1：广度优先搜索（BFS）
BFS的思路是：
- 创建一个队列，将起始位置加入队列
- 创建一个访问数组，标记已经访问过的下标（避免重复访问和循环）
- 不断从队列中取出下标，检查是否为目标值（arr[i] == 0）
- 如果不是目标值，则将可以跳到的新位置（i + arr[i]和i - arr[i]）加入队列
- 继续步骤3-4，直到队列为空或找到目标值
解法2：深度优先搜索（DFS）
DFS的思路是：
- 创建一个访问数组，标记已经访问过的下标
- 从起始位置开始，递归地探索可以到达的所有位置
- 如果当前位置的值为0，返回true
- 否则，尝试跳到i + arr[i]和i - arr[i]，并递归地判断是否能到达目标
- 如果两个方向都无法到达目标，返回false
算法过程
让我们以示例1为例，详细解释BFS的执行过程：
arr = [4,2,3,0,3,1,2], start = 5
- 初始状态：
- 队列：[5]
- 已访问：[false, false, false, false, false, true, false]
- 处理节点5：
- 当前值：arr[5] = 1
- 尝试向前跳：5 + 1 = 6，加入队列
- 尝试向后跳：5 - 1 = 4，加入队列
- 队列：[6, 4]
- 已访问：[false, false, false, false, true, true, true]
- 处理节点6：
- 当前值：arr[6] = 2
- 尝试向前跳：6 + 2 = 8，越界，不加入队列
- 尝试向后跳：6 - 2 = 4，已访问，不加入队列
- 队列：[4]
- 已访问：[false, false, false, false, true, true, true]
- 处理节点4：
- 当前值：arr[4] = 3
- 尝试向前跳：4 + 3 = 7，越界，不加入队列
- 尝试向后跳：4 - 3 = 1，加入队列
- 队列：[1]
- 已访问：[false, true, false, false, true, true, true]
- 处理节点1：
- 当前值：arr[1] = 2
- 尝试向前跳：1 + 2 = 3，加入队列
- 尝试向后跳：1 - 2 = -1，越界，不加入队列
- 队列：[3]
- 已访问：[false, true, false, true, true, true, true]
- 处理节点3：
- 当前值：arr[3] = 0，找到目标值，返回true
因此，从起始位置5出发，确实可以到达值为0的下标3，路径为：5 -> 4 -> 1 -> 3。
详细代码实现
Java 实现 - BFS
class Solution {public boolean canReach(int[] arr, int start) {int n = arr.length;Queue<Integer> queue = new LinkedList<>();boolean[] visited = new boolean[n];// 将起始位置加入队列并标记为已访问queue.offer(start);visited[start] = true;// BFSwhile (!queue.isEmpty()) {int current = queue.poll();// 如果当前位置的值为0，返回trueif (arr[current] == 0) {return true;}// 尝试向前跳int forward = current + arr[current];if (forward < n && !visited[forward]) {queue.offer(forward);visited[forward] = true;}// 尝试向后跳int backward = current - arr[current];if (backward >= 0 && !visited[backward]) {queue.offer(backward);visited[backward] = true;}}// 无法到达值为0的下标return false;}
}C# 实现 - BFS
public class Solution {public bool CanReach(int[] arr, int start) {int n = arr.Length;Queue<int> queue = new Queue<int>();bool[] visited = new bool[n];// 将起始位置加入队列并标记为已访问queue.Enqueue(start);visited[start] = true;// BFSwhile (queue.Count > 0) {int current = queue.Dequeue();// 如果当前位置的值为0，返回trueif (arr[current] == 0) {return true;}// 尝试向前跳int forward = current + arr[current];if (forward < n && !visited[forward]) {queue.Enqueue(forward);visited[forward] = true;}// 尝试向后跳int backward = current - arr[current];if (backward >= 0 && !visited[backward]) {queue.Enqueue(backward);visited[backward] = true;}}// 无法到达值为0的下标return false;}
}Java 实现 - DFS
class Solution {public boolean canReach(int[] arr, int start) {int n = arr.length;boolean[] visited = new boolean[n];return dfs(arr, start, visited);}private boolean dfs(int[] arr, int index, boolean[] visited) {// 如果下标越界或已经访问过，返回falseif (index < 0 || index >= arr.length || visited[index]) {return false;}// 如果当前位置的值为0，返回trueif (arr[index] == 0) {return true;}// 标记当前位置为已访问visited[index] = true;// 尝试向前跳和向后跳return dfs(arr, index + arr[index], visited) || dfs(arr, index - arr[index], visited);}
}C# 实现 - DFS
public class Solution {public bool CanReach(int[] arr, int start) {int n = arr.Length;bool[] visited = new bool[n];return Dfs(arr, start, visited);}private bool Dfs(int[] arr, int index, bool[] visited) {// 如果下标越界或已经访问过，返回falseif (index < 0 || index >= arr.Length || visited[index]) {return false;}// 如果当前位置的值为0，返回trueif (arr[index] == 0) {return true;}// 标记当前位置为已访问visited[index] = true;// 尝试向前跳和向后跳return Dfs(arr, index + arr[index], visited) || Dfs(arr, index - arr[index], visited);}
}复杂度分析
BFS 方法
- 时间复杂度：O(n)，其中 n 是数组的长度。在最坏情况下，我们需要访问所有节点一次。
- 空间复杂度：O(n)，需要使用队列和访问数组，队列的大小最大为O(n)，访问数组的大小为O(n)。
DFS 方法
- 时间复杂度：O(n)，与BFS相同，最坏情况下需要访问所有节点一次。
- 空间复杂度：O(n)，需要使用访问数组和递归调用栈，在最坏情况下，递归调用栈的深度可能达到O(n)。
BFS和DFS的对比
- BFS（广度优先搜索）：
- 优点：可以找到最短路径（如果需要的话）
- 适用场景：当目标节点到起始节点的距离较近时
- 实现方式：使用队列，先进先出
- DFS（深度优先搜索）：
- 优点：实现简单，尤其是递归实现
- 适用场景：当解空间非常大或需要深入探索时
- 实现方式：使用递归或栈，先进后出
对于这个问题，两种方法都可以很好地解决。选择哪种方法主要取决于个人偏好和问题的具体要求。
边界情况与注意事项
- 数组只有一个元素：如果arr.length == 1，只有当arr[0] == 0且start == 0时才能返回true。
- 无法到达任何值为0的位置：如示例3所示，有些情况下可能无法到达任何值为0的位置，此时返回false。
- 可能的循环路径：由于可以向前和向后跳，很容易形成循环路径。使用visited数组标记已访问的位置可以避免这个问题。
- 越界检查：在进行跳跃操作时，需要确保新的位置不会越界（小于0或大于等于数组长度）。