一題多解 遊戲模擬 Jump Game III 青蛙過河 III Leetcode_#1306

Cris Tagupa on Unsplash

題目敘述

題目會給我們一個輸入陣列nums，每個元素值代表那個格子點可以左右位移的固定長度。

例如，假設 nums[i] = 3，那麼下一步可以移動到nums[i-3] 或 nums[i+3]這兩個格子點。

題目​會給定一個起始點start索引位置，請問我們能不能走到內部數值為0的格子點?

可以的話返回True。

無解的話返回False。

題目的原文敘述

測試範例

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

輸入陣列arr長度介於1 ~ 5*10^4 之間。

• 0 <= arr[i] < arr.length

每個陣列元素值都界於0~陣列長度之間。

• 0 <= start < arr.length

起始點一定是合法位置，不會在界外。

演算法

根據題意描述，這是一條判定路徑存在與否的問題。

抽象地想，我們可以把

每個陣列格子點視為一個節點

陣列的值就代表指向另外兩個節點 i - nums[i] 和 i + nums[i]的指向邊。

到這一步，我們就把路徑存在與否的問題，轉換成圖論上的路徑搜索問題。

現在題目被我們映射到一個等價的問題，從nums[start]節點開始走，是否存在一條路徑走到終點nums[end], 而且 nums[end]值為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 

每個陣列格子點視為一個節點

陣列的值就代表指向另外兩個節點 i - nums[i] 和 i + nums[i]的指向邊。

畫成圖，就變成下方這個樣子。

起點是5，問我們能不能從5號節點走向終點，而且終點的節點值value = 0

答案是可以，我們可以用DFS和BFS去做路徑搜索，最後有兩條路徑可以走到終點，終點是左下角的3號節點，節點值value=0。

綠色部分就是從起點start=5走向終點(節點值value=0)的路徑

ID 5 -> ID 4 -> ID 1 -> ID 3，節點值value = 0

ID 5 -> ID 6 -> ID 4 -> ID 1 -> ID 3，節點值value = 0

程式碼 DFS

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        # Base case aka stop condition

        # Invalid index checking, or repeated traversal
        if ( ( start < 0) or (start >= len(arr) ) or ( arr[ start ] == -1) ):
            return False;
        

        # Reach destination
        if arr[ start ] == 0 :
            return True;
        
        # General cases:
        offset = arr[ start ]

        # mark as visited
        arr[start] = -1
        
        # search in DFS
        return self.canReach(arr, start + offset ) or self.canReach( arr, start - offset )

複雜度分析 DFS 尋找路徑

令n=輸入陣列nums的長度 = 圖中的節點總數

時間複雜度:

從start拜訪整張圖，每個節點至多訪問一次，每個節點最多兩條向外的指向邊。

最後一定有結果，若有路徑回傳True，若無解則回傳False。

拜訪整張圖所需時間為O(n)。

空間複雜度:

從起點開始DFS遞迴搜索，每一層拜訪一個節點，最大深度為O(n)。

程式碼 BFS

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        
        if arr[start] == 0:
            return True

        n = len(arr)

        # mark as visited
        seen = {start}
        bfs_q = deque([start])

        while bfs_q:
            u = bfs_q.popleft()
            for next_node in [u + arr[u], u - arr[u]]:
                if 0 <= next_node < n and next_node not in seen:
                    if arr[next_node] == 0:
                        return True

                    bfs_q.append(next_node)

                    # # mark as visited
                    seen.add(next_node)
        
        return False

複雜度分析 BFS 尋找路徑

令n=輸入陣列nums的長度 = 圖中的節點總數

時間複雜度:

從start拜訪整張圖，每個節點至多訪問一次，每個節點最多兩條向外的指向邊。

最後一定有結果，若有路徑回傳True，若無解則回傳False。

拜訪整張圖所需時間為O(n)。

空間複雜度:

從起點開始BFS逐層搜索，先進先出拜訪一個節點，queue最大長度為O(n)。

關鍵知識點

把原本的題目映射到圖論上的找路徑問題，

由從找路徑聯想到其實就是拜訪整張圖，

從拜訪整張圖想到圖論裡最泛用的DFS深度優先搜索 和 BFS廣度優先搜索。

Reference:

[1] Jump Game III_Python O(n) by DFS