資料結構與演算法教學系列文 (10) - 差分陣列、單調堆疊/佇列
HackMD 完整版請點我 差分陣列（Difference Array） 差分陣列是一種快速處理區間更新的技巧，特別適用於頻繁對陣列特定區間進行加減的情境，其基於前綴和（Prefix Sum）的概念來輔助實現。 其核心概念是透過維護一個輔助陣列 diff，來記錄原陣列的數值變化，使得區間的加減可以在 O(1) 時間內完成，而最終結果則可透過前綴和的技巧來計算。 輔助陣列的建立輔助陣列 diff 的計算方法為：diff[0] = nums[0]diff[i] = nums[i] - nums[i-1] (i > 0) 以上圖來看，原陣列 nums 是 [8, 2, 6, 3, 1]：diff[0] = 8diff[1] = nums[1] - nums[0] = 8 - 2 = -6diff[2] = nums[2] - nums[1] = 6 - 2 = 4…diff = [8, -6, 4, -3, -2] 有注意到嗎？每個 diff 記錄的是「這個位置與上個位置的差異...
資料結構與演算法教學系列文 (9) - 圖的進階議題
HackMD 完整版請點我 圖的進階議題（Advanced Topic on Graph）最短路徑（Shortest Path）最短路徑問題（Shortest Path Problem）是圖論中的一個重要課題，目的是尋找從一個起始節點到其他節點的最短路徑。相關的應用像是地圖中的導航系統、網路路由選擇等等，背後都是使用最短路徑的演算法。 path - 演算法筆記 戴克斯特拉演算法（Dijkstra’s Algorithm） 戴克斯特拉演算法是一種廣泛使用的方法，特別適用於權重非負的有向圖和無向圖，通過不斷選擇當前距離最小的未訪問節點，並更新其所有相鄰節點的最短距離，來尋找從起始節點到其他所有節點的最短路徑。 特別要注意的是，若存在負權重的邊，則戴克斯特拉演算法就不再適用。為什麼？讓我們看看以下的圖：你想到原因了嗎？在這張圖中，使用戴克斯特拉演算法會發生什麼事情？ 基礎演算法系列 — Graph 資料結構與 Dijkstra’s Algorithm Visualization of Above Example Bellman–Ford Algorithm相較於戴克斯特拉演算法...
資料結構與演算法教學系列文 (8) 字串比對、位元運算、雙重指標
HackMD 完整版請點我 字串比對（String Matching）KMP 演算法 KMP 演算法是一種用於字串搜尋的高效方法。透過建立部分配對表（最長的相同前後綴），可以快速定位搜尋字串中的可能配對位置，減少不必要的重複比較，從而加速搜尋過程。 KMP 演算法其實相對複雜且較難實作，我個人認為有大概理解概念就好，實際上也很少遇到需要直接實作該演算法的情境。 初學者學 KMP 演算法 補充：KMP algorithm，從自學到放棄 (1)補充：KMP algorithm，從自學到放棄 (2)補充：演算法筆記：substring補充：KMP Visualization Leetcode 28. Find the Index of the First Occurrence in a String 位元運算（Bit Manipulation） Bit manipulation 是在電腦中用「位元」（bit）來進行操作的技巧，這種技巧常在程式設計競賽或像 Leetcode 這樣的題目中出現。位元是電腦中最基本的單位，由 0 或 1 組成，這跟開關一樣，只有開或關的狀態。這些 ...
資料結構與演算法教學系列文 (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 動態規...
資料結構與演算法教學系列文 (6) - 暴力法、貪婪演算法、回溯法
HackMD 完整版請點我 其他演算法與常見解題技巧演算法（Algorithm）是在有限的步驟之內，提供明確的法則，求出問題正確答案的程序。它可以是一種方法、法則或者程序，讓資料可按照預先設計的方式處理。 認識演算法 推薦補充閱讀：演算法筆記 Algorithm Design 暴力法（Brute Force）暴力法（Brute Force）是一種基本的解題策略，透過系統地嘗試所有可能的解決方案來找出答案。它的原理很簡單：列舉所有可能性，不斷嘗試，直到找到符合要求的解。 這種方法的優點是實現簡單，且保證能找到存在的解。但它的效率通常較低，特別是在處理大規模問題時，因此暴力法常用於簡單問題或作為其他算法的比較基準。 以下補充幾個以前教過，但其實都跟暴力法有關的演算法。 補充：【舌尖上的演算法】Day6 – Brute Force - Selection Sort補充：【舌尖上的演算法】Day7 – Brute Force - Bubble Sort補充：【舌尖上的演算法】Day8 – Brute Force - Knapsack補充：【舌尖上的演算法】Day9 – Brut...
資料結構與演算法教學系列文 (5) - 雜湊表、字典樹、並查集
HackMD 完整版請點我 雜湊表（Hash Table） 雜湊函數的性質雜湊函式是一種把輸入數據轉換成固定長度的字符串（雜湊值）的工具。它有以下特點： 固定長度輸出：無論輸入數據有多長，輸出都是固定長度。 無法回推：從雜湊值無法反推出原始輸入（即單向性），保證了數據的不可逆性。 抗碰撞性：難以找到兩個不同的輸入有相同的雜湊值。 快速計算：能快速生成雜湊值。 [資料結構] 雜湊 (Hash) Images are from 什麼是Hash Function? 有什麼特性及用途? 雜湊函數的應用 資料完整性驗證：確保收到的資料是完整的，或確保文件未被篡改。 密碼儲存：儲存密碼的雜湊值，而不是明文密碼，提高安全性。常見的加密方式如 MD5、SHA-256 等等，若有興趣可以再研究密碼學。 資料結構：用於實現雜湊表，能夠快速存取資料。使用雜湊函數的常見資料結構包含集合（Set）、字典（Dictionary）等等。 數位簽章：保護資料完整性和驗證身份。 補充：雜湊函數 - 維基百科 Leetcode 49. Group Anagrams 387. First Uni...
資料結構與演算法教學系列文 (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...
資料結構與演算法教學系列文 (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，就稱為二元搜尋樹。二元搜尋樹有良好的排序特質，...
資料結構與演算法教學系列文 (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...
資料結構與演算法教學系列文 (1) - 概述、排序、搜尋、時間複雜度
哈囉！久違又來更新教學文系列了，這次的主題是在學完基礎程式設計後，一定也需要會的東西：資料結構與演算法。若你對程式設計還不太熟悉，或是想回去複習一下 Python 或 C++，可以參考我下面的系列文： Python 教學 C++ 教學 這個系列文應該會很長，因為 DSA（i.e. Data Structure and Algorithm）這個主題是在是涵蓋太多東西了，甚至我寫的內容也沒有到很完整。這次的來源一樣是拿來做家教講義，文字部分不會太詳盡，有需要更詳盡的內容歡迎聯絡我，如果我有空就可以幫你上課 XD。 最後就是轉載請記得標註來源，這裡面的內容都是作者本人收集的心血！ HackMD 完整版請點我 入門介紹 Google Coding Style 甚麼是演算法？ 甚麼是資料結構？ 來複習一下學習地圖，以臺大資工系必修為例：以臺大資管系必修為例： 而在演算法與資料結構的世界裡面，大概又可以分為以下幾種類別。在我們之後的課程中，會逐漸的介紹每個名詞以及其對應概念： 相關連結： How to master DSA labuladong 的算法筆記 演算法與資料結構 競...
