LeetCode 1306. Jump Game III (Java版; Medium)

冷不防 2023-07-18 02:30 28阅读 0赞

### [welcome to my blog][] ###

## LeetCode 1306. Jump Game III (Java版; Meidum) ##

#### 题目描述 ####

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

#### 第一次做; 核心: 1)广度优先遍历BFS; 2)在cur处处理结果, 别在邻居处处理结果 ####

class Solution { 
        public boolean canReach(int[] arr, int start) { 
            //记录访问过的索引, 避免来回跳
            boolean[] flag = new boolean[arr.length];
            LinkedList<Integer> queue = new LinkedList<>();
            queue.add(start);
            while(!queue.isEmpty()){ 
                int cur = queue.poll();
                //在这里处理结果, 别在"邻居"中处理结果
                if(arr[cur]==0){ 
                    return true;
                }
                int index = cur-arr[cur];
                if(index>=0){ 
                    //没访问过的加入队列
                    if(flag[index]==false){ 
                        queue.add(index);
                        flag[index]=true;
                    }
                }
                index = cur + arr[cur];
                if(index < arr.length){ 
                    if(flag[index]==false){ 
                        queue.add(index);
                        flag[index]=true;
                    }
                }
            }
            return false;
        }
    }

#### 第一次做; 核心: 1) 深度优先遍历DFS; 使用DFS尝试各种可能; 改变现场, 恢复现场, 使用boolean\[\] flag记录访问过的索引, 避免来回跳 2)注意这里不是回溯, 没有返回, 没有返回, 没有返回 ####

class Solution { 
        public boolean canReach(int[] arr, int start) { 
            //记录访问过的索引, 避免来回跳
            boolean[] flag = new boolean[arr.length];
            return core(arr, start, flag);
        }
        //
        private boolean core(int[] arr, int index, boolean[] flag){ 
            //base case
            if(index < 0 || index >= arr.length || flag[index]==true){ 
                return false;
            }
            if(arr[index]==0){ 
                return true;
            }
            //改变现场
            flag[index]=true;
            boolean leftRes = core(arr, index-arr[index], flag);
            if(leftRes){ 
                return true;
            }
            boolean rightRes = core(arr, index+arr[index], flag);
            //恢复现场; 并不是回溯, 所以不需要恢复现场
            //flag[index] = false;
            return rightRes;
        }
    }

[welcome to my blog]: https://littlehaes.com