資料結構與演算法

這個系列記錄資料結構與演算法的學習筆記。每篇筆記包含概念說明、ASCII 視覺化圖解、Java 實作程式碼與時間/空間複雜度分析。

學習路線建議

不知道從哪裡開始？依照以下難度分級，循序漸進學習：

難度	說明	建議對象
⭐ 入門	最基礎的資料結構與演算法，先從這些開始	初學者、非本科轉職
⭐⭐ 進階	需要入門基礎，面試常考	有基礎想加強、準備面試
⭐⭐⭐ 挑戰	較複雜的結構與技巧，競程或進階面試才會用到	競程選手、資深工程師

⭐ 入門（先學這些）：Array、Linked List、Stack、Queue、Hash Table、Linear Search、Sorting basics

⭐⭐ 進階：Tree、Heap、Graph、Binary Search、Dynamic Programming、Recursion、Two Pointers、Sliding Window

⭐⭐⭐ 挑戰：Trie、AVL Tree、Segment Tree、Advanced Graph、Backtracking、String Algorithms、Math Algorithms

資料結構（Data Structures）

基礎資料結構

#	主題	難度	說明
01	Array 陣列	⭐	連續記憶體、隨機存取、動態擴容
02	Linked List 鏈結串列	⭐	單向/雙向、插入刪除 O(1)、指標操作
03	Stack 堆疊	⭐	LIFO、括號匹配、運算式求值
04	Queue 佇列	⭐	FIFO、Circular Queue、BFS 應用
05	Hash Table 雜湊表	⭐	雜湊函數、碰撞處理、O(1) 查找
06	Tree 樹	⭐⭐	BST、遍歷方式、前中後序
07	Heap 堆積	⭐⭐	Min/Max Heap、Priority Queue、Heapify
08	Graph 圖	⭐⭐	鄰接表/矩陣、BFS/DFS、有向/無向

進階資料結構

#	主題	難度	說明
09	Trie 前綴樹	⭐⭐⭐	字串搜尋、自動補全、前綴匹配
10	AVL Tree 自平衡樹	⭐⭐⭐	旋轉操作、平衡因子、O(log n) 保證
11	Segment Tree 線段樹	⭐⭐⭐	區間查詢、區間更新、Lazy Propagation
12	Fenwick Tree 樹狀陣列	⭐⭐⭐	前綴和、單點更新、BIT
13	Union-Find 並查集	⭐⭐⭐	路徑壓縮、按秩合併、連通分量
14	LRU Cache	⭐⭐	HashMap + 雙向鏈結串列、O(1) 操作
15	Deque 雙端佇列	⭐⭐	頭尾皆可操作、滑動視窗應用
16	Skip List 跳躍表	⭐⭐⭐	多層索引、機率平衡、Redis 應用
17	Bloom Filter 布隆過濾器	⭐⭐⭐	機率型資料結構、空間效率、誤判率

演算法（Algorithms）

基礎演算法

#	主題	難度	說明
01	Searching 搜尋	⭐	Linear Search、Binary Search
02	Sorting 排序	⭐	Bubble、Selection、Insertion、Merge、Quick Sort
03	Dynamic Programming 動態規劃	⭐⭐	Fibonacci、LCS、背包、Coin Change、LIS
03-2	Dynamic Programming 動態規劃（下）	⭐⭐	六個經典問題
04	Recursion 遞迴	⭐⭐	階乘、費氏數列、河內塔、回溯法
05	Graph Algorithms 圖演算法	⭐⭐	Dijkstra、Bellman-Ford、Floyd-Warshall、拓撲排序
05-2	Graph Algorithms 圖演算法（下）	⭐⭐	拓撲排序與工程應用
06	Greedy 貪婪演算法	⭐⭐	活動選擇、分數背包、Huffman、Kruskal

進階演算法與技巧

#	主題	難度	說明
07	String Algorithms 字串演算法	⭐⭐⭐	KMP、Rabin-Karp、Z Algorithm、Manacher
08	Bit Manipulation 位元運算	⭐⭐	AND/OR/XOR、位元技巧、常見應用
09	Two Pointers 雙指標	⭐⭐	相向指標、同向指標、快慢指標
10	Sliding Window 滑動視窗	⭐⭐	固定/可變視窗、最大/最小子陣列
11	More Sorting 進階排序	⭐⭐⭐	Heap、Counting、Radix、Bucket、Shell Sort
12	Advanced Graph 進階圖論	⭐⭐⭐	Prim、Tarjan SCC、割點橋、二分圖匹配
13	Backtracking 回溯法	⭐⭐⭐	N-Queens、排列組合、子集生成
14	Divide and Conquer 分治法	⭐⭐	合併排序、快速冪、最近點對
15	Monotone Stack 單調堆疊	⭐⭐⭐	下一個更大元素、柱狀圖最大矩形
16	Prefix Sum 前綴和	⭐⭐	一維/二維前綴和、差分陣列
17	Math Algorithms 數學演算法	⭐⭐⭐	GCD、質數篩、快速冪、組合數學

刷題路線與反模式

#	主題	說明
23	LeetCode 刷題路線：從 Easy 到 Hard 的跨主題推進地圖	隨機刷 LeetCode 是最沒效率的方式——做了 200 題但面試還是不會
24	演算法選型 Anti-patterns：七種讓系統性能崩潰的錯誤選擇	演算法選錯不是「性能不夠好」

競程與進階主題（35-63）

#	主題	說明
35	Suffix Array 後綴陣列	Suffix Array 把字串所有後綴排序後壓進一個整數陣列
36	Computational Geometry 計算幾何基礎	從叉積判斷轉向方向開始
37	Red-Black Tree 紅黑樹	紅黑樹是 Java TreeMap、Linux 排程器、Nginx 計時器的核心——它用「…
38	B+Tree 資料庫索引的核心結構	MySQL InnoDB、PostgreSQL、NTFS 都用 B+Tree 做索引——不…
39	HyperLogLog 用 1.5 KB 計算十億個不同用戶	Google 用 HyperLogLog 計算搜尋獨立用戶數
40	Count-Min Sketch & Cuckoo Filter 串流資料的頻率與過濾	Cloudflare 用 Count-Min Sketch 做即時 DDoS 偵測
41	KD-Tree & R-Tree 空間索引：找最近的那個點	Google Maps 找最近的加油站、Uber 媒合最近的司機、遊戲引擎碰撞偵測——這些…
42	進階 DP：當狀態不再是一個數字	Edit Distance 讓 Google 的拼字修正、Git diff、DNA 比對都…
43	網路流：最大流、最小割、二分圖匹配	工廠到倉庫最多能運多少貨？航班座位如何分配才能服務最多旅客？這些問題都是網路流——最大流定…
44	`[[44-rolling-hash\|Rolling Hash 滾動雜湊：O(1) 的子字串比較]]`	找最長公共子字串、判斷兩個子字串是否相同——如果每次都逐字元比較是 O(m)
45	隨機化演算法：讓最壞情況消失	QuickSort 的最壞情況是 O(n²)
46	歐拉路徑：每條邊走且只走一次	「一筆畫問題」——能不能不抬筆畫完一個圖形？柯尼斯堡七橋問題讓歐拉在 1736 年發現了圖…
47	`[[47-meet-in-middle\|Meet in the Middle：把 O(2ⁿ) 砍成 O(2^(n/2))]]`	n=40 的子集和問題
48	掃描線：把二維問題拆成一維問題的連續處理	n 個矩形重疊的面積、地圖上線段的所有交點、最近點對——這些二維問題直接算是 O(n²)
49	莫隊演算法：把亂序查詢變成有序移動	q 個區間查詢
50	Aho-Corasick 自動機：同時搜尋所有關鍵字	敏感詞過濾要同時比對 10 萬個關鍵字——用 KMP 逐個比對是 O(k×n)
51	組合博弈論：Nim 遊戲與 Sprague-Grundy 定理	兩堆石子
52	`[[52-fft\|FFT 快速傅立葉變換：O(n²) 乘法變 O(n log n)]]`	兩個大數相乘（比如兩個 100 萬位的數字）直接算是 O(n²)
53	`[[53-two-sat\|2-SAT：O(n) 解布林可滿足性問題]]`	一般 SAT 是 NP-complete
54	`[[54-binary-lifting\|Binary Lifting：O(log n) 跳祖先、找 LCA]]`	樹上「往上跳 k 步」暴力需要 O(k)
55	`[[55-centroid-decomposition\|重心分解：O(n log n) 處理所有樹上路徑]]`	樹上有多少條路徑長度 ≤ k？暴力枚舉所有點對是 O(n²)
56	樹鏈剖分 HLD：把樹上路徑轉成線段樹區間	樹上路徑的和/最大值查詢
57	Tarjan 離線 LCA：一次 DFS 回答所有 LCA 查詢	Binary Lifting 是線上 LCA——O(n log n) 預處理
59	Treap 與 Splay Tree：不靠嚴格規則的平衡樹	AVL/紅黑樹靠嚴格旋轉，這兩條改用隨機與自我調整——好寫又能玩區間操作
60	Sparse Table：靜態區間查詢 O(1)	資料不會變時，線段樹那個 log 是白付的稅——冪等區間查詢一步到位
61	單調佇列：為什麼滑動視窗最大值天生要用它	暴力掃每個視窗是 O(nk)，單調佇列讓每個元素只進出各一次
62	持久化線段樹（主席樹）：查得到歷史的每一個版本	一般線段樹改一次舊版本就沒了——路徑複製只多 O(log n) 就保留全部版本
63	Fibonacci Heap 與 Link-Cut Tree：把攤還成本壓到極致	一個把 decrease-key 壓到 O(1)，一個在會塌會長的森林上還能查路徑

閱讀建議

入門者：從 ⭐ 入門的文章開始，建立資料結構與演算法的基礎觀念。
面試準備：重點看 ⭐⭐ 進階，特別是 03 動態規劃、09 雙指標、10 滑動視窗、13 回溯法。
競程選手：⭐⭐⭐ 挑戰級的進階資料結構（11-13）和進階圖論（12）是常見考點。
實務開發：05 Hash Table、14 LRU Cache、17 Bloom Filter 在生產系統中最常出現。