LeetCode 1306. Jump Game III

Problem

LeetCode 1306. Jump Game III

1. 题目简述

给出一个整形非负数组，初始在index为start的位置。当处于i位置时，可以跳跃到i - arr[i]或者i + arr[i]的位置。判断是否能够到达一个值为0的位置。例如：

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 = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

2. 算法思路

BFS或DFS

虽然这道题叫jump game，但是和之前的jump game完全不同。理由在于jump game1和2都是可以看做是动态规划问题，然后进一步简化使用Greedy。但是这道题并不是一个求极值的问题，所以不要被迷惑，这道题不能用DP，而是其他方法。

那么其实就两种情况，一种是可以顺利到达节点为0，另一种不能。如果能够到达，则最终的case则是当前节点值为0；如果不能到达，则表示全局陷入了一个循环怪圈，屡次循环却无法到达，也就是说我们某种跳跃策略一旦发现了循环的迹象，立刻终止。

与其说是图，更像是一棵树，每个节点的两个子节点为i+arr[i]和i - arr[i]，因此BFS和DFS其实都是行得通的。这里两种算法都写出来。

Tips:
这里运用了一个小技巧，因为arr[i]未遍历时一定大于0（除去最终的0节点），我们遍历完某节点后将其置为-arr[i]，下次再遍历到的时候，如果发现其为负值，则立刻返回false。

3. 解法

1. DFS

class Solution {
    public boolean canReach(int[] arr, int start) {
        if (strat < 0 || start > arr.length - 1 || arr[start] < 0) {
            return false;
        }
        if (arr[start] == 0) {
            return true;
        }
        arr[start] = -arr[start];

        return canReach(arr, start + arr[start]) || canReach(arr, start - arr[start]);
    }
}

2. BFS

class Solution {
    public boolean canReach(int[] arr, int start) {
        Queue<Integer> queue = new LinkedList();
        queue.add(start);

        while (!queue.isEmpty()) {
            int index = queue.poll();
            if (arr[index] == 0) {
                return true;
            }
            if (arr[index] > 0 && index - arr[index] >= 0) {
                queue.add(index - arr[index]);
            }
            if (arr[index] > 0 && index + arr[index] < arr.length) {
                queue.add(index + arr[index]);
            }
            arr[index] = -arr[index];
        }

        return false;
    }
}