[LeetCode] 1306. Jump Game III #1306

grandyang · 2019-05-30T16:34:26Z

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 * 104
0 <= arr[i] < arr.length
0 <= start < arr.length

这道题是 Jump Game 系列的第三道，前面两道分别是 Jump Game 和 Jump Game II，与之前不同的是，这道题给了一个起始位置 start，而且说了对于某个位置i，可以跳到 i + arr[i] 或者 i - arr[i] 这两个位置，问是否可以到达数字为0的位置，注意这里不是下标为0的位置，而是该位置上的数字为0。博主最先想到的方法是用 BFS 来做，因为每个位置相当于可以展开到两个新的位置，新的位置再展开，这样所有能到的位置都展开了，就可以知道有没有数字0了。

这里用个队列 queue，先把 start 放进去，然后用个数组 visited，来记录某个位置是否访问过，将 start 位置标记为 true。然后开始循环，取出队首元素，若该位置对应的数字为0，说明找到了，返回 true。然后计算出两个新的位置 left 和 right，然后分别判断一下，若没有出界且没有访问过，则标记为已访问，并加入到队列中即可，参见代码如下：

解法一：

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<bool> visited(n);
        queue<int> q{{start}};
        visited[start] = true;
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            if (arr[t] == 0) return true;
            int left = t - arr[t], right = t + arr[t];
            if (left >= 0 && !visited[left]) {
                visited[left] = true;
                q.push(left);
            }
            if (right < n && !visited[right]) {
                visited[right] = true;
                q.push(right);
            }
        }
        return false;
    }
};

我们也可以用递归来做，这里可以不用另外的函数来递归，就直接用给定的函数，那么为了记录访问过的位置，可以将访问过的位置上的数字变为相反数，这样在开头判断一下，若 start 出界，或者 arr[start] 为负数时，返回 false，若 arr[start] 为0，返回 true。否则将 arr[start] 赋值为其相反数，然后对两个展开的新的位置调用递归函数即可，参见代码如下：

解法二：

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        if (start < 0 || start >= arr.size() || arr[start] < 0) return false;
        if (arr[start] == 0) return true;
        arr[start] = - arr[start];
        return canReach(arr, start + arr[start]) || canReach(arr, start - arr[start]);
    }
};

我们也可以浓缩为一行代码来搞定，简直碉堡了～

解法三：

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        return start >= 0 && start < arr.size() && arr[start] >= 0 && ((arr[start] = -arr[start]) == 0 || canReach(arr, start + arr[start]) || canReach(arr, start - arr[start]));
    }
};

Github 同步地址:

#1306

类似题目：

Jump Game

Jump Game II

Jump Game VII

参考资料：

https://leetcode.com/problems/jump-game-iii/

https://leetcode.com/problems/jump-game-iii/discuss/473221/Simple-Java-DFS-solution

https://leetcode.com/problems/jump-game-iii/discuss/465602/JavaC%2B%2BPython-1-Line-Recursion

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）