LeetCode 筆記 - 1306. Jump Game III

題目在此 1306. Jump Game III

給定一個數列,第 i 個數值表示你可以把 i + arr[i] or i - arr[i] 當作下一個 index
請回傳是否可以找到 value 0

解題思維

如果沒寫過第一題,可以先看 LeetCode 筆記 - 55. Jump Game
如果沒寫過第二題,可以先看 LeetCode 筆記 - 45. Jump Game II

這題型就是附帶條件的 Depth First Search
照著條件實作就可以了

有個實作小細節是可以記錄看過的 index,一但又看到就回傳失敗
因為如果可以找到 value 0,早就回傳 True
不會還在這打打鬧鬧

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:

if (size := len(arr)) == 1:
return True

visited = set()

def dfs(index):
if index < 0 or size <= index:
return False
if index in visited:
return False
visited.add(index)

if arr[index] == 0:
return True
result = dfs(index + arr[index]) or dfs(index - arr[index])

return result

return dfs(start)

相關文章