题目

这里有一个非负整数数组 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^4
0 <= arr[i] < arr.length
0 <= start < arr.length

思路

我们可以按照跳跃的位置进行深搜，当到达1306. 跳跃游戏 III - 图1元素就停下来，否则就试着王两边跳，进行递归，当然超过边界也要停下来。过程中需要1306. 跳跃游戏 III - 图2数组记录一个位置是否被访问过，这里写两个dfs版本，一个有返回值的，一个没有返回值，就当多加练习。

代码

dfs无返回值

  1. class Solution {
  2.     boolean ans = false;
  4.     public boolean canReach(int[] arr, int start) {
  5.         int n = arr.length;
  6.         boolean[] visited = new boolean[n];
  7.         dfs(start, n, arr, visited);
  8.         return ans;
  9.     }
  11.     private void dfs(int start, int n, int[] arr, boolean[] visited) {
  12.         if (start >= n || start < 0 || visited[start]) {
  13.             return;
  14.         }
  15.         if (arr[start] == 0) {
  16.             ans = true;
  17.             return;
  18.         }
  19.         visited[start] = true;
  20.         dfs(start + arr[start], n, arr, visited);
  21.         dfs(start - arr[start], n, arr, visited);
  22.     }
  23. }

dfs有返回值

  1. class Solution {
  2.     public boolean canReach(int[] arr, int start) {
  3.         int n = arr.length;
  4.         boolean[] visited = new boolean[n];
  5.         return dfs(start, n, arr, visited);
  6.     }
  8.     // 该函数表示从start出发能否走到0元素位置
  9.     private boolean dfs(int start, int n, int[] arr, boolean[] visited) {
  10.         if (start >= n || start < 0 || visited[start]) {
  11.             return false;
  12.         }
  13.         // 走到了，返回true
  14.         if (arr[start] == 0) {
  15.             return true;
  16.         }
  17.         visited[start] = true;
  18.         // 目前没走到，试着继续往左往右跳，只要一个方向可以就返回true
  19.         return dfs(start + arr[start], n, arr, visited) || dfs(start - arr[start], n, arr, visited);
  20.     }
  21. }