資料結構與演算法教學系列文 (8) 字串比對、位元運算、雙重指標
字串比對（String Matching）
KMP 演算法
KMP 演算法是一種用於字串搜尋的高效方法。透過建立部分配對表（最長的相同前後綴），可以快速定位搜尋字串中的可能配對位置，減少不必要的重複比較，從而加速搜尋過程。
KMP 演算法其實相對複雜且較難實作，我個人認為有大概理解概念就好，實際上也很少遇到需要直接實作該演算法的情境。
- 初學者學 KMP 演算法
補充：KMP algorithm，從自學到放棄 (1)
補充：KMP algorithm，從自學到放棄 (2)
補充：演算法筆記：substring
補充：KMP Visualization
Leetcode
位元運算（Bit Manipulation）
Bit manipulation 是在電腦中用「位元」（bit）來進行操作的技巧，這種技巧常在程式設計競賽或像 Leetcode 這樣的題目中出現。位元是電腦中最基本的單位，由 0 或 1 組成，這跟開關一樣，只有開或關的狀態。這些 0 與 1 會再經由二進位制與二補數的方式，組成所有的其他數字。常見的位元操作有：AND, OR, XOR, NOT, Shift 等等，參考以下：
Leetcode
雙重指標（Two Pointers）
常用於陣列當中，用兩個指標指著不同的位置，與滑動視窗（Sliding Window）有異曲同工之妙，兩者基本上是相同技巧。
快慢指標（Fast & Slow Pointers）
此種技巧為雙重指標的特殊版本，使用一快一慢的指標（一次走不同步數 or 一個先走一個後走），常用在 Linked List 當中。
這樣可以幹嘛呢？我們來看看以下的例子：
尋找中點
判斷 Cycle 是否存在 Linked List 中
尋找倒數第 K 個節點
Leetcode
本部落格所有文章除特別聲明外，均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源 Jack's Space！
相關推薦
2025-06-10
資料結構與演算法教學系列文 (4) - 矩陣、堆積、優先佇列
HackMD 完整版請點我 矩陣（Matrix） 在介紹 Graph 的表示方法時，我們提到了兩種不同的表示方式，分別是鄰接串列（Adjacency List）與鄰接矩陣（Adjacency Matrix）。不過其實，矩陣本身也可以被當作一種資料結構來使用，舉凡像是迷宮、地圖等等具有 2D 性質的資料型態，都可以使用矩陣來表示。 Matrix 的相關操作其實都與 Graph 差不多，不外乎就是在 Matrix 中進行搜尋或遍歷，但因為我們可以以 $O(1)$ 的複雜度，直接取用 Matrix 內部中的任一元素（matrix[row][col]），所以 Matrix 在某些應用上具有較為快速的優勢。那接著就讓我們直接實戰演練吧！ Leetcode 200. Number of Islands 994. Rotting Oranges 1351. Count Negative Numbers in a Sorted Matrix 堆積（Heap）一種具有特殊性質（Parent Node 大於或小於 Child Node）的 Complete Binary Tree。 堆積排序法(H...
2025-06-10
資料結構與演算法教學系列文 (2) - 陣列、鏈結串列、堆疊、佇列
HackMD 完整版請點我 資料結構（Data Structure）資料結構是一種設計、組織、儲存資料的方式，以實現最佳性能和效率。這些結構包含不同形式，像是陣列、鍊結列表、樹、圖等等。選擇適當的資料結構對於解決特定的問題至關重要，不同的資料結構可以用於不同的應用，並且可以極大地影響程序的運行時間和記憶體使用。 陣列（Array）可隨機存取的一串連續記憶體位址。 陣列 (Array) 簡介 補充：List Are Arrays in Python Leetcode 26. Remove Duplicates from Sorted Array 27. Remove Element 鏈結串列（Linked List）元素間彼此串聯在一起，形成一條鍊子的資料結構。也可以是上圖雙向連結的形式。 Linked List：Intro(簡介) Linked List：新增資料、刪除資料、反轉 Leetcode 21. Merge Two Sorted Lists 24. Swap Nodes in Pairs 206. Reverse Linked List 堆疊（Stack...
2025-06-10
資料結構與演算法教學系列文 (1) - 概述、排序、搜尋、時間複雜度
哈囉！久違又來更新教學文系列了，這次的主題是在學完基礎程式設計後，一定也需要會的東西：資料結構與演算法。若你對程式設計還不太熟悉，或是想回去複習一下 Python 或 C++，可以參考我下面的系列文： Python 教學 C++ 教學 這個系列文應該會很長，因為 DSA（i.e. Data Structure and Algorithm）這個主題是在是涵蓋太多東西了，甚至我寫的內容也沒有到很完整。這次的來源一樣是拿來做家教講義，文字部分不會太詳盡，有需要更詳盡的內容歡迎聯絡我，如果我有空就可以幫你上課 XD。 最後就是轉載請記得標註來源，這裡面的內容都是作者本人收集的心血！ HackMD 完整版請點我 入門介紹 Google Coding Style 甚麼是演算法？ 甚麼是資料結構？ 來複習一下學習地圖，以臺大資工系必修為例：以臺大資管系必修為例： 而在演算法與資料結構的世界裡面，大概又可以分為以下幾種類別。在我們之後的課程中，會逐漸的介紹每個名詞以及其對應概念： 相關連結： How to master DSA labuladong 的算法筆記 演算法與資料結構 競...
2025-06-10
資料結構與演算法教學系列文 (7) - 分治法、動態規劃、前綴和
HackMD 完整版請點我 分治法（Divide-and-Conquer） Divide-and-Conquer又稱為分治法。其中 Divide 指的是將一個較大的問題不斷切割成小問題。而 Conquer 是當最後切割成的小問題簡單到可以直接解決，就可以組合成大問題的答案。在程式語言中時常都會用到分治法的觀念，並結合遞迴的概念求解。 Source: 分而治之法與遞迴關係 還記得之前教過的 Merge Sort 嗎？（合併排序法：將陣列不斷細分，再將細分後的結果兩兩合併。）其實 Merge Sort 的精神本質上就是 Divide-and-Conquer！ 【舌尖上的演算法】Day15 – Divide and Conquer - Merge Sort Leetcode 108. Convert Sorted Array to Binary Search Tree 148. Sort List 動態規劃（Dynamic Programming） Dynamic Programming = Divide-and-Conquer + Memoization 動態規...
2025-06-10
資料結構與演算法教學系列文 (3) - 樹、圖
HackMD 完整版請點我 樹（Tree）基本單位為 Node，且只有一個 Node 是 Root（無人指向的 Node），且不存在任何 Cycle。每個 Node 可以指向多個 Child。 Tree(樹): Intro(簡介) 二元樹（Binary Tree）當樹中的每個 Node 都只有兩個 Child，即為 Binary Tree。 Binary Tree: Intro(簡介) Binary Tree: Traversal(尋訪) 以上面的 Binary Tree 為例： Pre-Order Traversal: ABDECFG In-Order Traversal: DBEAFCG Post-Order Traversal: DEBFGCA 延伸閱讀：Binary Tree: 建立一棵Binary Tree 二元搜尋樹（Binary Search Tree）若一個二元樹中，所有 Node 都滿足 Node.left.value < Node.value < Node.right.value，就稱為二元搜尋樹。二元搜尋樹有良好的排序特質，...
評論
