最近的文章
Array 陣列掃描
·3 分鐘
演算法
Array
Simulation
Enumeration
相鄰比較與走過單調段(上坡、下坡、山峰與山谷)、一次掃描維護前綴 / 後綴的最大值與總和、小範圍枚舉配對,以及用 tuple 當 key 處理平手
Bit Manipulation 位元運算
·3 分鐘
演算法
Bit-Manipulation
常用的位元操作、AND 只會減少位元而 OR 只會增加位元、用 n & (n » 1) 找相鄰的 1,以及全部是 1 的數 2^k - 1
Bucket Sort 桶子與鴿籠原理
·1 分鐘
演算法
Bucket-Sort
Pigeonhole-Principle
Sorting
把值域切成 n - 1 個桶子,最大間距一定不會落在同一個桶子裡,所以每個桶子只要記最小值和最大值,就能線性時間找出排序後的最大相鄰差
Hash Table 雜湊表
·4 分鐘
演算法
Hash-Table
Counting
Array
計數與「次數的次數」、把陣列本身當雜湊表(負號標記)、多個 key 同時計數(列、欄、對角線)、固定左端點增量計數,以及用正規化後的 key 分組
Linked List 鏈結串列
·3 分鐘
演算法
Linked-List
Two-Pointers
Dummy head、反轉(整條、一段、一半)、快慢指針找中點與環、間隔 n 的雙指針、兩兩交換、兩條串列相遇,以及用雜湊表複製帶 random 指標的串列
Matrix 矩陣
·3 分鐘
演算法
Matrix
Simulation
Array
轉置與旋轉、二維 index 和一維序列互換、鄰居與對角線、四個邊界的螺旋走訪
Segment Tree 與 Fenwick Tree
·2 分鐘
演算法
Segment-Tree
Binary-Indexed-Tree
Design
單點更新、區間查詢:Fenwick Tree(樹狀陣列)用 i & -i 跳,線段樹用遞迴把區間切兩半;兩者都是每次操作 O(log n)
SQL 基本查詢
·2 分鐘
演算法
Database
Sql
SELECT … WHERE 的條件組合,以及 NULL 的三值邏輯:任何跟 NULL 的比較都不是 true,要用 IS NULL
String 字串處理
·4 分鐘
演算法
String
Simulation
Hash-Table
用 list 組字串的模擬、在每個位置嘗試比對的解析、長度 k 的所有子字串、字元分類計數、固定起點的平衡子字串判斷,以及切成單字再處理
Backtracking 回溯
·3 分鐘
演算法
Backtracking
Recursion
Dfs
Pruning
選擇、遞迴、撤銷的模板,子集合、排列、限制條件、網格搜尋與剪枝
BFS 與圖的遍歷
·3 分鐘
演算法
Bfs
Dfs
Graph
Matrix
Union-Find
連通塊、網格 flood fill、多源 BFS、狀態空間 BFS、最短環,以及遞迴 DFS 的深度問題
Binary Search 二分搜尋
·5 分鐘
演算法
Binary-Search
Prefix-Sum
Two-Pointers
lower / upper bound、對答案二分、第 k 小、整數開根號,以及兩種區間寫法不能混用
