题目

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:

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

Example 2:

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

Example 3:

  1. Input: arr = [3,0,2,1,2], start = 2
  2. Output: false
  3. 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

题意

从数组arr的指定位置开始，每次能向左跳或向右跳arr[i]个位置，问能否到达值为0的位置。

思路

直接DFS。如果当前位置的值为0，则直接返回true；否则向两个位置递归处理，注意要先判断左右两个下一跳的位置是否合法，且对应下标是否已访问。

代码实现

Java

  1. class Solution {
  2.     public boolean canReach(int[] arr, int start) {
  3.         return dfs(arr, start, new boolean[arr.length]);
  4.     }
  6.     private boolean dfs(int[] arr, int index, boolean[] visited) {
  7.         if (arr[index] == 0) {
  8.             return true;
  9.         }
  11.         int left = index - arr[index];
  12.         int right = index + arr[index];
  13.         boolean dfsLeft = false;
  14.         boolean dfsRight = false;
  16.         visited[index] = true;
  18.         if (0 <= left && left < arr.length && !visited[left]) {
  19.             dfsLeft = dfs(arr, left, visited);
  20.         }
  21.         if (0 <= right && right < arr.length && !visited[right]) {
  22.             dfsRight = dfs(arr, right, visited);
  23.         }
  25.         return dfsLeft || dfsRight;
  26.     }
  27. }