LeetCode-1306. Jump Game III

LeetCode-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 = 5Output: trueExplanation: 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 = 0Output: 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 = 2Output: falseExplanation: 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​​

题解：

class Solution {public: void dfs(vector &arr, int k, int left, int right, bool &res) { if (k >= left && k < right) { if (res == true || arr[k] == 0) { res = true; return; } else if (arr[k] != -1) { int next[2] = {k + arr[k], k - arr[k]}; int tmp = arr[k]; arr[k] = -1; for (int i = 0; i < 2; i++) { dfs(arr, next[i], left, right, res); } arr[k] = tmp; } } } bool canReach(vector& arr, int start) { bool res = false; int n = arr.size(); dfs(arr, start, 0, n, res); return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。