↓快轉到主要內容

Algorithms

Stack 與單調棧
·3 分鐘
演算法 Stack Monotonic-Stack Greedy Simulation
巢狀結構解析、跟前一個元素合併的模擬、單調棧、貪心刪字元取字典序最小,以及 lazy deletion 的 Max Stack
Queue 與設計題
·2 分鐘
演算法 Queue Design Iterator Lazy-Deletion
環狀佇列、交錯迭代器、FIFO 配對加上取消,以及設計題常用的資料結構組合
Number Theory 數論
·4 分鐘
演算法 Math Number-Theory Prime Sieve Union-Find Gcd
GCD、判斷質數、埃氏篩 / 線性篩 / 最小質因數(SPF)、質因數分解後用 Union-Find 連起來,以及用質因數的最後出現位置切陣列
Merge Sort 與分治計數
·4 分鐘
演算法 Merge-Sort Divide-and-Conquer Sorting Counting
Merge sort 模板、逆序對類計數題的計數位置、linked list 版本與常見錯誤
Math 數學技巧
·5 分鐘
演算法 Math Combinatorics Geometry Brainteaser
組合計數(配對數、切分方式)、第 k 個排列逐位決定、幾何(最近點、餘弦定理、三角不等式)、排序或觀察之後變成公式的題目,以及直式進位、進位制轉換和快速冪
Linear DP 線性 DP
·4 分鐘
演算法 Dynamic-Programming State-Machine Monotonic-Queue Binary-Search
一維 DP、狀態機 DP、DP + 單調佇列、排序後的區間排程 DP、子序列計數去重,以及標了 DP 但用觀察或貪心更快的題目
Interval DP 區間 DP
·2 分鐘
演算法 Dynamic-Programming Interval-Dp Memoization Binary-Search
區間 DP(枚舉最後一步 / 兩端合併)、切成 k 段的分割 DP、回文表 + 分割,以及狀態太複雜時直接記憶化搜尋整個狀態
Heap 優先佇列
·3 分鐘
演算法 Heap Priority-Queue Greedy Dijkstra
heapq 基本用法、Top-K、lazy deletion、雙 heap、K 路合併、掃描線與 Dijkstra
Greedy 貪心
·4 分鐘
演算法 Greedy Sorting Intervals
排序後掃描、區間按右端點排序、左右兩次掃描、配對與奇偶不變量、相鄰差值,以及「比平均大的先拿掉」;每一種都附上為什麼貪心是對的
Binary Search 二分搜尋
·5 分鐘
演算法 Binary-Search Prefix-Sum Two-Pointers
lower / upper bound、對答案二分、第 k 小、整數開根號,以及兩種區間寫法不能混用
BFS 與圖的遍歷
·3 分鐘
演算法 Bfs Dfs Graph Matrix Union-Find
連通塊、網格 flood fill、多源 BFS、狀態空間 BFS、最短環,以及遞迴 DFS 的深度問題
Backtracking 回溯
·3 分鐘
演算法 Backtracking Recursion Dfs Pruning
選擇、遞迴、撤銷的模板,子集合、排列、限制條件、網格搜尋與剪枝