Sliding Window – 陪你刷題

何謂 sliding window?
sliding window 適用於線性資料結構,可以用來解決在線性資料結構中找到滿足特定條件的 sub-sequence 或 sub-array的問題。

sliding window 有以下特點:
1. 在線性時間內完成
2. 利用 two pointer 來控制 window 大小
3. 答案是連續的資料

閱讀全文〈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 左右指標篇 – 陪你刷題〉

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

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

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

何謂快慢指標

快慢指標技巧是使用兩個指標以不同的速度向前移動來解決 linked list 相關問題的一種技巧。其中一個指標稱為「慢指標」,用於順序訪問 linked list 中每個節點;另一個指標稱為「快指標」,,它可以根據需求以更快的速度跳過某些節點。

利用快慢指標可以解決以下幾類 linked list 問題:

  1. 剔除 sorted linked list 中的重複元素:快指標跳過重複元素,慢指標負責移除操作。

  2. 判斷 linked list 是否成環:如果快慢指標最終指向同一個節點,則列表成環。

  3. 尋找 linked list 的環起點:使用快慢指標找到環,然後重新定位慢指標找出環的起點。

  4. 尋找 linked list 的中間節點:快指標跳兩步,慢指標跳一步,慢指標最終會指向中間。

  5. 尋找 linked list 倒數第 K 個節點:快指標先向前走 K 步,然後快慢指標同時向前,慢指標指向的就是倒數第 K 個節點。

通過巧妙利用快慢指標的速度差,可以高效解決許多 linked list 算法問題。

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