學習歷程

C++ 語法

難度主題筆記月份
1cin / cout / getlineLinkSep. 2019
1<iomanip>LinkFeb. 2020
1if – elseSep. 2019
1for / while / continue / breakSep. 2019
1arraySep. 2019
1stringSep. 2019
2funciton & recursionSep. 2019
2pointer & referenceSep. 2019
2structSep. 2019

C++ 內建線性資料結構

難度主題筆記範例月份
1 Array範例Sep. 2019
2 C++ STL vector LinkSep. 2019
2 C++ STL bitset Nov. 2019
2 C++ STL list
2 C++ STL stackLink範例Sep. 2019
2 C++ STL queueLink範例Sep. 2019
2 C++ STL dequeJan. 2020

C++ STL algorithm

難度主題筆記範例月份
2sortLinkSep. 2019
2reverseLinkSep. 2019
2lower_bound & upper_boundLinkSep. 2019
2is_permutation & next_permutation & prev_permutationLinkSep. 2019
2find( ) vs. set.find( )LinkSep. 2019
2memset() vs. for-loopLinkFeb. 2020

C++ 內建非線性資料結構

難度主題筆記範例月份
2C++ STL set / multisetLink範例Sep. 2019
2C++ STL map / unordered_mapLink範例Sep. 2019
2C++ STL priority queueLink範例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 searchLink範例Dec. 2019
3分治 Divide & Conquer
=> 合併排序法 Merge sort
=> 快速排序法 Quick sort
=> 河內塔 Tower of Hanoi
Link範例Aug. 2019
2貪心 GreedyLink範例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=> 最長遞增子序列 LISLink範例Aug. 2019
3=> 0-1背包問題 0-1 KnapsackLink範例Aug. 2019
3=> 零錢問題 Change coinsLink範例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, DSULink範例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) TreeLink範例Jan. 2020
6=> 二維樹狀數組 BIT範例Jan. 2020
5單調棧 Monotonic StackLink範例Jan. 2020
5單調隊列 Monotonic QueueLink範例Jan. 2020
3雙向鏈結串列 Doubly Linked ListLinkMar. 2020
5HashLink範例Jan. 2020

圖論 Graph

難度主題筆記範例月份
3圖的遍歷 Graph Traversal
=> 深度優先搜索 DFS
LinkOct. 2019
3=> 廣度優先搜索 BFSLinkOct. 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=> 二分圖的最大匹配LinkFeb. 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
LinkDec. 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=> 樹重心 CentroidLinkNov. 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)LinkFeb. 2020
數論 Number Theory
2=> 質數 Prime Testing範例Aug. 2019
3=> 質數篩法 Sieve of EratosthenesLink範例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) functionLink範例Nov. 2019
5=> 擴展歐幾里德 (Extended Euclidean algorithm)範例Feb. 2020
2=> 模運算 Modulo Arithmetic 範例Aug. 2019
5=> 模逆元LinkFeb. 2020
4=> 快速冪 (Exponentiating by squaring)LinkNov. 2019
6Probability Theory
4Cycle-Finding範例Dec. 2019
Game Theory
5=> Nim GameLinkJan. 2020

字串處理 String Processing

難度主題筆記範例月份
基本字串處理
2=> Cipher/Encode/Encrypt/Decode/Decrypt範例Sep. 2019
2=> Frequency Counting範例Sep. 2019
2=> Input ParsingSep. 2019
2=> Output FormattingSep. 2019
2=> String Comparison範例Sep. 2019
字串匹配String Matching
5=> Knuth-Morris-Pratt’s (KMP) Algorithm
Link
Feb. 2020
String Processing with DP】
3=> 最長共同子序列 LCSLinkAug. 2019
4=> String Alignment (Edit Distance)範例Feb. 2020
=> Longest Palindrome
7===> Manacher’s Algorithm範例Apr. 2020
Suffix Trie/Tree/Array
5=> 字典樹 TrieLinkFeb. 2020
=> Suffix Trie
=> Suffix Tree
6=> Suffix Array
字串處理:Z-Algorithm範例1範例2Sep. 2020

計算幾何 Computational Geometry

難度主題筆記範例月份
Basic Geometry Objects
6=> Point
6=> Line
6=> Circle
6=> Triangle
6=> Quadrilaterals
Algorithm on PolygonApr. 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範例2Jan. 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) & 倍增法】
LinkDec. 2019
【Magic Square Construction
(Odd Size)】
【矩陣 Matrix】
5=> 矩陣乘法 Matrix MultiplicationLinkFeb. 2020
=> Matrix Chain Multiplication
5=> 矩陣快速冪 Matrix PowerLinkMar. 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