iT邦幫忙

2021 iThome 鐵人賽

DAY 18
0
自我挑戰組

快樂社畜路:畢業後的後端開發求職準備系列 第 18

【LeetCode】BFS

手動 redirect:【Day 3】系統模型、容錯、高可用

因為寫了 DFS,感覺不得不來一下 BFS。

BFS:先把這一層能走訪的元素先走了,再到下一層去。所以用 FIFO 的 queue 或等價的遞迴做。

不只是用在 樹 或 圖!

雖然提到 DFS 或 BFS 這兩種尋訪 / 爆破(brute force)方法,
通常會想到 tree traversal 或是 graph traversal,
但在某些輸入為 array 的題目,也能用到這樣的概念呢!
45. Jump Game II
1306. Jump Game III

蠻值得培養一下這樣的思考,
至少以我來說,跳跳遊戲系列都還蠻戳中我思考死穴的。

要用 BFS 還是 DFS?

it depends.
雖然很幹話,
但對於樹或圖的題目,通常能用 BFS 就可以用 DFS,
時間複雜度大致相同(還是有不同的時候),但根據輸入的測資可能實際時間上會有差異。
所以應該要能夠在當下思考、提出這兩者之間的差異,
並依據需求去選擇。

真的要總結的話,
DFS 重點在於遞迴和 backtrack,在圖中比較常使用 DFS。
BFS 重點在於把當下所有可能都記錄下來,適合大範圍地尋找、最短路徑,耗費較多額外空間。


上一篇
【刷題平台】中英 LeetCode、HackerRank、CodeSignal、牛客網
下一篇
【LeetCode】bit operation
系列文
快樂社畜路:畢業後的後端開發求職準備30

尚未有邦友留言

立即登入留言