1306. Jump Game III

Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 题解。

这里是第 169 期的第 3 题，也是题目列表中的第 1306 题 -- 『Jump Game III』

题目描述

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

官方难度

MEDIUM

解决思路

题目的内容是一个小游戏，可以想象这样一个场景：

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

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

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

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

其实上述两种思路也就对应了两种很常见的遍历思路，即广度优先遍历和深度优先遍历。这部分内容我会在数据结构的新坑中详细介绍。

广度优先遍历

基于上面的第一种思路，我们用到了一个 visited 集合来判断是否已经访问过，从而规避循环。同时我们用一个 queue 来保存所有记录节点，方便基于延伸。具体代码如下：

const canReach = (arr, start) => {
  const visited = new Set();
  const queue = [start];
  for (let len = 0, max = arr.length; len < queue.length; ++len) {
    const idx = queue[len];
    if (visited.has(idx)) continue;
    if (arr[idx] === 0) return true;
    visited.add(idx);
    idx + arr[idx] < max && queue.push(idx + arr[idx]);
    idx - arr[idx] >= 0 && queue.push(idx - arr[idx]);
  }
  return false;
};

这里算是一个非常常见的广度优先遍历的实现模板了，不过具体到这道题其实还可以再优化一下。我们可以注意到题目的限制条件里，arr 的每个值取值范围是 [0, arr.length]。基于此，我们可以通过赋值为一个范围外的特殊值来标识已经访问过，从而去掉 visited 集合的使用。我这里直接使用了 -1 作为特殊值，具体代码如下：

const canReach = (arr, start) => {
  const queue = [start];
  for (let len = 0, max = arr.length; len < queue.length; ++len) {
    const idx = queue[len];
    if (arr[idx] === -1) continue;
    if (arr[idx] === 0) return true;
    idx + arr[idx] < max && queue.push(idx + arr[idx]);
    idx - arr[idx] >= 0 && queue.push(idx - arr[idx]);
    arr[idx] = -1;
  }
  return false;
};

深度优先遍历

基于上面的第二种思路，我们可以通过基于递归的方式来实现不断的层层深入，以及遇到循环后回退。具体代码如下：

const canReach = (arr, start) => {
  const val = arr[start];
  if (val === 0) return true;
  if (val === -1) return false;
  arr[start] = -1;
  return (start - val >= 0 && canReach(arr, start - val)) || (start + val < arr.length && canReach(arr, start + val));
};

递归实现的一个很明显的好处就是，看起来代码量更少了。特别适合懒懒的张小猪本猪，哈哈哈哈 >.<

另外值得注意的一点是，我们这里没有用到那个额外的 queue 去记录。那么是否我们的额外空间复杂度就是 O(1) 了呢？其实并不是的。因为我们其实是通过递归的调用栈来变相的记录了路径和回退过程。所以，在考虑额外的空间复杂度的时候，我们需要把递归的调用栈考虑进去，也就是说这里的空间复杂度其实还是 O(n)。

最后，利用到参数的默认值可以进行运算、逻辑运算符、以及逗号表达式，我们可以把上述代码变成一行实现，具体如下：

const canReach = (arr, start, val = arr[start]) => val === 0 || (arr[start] = -1, val !== -1) && ((start - val >= 0 && canReach(arr, start - val)) || (start + val < arr.length && canReach(arr, start + val)));

友情提示：生产环境中不要这样写哈，被打死我不负责，哈哈哈哈。

总结

这道题中我们可以了解到深度优先遍历和广度优先遍历这两种遍历思路，以及在具体的场景中我们还可以做的一些小优化。这两种遍历方式在以后应该会挺常见的。最后再强调一下，一行的那个写法真的会被同事打死的，哈哈哈哈嗝 >.<

相关链接

• Weekly Contest 169 的其他问题
• 本文在 leetcode 的 post
• 我的题解 repo