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

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

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

何謂左右指標

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

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

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

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

Two Pointer 快慢指標篇 – 陪你刷題

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

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

何謂快慢指標

透過一慢一快的兩個指標朝著同個方向前進,其中一個指標用於順序走訪 ,而另外一個則根據需求來訂定移動的策略,這樣的技巧通常用於解決 linked list 的各種問題。

利用快慢指標可以解決以下問題

  1. 將 sorted array 中重複元素剔除
  2. 判斷 linked list 是否有環
  3. 尋找 linked list 的環起點
  4. 尋找 linked list 的中間節點
  5. 尋找 linked list 上倒數第 K 個點

閱讀全文〈Two Pointer 快慢指標篇 – 陪你刷題〉

Monotonic Stack – 陪你刷題

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

本篇要來探討的是 Monotonic Stack。

什麼是 Monotonic Stack

Stack 我們都了解,有著 First-in-Last-out 的特性,而 Monotonic Stack 則是 stack 內的元素都保持著 Monotonic (單調性) 。

閱讀全文〈Monotonic Stack – 陪你刷題〉