Leetcode_1306_Jump Game III

[lihe]

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

跳出深搜的条件：

• index < 0 || index >=arr.length return false
• index 已经是访问过的下标 return false
• arr[index] == 0 return true

class Solution { // DFS
    public boolean canReach(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        return dfs(arr, start, visited);
    }

    private boolean dfs(int[] arr, int index, boolean[] visited){
        if(index < 0 || index >= arr.length) return false;
        if(visited[index] == true) return false;
        if(arr[index] == 0)
            return true;
        else{
            visited[index] = true;
            return dfs(arr, index - arr[index], visited) || dfs(arr, index + arr[index], visited);
        }
    }
}

class Solution {  // BFS
    public boolean canReach(int[] arr, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[arr.length];
        
        queue.add(start);
        
        while (!queue.isEmpty()){
            int size = queue.size();
            
            for(int i = 0; i < size; i++){
                int index = queue.poll();
                if(arr[index] == 0)
                    return true;
                
                if(index - arr[index] >= 0 && visited[index - arr[index]] == false){
                    queue.offer(index - arr[index]);
                    visited[index - arr[index]] = true;
                }
                
                if(index + arr[index] < arr.length && visited[index + arr[index]] == false){
                    queue.offer(index + arr[index]);
                    visited[index + arr[index]] = true;
                }
            }
        }
        return false;
    }
}