Backtracking 回溯法 – 陪你刷題

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

何謂回溯法

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

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

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

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

Sliding Window – 陪你刷題

何謂 sliding window?
給定的 input 是線性資料結構,代表你可以循序存取 (sequential access),例如 array, linked list 或 string ,題目要求找出滿足特定條件的最長/最短的 substring, subarray 或一個目標值,就可以使用 sliding window 技巧,此技巧有以下特質:

1. 在線性時間內完成
2. 透過操控 two pointer 找出滿足條件的區間
3. 不管是搜索的範圍,或是最終答案,一定都是 continuous 的資料,continuous 代表資料可以被依序存取

閱讀全文〈Sliding Window – 陪你刷題〉

Two Pointer 左右指標篇 – 陪你刷題

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

今天要來探討的是 Two Pointer 雙指標的技巧,其中雙指標又可以分為快慢指標與左右指標,本篇將著重於左右指標。

何謂左右指標

如果想要透過走訪 array 來解決問題,一般會透過 index 或是利用指標由頭走到尾。

在某些狀況會希望由頭跟尾一起出發來走訪,此時透過左右指標分別由 array 的兩端開始,進行搬移或比較兩個元素的動作。

利用左右指標可以解決以下問題:

  1. 反轉 array
  2. 檢查 string 是否回文
  3. 在 array 中找出指定兩數之和
  4. binary search 就是左右指標的一種實現
  5. sliding window
    閱讀全文〈Two Pointer 左右指標篇 – 陪你刷題〉