目錄
C++ 語法
難度 | 主題 | 筆記 | 月份 |
---|---|---|---|
1 | cin / cout / getline | Link | Sep. 2019 |
1 | <iomanip> | Link | Feb. 2020 |
1 | if – else | Sep. 2019 | |
1 | for / while / continue / break | Sep. 2019 | |
1 | array | Sep. 2019 | |
1 | string | Sep. 2019 | |
2 | funciton & recursion | Sep. 2019 | |
2 | pointer & reference | Sep. 2019 | |
2 | struct | Sep. 2019 |
C++ 內建線性資料結構
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
1 | Array | 範例 | Sep. 2019 | |
2 | C++ STL vector | Link | Sep. 2019 | |
2 | C++ STL bitset | Nov. 2019 | ||
2 | C++ STL list | |||
2 | C++ STL stack | Link | 範例 | Sep. 2019 |
2 | C++ STL queue | Link | 範例 | Sep. 2019 |
2 | C++ STL deque | Jan. 2020 |
C++ STL algorithm
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
2 | sort | Link | Sep. 2019 | |
2 | reverse | Link | Sep. 2019 | |
2 | lower_bound & upper_bound | Link | Sep. 2019 | |
2 | is_permutation & next_permutation & prev_permutation | Link | Sep. 2019 | |
2 | find( ) vs. set.find( ) | Link | Sep. 2019 | |
2 | memset() vs. for-loop | Link | Feb. 2020 |
C++ 內建非線性資料結構
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
2 | C++ STL set / multiset | Link | 範例 | Sep. 2019 |
2 | C++ STL map / unordered_map | Link | 範例 | Sep. 2019 |
2 | C++ STL priority queue | Link | 範例 | Sep. 2019 |
基礎演算法
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
2 | 【枚舉 Complete Search】 => Iterative Complete Search | Link | 範例 | Aug. 2019 |
3 | => Recursive Complete Search Backtracking (八皇后 8-Queens) | Link | 範例 | Oct. 2019 |
2 | 【排序 Sorting】 => 泡沫排序法 Bubble sort => 插入排序法 Insertion sort => 選擇排序法 Selection sort | Link | 範例 | Aug. 2019 |
2 | 【搜尋 Search】 => Two Pointers => 二分搜 Binary search | Link | 範例 | Aug. 2019 |
3 | => 三分搜 Ternary search | Link | 範例 | Dec. 2019 |
3 | 【分治 Divide & Conquer】 => 合併排序法 Merge sort => 快速排序法 Quick sort => 河內塔 Tower of Hanoi | Link | 範例 | Aug. 2019 |
2 | 【貪心 Greedy】 | Link | 範例 | Aug. 2019 |
3 | 【動態規劃 Dynamic Programming (DP)】 => Top-down DP => Bottom-up DP | Link | 範例 | Aug. 2019 |
3 | => Max 1D Range Sum | 範例 | Aug. 2019 | |
4 | => Max 2D Range Sum | 範例 | Feb. 2019 | |
3 | => 最長遞增子序列 LIS | Link | 範例 | Aug. 2019 |
3 | => 0-1背包問題 0-1 Knapsack | Link | 範例 | Aug. 2019 |
3 | => 零錢問題 Change coins | Link | 範例 | Aug. 2019 |
4 | => 區間DP | 範例 | Jan. 2020 | |
6 | => 借還DP | 範例 | Jun. 2020 | |
4 | => 環狀陣列之最大連續和 | 範例 | Mar. 2020 | |
=> Traveling Salesman Problem (TSP) |
進階資料結構
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
3 | 【圖 Graph】 => 鄰接矩陣 Adjacency matrix => 鄰接表 Adjacency list | Link | 範例 | Oct. 2019 |
4 | 【並查集 Union-Find Disjoint Sets, DSU】 | Link | 範例 | Dec. 2019 |
5 | 【線段樹 Segment Tree】 => 區間問題 => 線段樹的結構 (二元樹) => build 建立線段樹 => query 線段樹的區間查詢 => update 單點修改線段樹 | Link | 範例 | Dec. 2019 |
5 | => 懶標記 lazy tag => 區間修改線段樹 | 範例 | Dec. 2019 | |
5 | => 樹壓平 (樹的DFS序) | 範例 | Jan. 2020 | |
5 | => 掃描線 (線段樹實作) | 範例 | Mar. 2020 | |
5 | 【樹狀數組 Binary Indexed (Fenwick) Tree】 | Link | 範例 | Jan. 2020 |
6 | => 二維樹狀數組 BIT | 範例 | Jan. 2020 | |
5 | 【單調棧 Monotonic Stack】 | Link | 範例 | Jan. 2020 |
5 | 【單調隊列 Monotonic Queue】 | Link | 範例 | Jan. 2020 |
3 | 【雙向鏈結串列 Doubly Linked List】 | Link | Mar. 2020 | |
5 | 【Hash】 | Link | 範例 | Jan. 2020 |
圖論 Graph
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
3 | 【圖的遍歷 Graph Traversal】 => 深度優先搜索 DFS | Link | Oct. 2019 | |
3 | => 廣度優先搜索 BFS | Link | Oct. 2019 | |
4 | => 連通塊 Finding Connected Components (Undirected Graph) | |||
4 | => Flood Fill – Labeling/Coloring the Connected Components | 範例 | Jan. 2020 | |
4 | 【拓撲排序 Topological sort】 (Directed Acyclic Graph) | Link | 範例 | Dec. 2019 |
6 | 【二分圖 Bipartite Graph】 => 二分圖染色 (BFS) | 範例 | Feb. 2020 | |
6 | => 二分圖判定 | 範例 | Feb. 2020 | |
6 | => 二分圖的最大匹配 | Link | Feb. 2020 | |
Graph Edges Property Check via DFS Spanning Tree | ||||
5 | 【圖的連通性】 => 關節點 / 割點 Finding Articulation Points and Bridges (Undirected Graph) | 範例 | Mar. 2020 | |
5 | => 雙連通分量 (Biconnected Component) | |||
5 | => 橋連通分量 (Bridge-connected Component) | |||
5 | => 強連通分量 (Strongly Connected Component) ===> Tarjan’s Algorithm Finding Strongly Connected Components (Directed Graph) | 範例 | Mar. 2020 | |
4 | 【最小生成樹 Minimum Spanning Tree (MST)】 => Kruskal algorithm | Link | Dec. 2019 | |
4 | => Prim’s Algorithm | |||
4 | => Maximum Spanning Tree | |||
5 | => Minimax (and Maximin) | 範例 | Nov. 2019 | |
5 | => 水母圖找環 | 範例 | Feb. 2020 | |
3 | 【單點源最短路 Single-Source Shortest Paths (SSSP)】 => SSSP on Unweighted Graph (BFS) | 範例 | ||
4 | => SSSP on Weighted Graph (Dijkstra’s algorithm) | Link | 範例 | Nov. 2019 |
4 | => SSSP on Graph with Negative Weight Cycle (Bellman Ford’s algorithm) | Nov. 2019 | ||
4 | 【全點對最短路 All-Pairs Shortest Paths】 (Floyd Warshall’s algorithm) | Link | 範例 | Nov. 2019 |
6 | 【網路流 Network Flow】 => Ford Fulkerson’s Method | |||
6 | => Edmonds Karp’s Algorithm | |||
6 | => Minimum Cut | |||
【Special Graphs】 | ||||
3 | 【樹狀結構 Tree】 => Tree Traversal pre-order, in-order, and post-order | 範例 | Oct. 2019 | |
3 | => 二元樹 Binary tree => 二元搜尋樹 Binary Search Tree (BST) | 範例 | Nov. 2019 | |
3 | => 樹上的DFS | 範例 | Nov. 2019 | |
3 | => 樹直徑 Diameter | |||
3 | => 樹圓心 | 範例 | Nov. 2019 | |
3 | => 樹重心 Centroid | Link | Nov. 2019 | |
=> Eulerian Graph | ||||
4 | => Euler Paths | 範例 | Jun. 2020 | |
4 | => Euler Circuits | 範例 | Jul. 2020 | |
Max Cardinality Bipartite Matching (MCBM) and Its Max Flow Solution |
數學 Mathematics
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
2 | 【簡單數學問題】 | 範例 | Aug. 2019 | |
2 | => 數學模擬 (暴力) | 範例 | Sep. 2019 | |
3 | => 找出規律 | 範例 | Feb. 2020 | |
3 | => 數列 | 範例 | Feb. 2020 | |
4 | => 指數、對數 | |||
4 | => 多項式 | |||
4 | => 進位制 | 範例 | Sep. 2019 | |
2 | 【大數 BigInteger】 | 範例 | Sep. 2019 | |
【組合數學 Combinatorics】 | ||||
2 | => Fibonacci Numbers | 範例 | Aug. 2019 | |
=> Binomial Coefficients | ||||
5 | => 卡特蘭數 (Catalan Numbers) | Link | Feb. 2020 | |
【數論 Number Theory】 | ||||
2 | => 質數 Prime Testing | 範例 | Aug. 2019 | |
3 | => 質數篩法 Sieve of Eratosthenes | Link | 範例 | Nov. 2019 |
3 | => 最大質因數建表 | 範例 | Nov. 2019 | |
2 | => 最大公因數 GCD => 最小公倍數 LCM | Link | 範例 | Aug. 2019 |
2 | => 階乘 Factorial (!) | Aug. 2019 | ||
2 | => 質因數 Prime Factors | 範例 | Aug. 2019 | |
4 | => 歐拉函數 Euler’s Phi (Totient) function | Link | 範例 | Nov. 2019 |
5 | => 擴展歐幾里德 (Extended Euclidean algorithm) | 範例 | Feb. 2020 | |
2 | => 模運算 Modulo Arithmetic | 範例 | Aug. 2019 | |
5 | => 模逆元 | Link | Feb. 2020 | |
4 | => 快速冪 (Exponentiating by squaring) | Link | Nov. 2019 | |
6 | 【Probability Theory】 | |||
4 | 【Cycle-Finding】 | 範例 | Dec. 2019 | |
【Game Theory】 | ||||
5 | => Nim Game | Link | Jan. 2020 |
字串處理 String Processing
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
【基本字串處理】 | ||||
2 | => Cipher/Encode/Encrypt/Decode/Decrypt | 範例 | Sep. 2019 | |
2 | => Frequency Counting | 範例 | Sep. 2019 | |
2 | => Input Parsing | Sep. 2019 | ||
2 | => Output Formatting | Sep. 2019 | ||
2 | => String Comparison | 範例 | Sep. 2019 | |
【字串匹配String Matching】 | ||||
5 | => Knuth-Morris-Pratt’s (KMP) Algorithm | Link | Feb. 2020 | |
【String Processing with DP】 | ||||
3 | => 最長共同子序列 LCS | Link | Aug. 2019 | |
4 | => String Alignment (Edit Distance) | 範例 | Feb. 2020 | |
=> Longest Palindrome | ||||
7 | ===> Manacher’s Algorithm | 範例 | Apr. 2020 | |
【Suffix Trie/Tree/Array】 | ||||
5 | => 字典樹 Trie | Link | Feb. 2020 | |
=> Suffix Trie | ||||
=> Suffix Tree | ||||
6 | => Suffix Array | |||
字串處理:Z-Algorithm | 範例1、範例2 | Sep. 2020 |
計算幾何 Computational Geometry
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
Basic Geometry Objects | ||||
6 | => Point | |||
6 | => Line | |||
6 | => Circle | |||
6 | => Triangle | |||
6 | => Quadrilaterals | |||
Algorithm on Polygon | Apr. 2021 | |||
6 | => Polygon Representation | |||
6 | => Perimeter of a Polygon | |||
6 | => Area of a Polygon | |||
6 | => Checking if a Polygon is Convex | |||
6 | => Checking if a Point is Inside a Polygon | |||
6 | => Cutting Polygon with a Straight Line | |||
6 | => Finding the Convex Hull of a Set of Points |
進階主題
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
Advanced Search Techniques | ||||
=> Backtracking with Bitmask | ||||
=> Backtracking with Heavy Pruning | ||||
=> State-Space Search with BFS or Dijkstra’s | ||||
=> Meet in the Middle (Bidirectional Search) | ||||
7 | => Informed Search: A* and IDA* | |||
Advanced DP Techniques | ||||
4 | => 數位DP (DP with Bitmask) | Link | 範例 | Feb. 2020 |
5 | => 插頭DP / 輪廓DP | 範例1、範例2 | Jan. 2021 |
其它主題
難度 | 主題 | 筆記 | 範例 | 月份 |
---|---|---|---|---|
5 | 【2-SAT Problem】 | 範例1 範例2 | Jul. 2020 | |
【Art Gallery Problem】 | ||||
【Bitonic Traveling Salesman Problem】 | ||||
【Bracket Matching】 | ||||
【Chinese Postman Problem】 | ||||
【Closest Pair Problem】 | ||||
6 | 【Dinic’s Algorithm】 | |||
【Formulas or Theorems】 | ||||
6 | 【Gaussian Elimination Algorithm】 | |||
【Graph Matching】 | ||||
【Great-Circle Distance】 | ||||
【Hopcroft Karp’s Algorithm】 | ||||
【Independent and Edge-Disjoint Paths】 | ||||
【Inversion Index】 | ||||
【Josephus Problem】 | ||||
【Knight Moves】 | ||||
【Kosaraju’s Algorithm】 | ||||
4 | 【最近共同祖先 Lowest Common Ancestor (LCA) & 倍增法】 | Link | Dec. 2019 | |
【Magic Square Construction (Odd Size)】 | ||||
【矩陣 Matrix】 | ||||
5 | => 矩陣乘法 Matrix Multiplication | Link | Feb. 2020 | |
=> Matrix Chain Multiplication | ||||
5 | => 矩陣快速冪 Matrix Power | Link | Mar. 2020 | |
【Max Weighted Independent Set】 | ||||
6 | 【Min Cost (Max) Flow】 | |||
【Min Path Coveron DAG】 | ||||
【Pancake Sorting】 | ||||
【Pollard’s rho Integer Factoring Algorithm】 | ||||
【Postfix Calculator and Conversion】 | ||||
【Roman Numerals】 | ||||
【Selection Problem】 | ||||
【Shortest Path Faster Algorithm】 | ||||
【Sliding Window】 | ||||
【線性時間排序】 | ||||
2 | => 計數排序 Counting Sort | 範例 | Feb. 2020 | |
=> 基數排序 Radix Sort | ||||
4 | 【稀疏表 Sparse Table 】 | 範例 | Dec. 2019 | |
2 | 【Tower of Hanoi】 | 範例 | Oct. 2019 | |
6 | 【cdq分治】 | 範例 | May. 2020 |