Tree Traversal 樹的遍歷 – 陪你刷題

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

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

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

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

時間複雜度 – 陪你刷題

為什麼要學 Big O

學習演算法和資料結構就是為了寫出高效率的程式碼,不只在時間上需要快速,在空間上的消耗更要節省,而 Big O 就是用來衡量演算法效率的單位。因此,在學習各種資料結構與演算法帶來的好處之前,要先懂得如何透過 Big O 辨別程式碼的效率。

閱讀全文〈時間複雜度 – 陪你刷題〉

Backtracking 回溯法 – 陪你刷題

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

何謂回溯法

回溯法的處理方式就像窮舉法,將所有可能的路徑都窮舉出來,接著每條岔路都派人走下去,換個角度來看,其實這個過程就如同在決策樹或是多子樹上遍歷 (Tree Traversal) 。

但如果把每條路都確實走過,這樣的作法的時間複雜度相當高,所以回溯法有時可以使用剪枝 (pruning) 的技巧提高效率,不用將所有解法都窮舉出來。

回溯法大部份用來解決廣義的搜索問題,從許多可能的解中找出滿足要求的所有解,回溯法可以應用於以下類型:

  • 八皇后問題
  • DFS : DFS 也是 Backtracking 的一種型態,但 DFS 更強調搜尋的順序是以深度優先。
  • 排列組合
  • 0-1 背包問題

閱讀全文〈Backtracking 回溯法 – 陪你刷題〉