题目

题目来源：力扣（LeetCode）

这里有一个非负整数数组 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. 面前放着几张纸牌，每个纸牌下面写着一个数字
  2. 游戏开始时，作为我们起始位置的纸牌已经确定啦
  3. 把纸牌翻过来，看到后面的数字为 n，那么我们现在可以选择向左走 n 步或者向右走 n 步，但是不能超出纸牌的范围
  4. 不断的重复这个过程，直到我们遇到翻过来的数字为 0 我们就成功啦
  5. 如果无论如何都找不到 0，那么我们就失败啦

那么回到题目中，纸牌和背后的数字是一个给定的由非负整数组成的数组，起始位置是给定的一个下标，我们需要返回 true 或者 false。

我们先想一想，如果是玩这个游戏的话，我们会怎么玩呢？由于出发点是确定的，而结束的点不确定，因为可能会有多个 0 的存在，所以我们可以从出发点开始不断的做尝试。基于此我们可以得到两种思路：

  • 遇到了选择左右的情况时，我们把两种情况都记录下来，然后继续针对所有已经记录的内容逐个继续尝试，不过需要注意循环的情况。
  • 遇到了选择左右的情况时，先选择一个方向，然后继续走下去，直到发生了循环再退到上一个选择点重新选择。

其实上述两种思路也就对应了两种很常见的遍历思路，即广度优先遍历和深度优先遍历。

广度优先遍历

我们使用广度优先搜索的方法得到从 start 开始能够到达的所有位置，如果其中某个位置对应的元素值为 0，那么就返回 true。
具体地，我们初始时将 start 加入队列。在每一次的搜索过程中，我们取出队首的节点 idx，它可以到达的位置为 idx + arr[idx] 和 idx - arr[idx]。如果某个位置落在数组的下标范围 [0, len(arr)) 内，并且没有被搜索过，则将该位置加入队尾。只要我们搜索到一个对应元素值为 0 的位置，我们就返回 true。在搜索结束后，如果仍然没有找到符合要求的位置，我们就返回 false。我们还用到了一个 visited 集合来判断是否已经访问过，从而规避循环。

  1. /**
  2.  * @param {number[]} arr
  3.  * @param {number} start
  4.  * @return {boolean}
  5.  */
  6. const canReach = (arr, start) => {
  8.   // 用一个 visited 集合存储已经访问过的节点，规避重复访问
  9.   const visited = new Set();
  10.   // 首先起始位置入队列
  11.   const queue = [start];
  12.   // 遍历队列中的元素
  13.   for (let len = 0, max = arr.length; len < queue.length; ++len) {
  14.     const idx = queue[len];
  15.     // 当前位置已经访问过，跳过，不再访问
  16.     if (visited.has(idx)) continue;
  17.     // 当前位置的值 等于 0
  18.     if (arr[idx] === 0) return true;
  19.     // 将当前访问的节点加入 visited 集合中
  20.     visited.add(idx);
  21.     // 某个位置落在数组的下标范围 [0, len(arr)) 内，并且没有被搜索过，则将该位置加入队尾
  22.     idx + arr[idx] < max && queue.push(idx + arr[idx]);
  23.     idx - arr[idx] >= 0 && queue.push(idx - arr[idx]);
  24.   }
  25.   return false;
  26. };

深度优先搜索

  1. const canReach = (arr, start) => {
  2.   const val = arr[start];
  3.   if (val === 0) return true;
  4.   if (val === -1) return false;
  5.   // arr 的每个值取值范围是 [0, arr.length]，基于此，通过赋值为一个范围外的特殊值来标识已经访问过
  6.   // 在这里使用 -1 作为特殊值
  7.   arr[start] = -1;
  8.   return (start - val >= 0 && canReach(arr, start - val)) || (start + val < arr.length && canReach(arr, start + val));
  9. };