一題多解 遊戲模擬 Jump Game III 青蛙過河 III Leetcode_#1306
題目敘述
題目會給我們一個輸入陣列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:
