BFS 廣度優先搜尋 – 陪你刷題

Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。

何時使用 BFS

當要尋找兩點間 最短距離時,就可以應用 BFS ,本質上就是將題目的起點、終點與所有可能性放到圖中,找尋起點與終點間最短距離。

另外一種常見的應用則是 Tree 的 level order traversal 。

相對於 DFS ,BFS 更適合用來解決找最短距離的問題,其代價就是要花費比較大的空間複雜度。

閱讀全文〈BFS 廣度優先搜尋 – 陪你刷題〉

Cyclic Sort – 陪你刷題

Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。

何謂 Cyclic Sort

題目給定一個 array ,如果 array 內部的數字都在一定範圍內, cyclic sort 可以在 in-place (use constant extra space) 且時間複雜度僅 O (n) 的條件下將 array 排序好。

閱讀全文〈Cyclic Sort – 陪你刷題〉

Tree Traversal 樹的遍歷 – 陪你刷題

Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。

透過此篇你可以學習到什麼?

詳解三種 binary tree 的走訪,並且以遞迴或非遞迴的方式實現。

閱讀全文〈Tree Traversal 樹的遍歷 – 陪你刷題〉