LeetCode: 1306-Jump Game III

Last Updated on 2021-12-10 by Clay

題目

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.

這個題目是 Jump Game 的第三題，題目會給定起始點，而每個位置上的數字代表著可以在這個位置上跳躍幾格的距離。

我們的目標就是：判斷從起始點開始，是否能跳到 0 所在的位置。

---

解題思路

看過一個很妙的理解是，這個題目其實就是一個二元搜索樹，每個節點都有左右兩個子節點，而我們要判斷的就是節點底下是否存在著值為 0 的子節點。

所以經典的解法之一自然就是 BFS 了。

我們先設定一個佇列（queue），將要搜尋的節點放入，一開始自然是只有放入 start 的結點。

接著判斷可跳躍的左右位置是否超出陣列 arr，如無超出的話便將左或右的位置加入等待判斷的佇列，也別忘了紀錄這個位置是否已經加入過佇列、以及判斷是否成功接觸到了 0 這個值。

如果接觸到了 0，自然是馬上回傳 true；如佇列都清空了仍然沒有接觸到 0，自然就是回傳 false 了。

C++ 範例程式碼

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        // Init
        queue<int> reached({start});
        vector<bool> visited(arr.size(), false);
        
        // BFS
        while (!reached.empty()) {
            // Get the first item in the queue
            int n = reached.front();
            reached.pop();
            
            // Hit
            if (arr[n] == 0) return true;
            
            // Add the new reach position to queue
            visited[n] = true;
            if (n-arr[n] >= 0 && visited[n-arr[n]] == false) reached.push(n-arr[n]);
            if (n+arr[n] < arr.size() && visited[n+arr[n]] == false) reached.push(n+arr[n]);
            
        }
        
        // There is no any path link to 0
        return false;
    }
};

Python 範例程式碼

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        # Init
        reached = [start]
        visited = [False] * len(arr)
        
        # BFS
        while reached:
            # Get the first item in the queue
            n = reached.pop()

            # Hit
            if arr[n] == 0: return True;
            
            # Add the new reach position to queue
            visited[n] = True;
            if n-arr[n] >= 0 and visited[n-arr[n]] == False: reached.append(n-arr[n])
            if n+arr[n] < len(arr) and visited[n+arr[n]] == False: reached.append(n+arr[n])
                    
        # There is no any path link to 0
        return False;        
        

---

References

• https://leetcode.com/problems/jump-game-iii/

---

Read More

• LeetCode 解題紀錄