Hi!
在這裡希望整理出，面試前需要複習的清單。不然每一次寫完就忘記，沒有複習就去面試的話，就是等著被電爆而已 QQ，太苦了，實在是被電爆太多次了。假如我被裁員，又找不到下份工作的話，就太慘了。
這裡把我認為比較不會遇到的類別設為 "Optional"，等想到再來弄了。
其中 Sort 的部分，有聽說會希望寫出組語，並想像有特殊硬體可加速的情況下，要怎麼改 code ，或是編譯器能進行怎樣的優化。。。總之詢問的方式百百種。假如我被問到這種問題，大概馬上就淘汰了。總之只能盡人事，聽天命了 (´・ω・`)
我的學習方式是先學習怎麼用這個算法，並記熟，可以在不翻書或網頁的情況下實作這個算法，確定在面試的過程中可以成功地把題目所需的演算法給實做出來，最後再練習證明該算法的正確性，練習證明可以增加對該算法的熟練度。證明的部分可以多翻翻 introduction to algorithms ( CLRS )。另外在面試的時候，有些比較嚴格的考官是會要求證明正確性以及時間空間複雜度的，這時候光是死記硬背演算法本身的話，也是會被淘汰的。
希望可以持續把解題過程中，沒有遇過的演算法或資料結構整理在這裡。另外我是在畢業後才開始碰刷題的東西，並不專業，資料很可能有誤。再麻煩大大們看到錯誤的時候，題點一下< _ _ >。
Sorting
sorting : merge sort
example problems : LeetCode 912. Sort an Array
// version 1
class Solution {
public:
void merge(vector<int> &nums, int start, int len) {
vector<int> tmp = vector<int>(len, 0);
int m = len / 2;
int lefti = 0;
int righti = m;
for(int i = 0;i < len;i++) {
if(lefti == m) {
tmp[i] = nums[start + righti];
righti++;
} else if(righti == len) {
tmp[i] = nums[start + lefti];
lefti++;
} else {
if (nums[start + lefti] < nums[start + righti]) {
tmp[i] = nums[start + lefti];
lefti++;
} else {
tmp[i] = nums[start + righti];
righti++;
}
}
}
for(int i = 0;i < len;i++) {
nums[start + i] = tmp[i];
}
}
void mergeSort(vector<int> &nums, int start, int len) {
if (len <= 1) {
return;
}
int m = len / 2;
mergeSort(nums, start, m);
mergeSort(nums, start + m, len - m);
merge(nums, start, len);
}
vector<int> sortArray(vector<int>& nums) {
vector<int> ans = nums;
mergeSort(ans, 0, ans.size());
return ans;
}
};
// version 2
class Solution {
public:
void merge(vector<int> &nums, int start, int len) {
vector<int> tmp = vector<int>(len, 0);
int m = len / 2;
int lefti = 0;
int righti = m;
int tmpi = 0;
while(lefti < m &&
righti < len) {
if(nums[start + lefti] < nums[start + righti]) {
tmp[tmpi] = nums[start + lefti];
lefti++;
} else {
tmp[tmpi] = nums[start + righti];
righti++;
}
tmpi++;
}
while(lefti < m) {
tmp[tmpi] = nums[start + lefti];
lefti++;
tmpi++;
}
while(righti < len) {
tmp[tmpi] = nums[start + righti];
righti++;
tmpi++;
}
for(int i = 0;i < len;i++) {
nums[start + i] = tmp[i];
}
}
void mergeSort(vector<int> &nums, int start, int len) {
if (len <= 1) {
return;
}
int m = len / 2;
mergeSort(nums, start, m);
mergeSort(nums, start + m, len - m);
merge(nums, start, len);
}
vector<int> sortArray(vector<int>& nums) {
vector<int> ans = nums;
mergeSort(ans, 0, ans.size());
return ans;
}
};
// version 3
class Solution {
public:
void merge(vector<int> &nums, int start, int len) {
vector<int> tmp = vector<int> (len, 0);
int mid = len / 2;
int lefti = start;
int righti = start + mid;
int tmpi = 0;
while(lefti < start + mid &&
righti < start + len) {
if (nums[lefti] <= nums[righti]) {
tmp[tmpi++] = nums[lefti++];
} else {
tmp[tmpi++] = nums[righti++];
}
}
while(lefti < start + mid) {
tmp[tmpi++] = nums[lefti++];
}
while(righti < start + len) {
tmp[tmpi++] = nums[righti++];
}
for (int i = 0; i < tmp.size(); i++) {
nums[start + i] = tmp[i];
}
}
void merge_sort(vector<int> &nums, int start, int len) {
if (len <= 1) {
return;
}
int mid = len / 2;
merge_sort(nums, start, mid);
merge_sort(nums, start + mid, len - mid);
merge(nums, start, len);
}
vector<int> sortArray(vector<int>& nums) {
merge_sort(nums, 0, nums.size());
return nums;
}
};Time Complexity :
→ average case :O(NlogN)
→ worst case : O(NlogN)
Space Complexity : O(N)
在 merge 階段，會需要 O(N) 的空間。
Stable : yes
reference :
https://web.ntnu.edu.tw/~algo/Sort.html
https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#C
TODO :
→ [ — ] Space Complexity 的證明
→ [ — ] 試著 trace 這一個解法。
sorting : quick sort
example problems : LeetCode 912. Sort an Array
class Solution {
public:
void quickSort(vector<int> &nums, int start, int len) {
if (len < 2) {
return;
}
int i, j;
// 每一輪的 pivot 值並不會改變
int pivot = nums[start + (len / 2)];
for(i = start, j = start + len - 1;;i++, j--) {
while(nums[i] < pivot) i++;
while(nums[j] > pivot) j--;
if(i >= j) {
break;
}
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
// 之後以 index == i 為分界線
// i 以左為一個子陣列
// i 以右，包含 i 自己，也為一個子陣列
// 左子陣列有機會出現值為 pivot 的元素
// 右子陣列也有機會出現值為 pivot 的元素
int leftNum = i - start;
int rightNum = len - leftNum;
quickSort(nums, start, leftNum);
quickSort(nums, start + leftNum, rightNum);
}
vector<int> sortArray(vector<int>& nums) {
vector<int> ans = nums;
quickSort(ans, 0, ans.size());
return ans;
}
};
Time Complexity :
→ average case :O(NlogN)
→ worst case : O(NN)
Space Complexity : ??
G : O(N)
Stable : No
reference :
https://web.ntnu.edu.tw/~algo/Sort.html
https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C
TODO :
→ [ — ] 試著證明 Time Complexity 的 Average Case
sorting : heap sort
example problems : LeetCode 912. Sort an Array
// version 1
class Solution {
public:
/*
三個節點中，取值最大的節點的 index
*/
int maxIndex(vector<int> &v, int i, int j, int k, int len) {
int ret = i;
if(j < len && v[j] > v[ret]) {
ret = j;
}
if(k < len && v[k] > v[ret]) {
ret = k;
}
return ret;
}
void downHeap(vector<int> &v, int i, int len) {
int j;
while(1) {
j = maxIndex(v, i, i * 2 + 1, i * 2 + 2, len);
if(j == i) {
break;
}
int t = v[i];
v[i] = v[j];
v[j] = t;
/*
某個子樹有變化，才需要對該子樹
繼續進行 downHeap
*/
i = j;
}
}
void heapSort(vector<int> &v) {
/*
v.size() - 1
--> 最後一個節點的 index
最後一個節點的 index
取其 (index - 1) / 2 就是最後一個節點的父母節點
--> ((v.size() - 1) - 1) / 2
--> 最後一個節點的父母節點的 index
*/
/*
這一步是用來製作 binary heap
的資料結構
*/
for(int i = (v.size() - 2) / 2;i >= 0;i--) {
downHeap(v, i, v.size());
}
/*
每次從該 binary-heap 取最大值，放到陣列的最後面
接著對少了一個元素的陣列進行 binary-heap 的 down-heap 操作
最後可得到一個由小到大進行排序的陣列
*/
for(int i = 0;i < v.size() - 1;i++) {
int t = v[v.size() - 1 - i];
v[v.size() - 1 - i] = v[0];
v[0] = t;
downHeap(v, 0, v.size() - i - 1);
}
}
vector<int> sortArray(vector<int>& nums) {
heapSort(nums);
return nums;
}
};
// version 2
class Solution {
public:
int max_index(vector<int> &nums, int i, int j, int k, int len) {
int ret = -1;
if(j < len &&
nums[i] > nums[j]) {
ret = i;
} else {
ret = j;
}
if(k < len &&
nums[k] > nums[ret]) {
ret = k;
}
return ret;
}
void down_heap(vector<int> &nums, int vertex, int len) {
// 還有子節點的話，就繼續做
while(vertex * 2 + 1 < len) {
// vertex * 2 + 1 --> 左子節點
// vertex * 2 + 2 --> 右子節點
int maxi = max_index(nums, vertex, vertex * 2 + 1, vertex * 2 + 2, len);
// 代表沒有動，所以子節點也不需要進行調整
if(vertex == maxi) {
break;
}
int tmp = nums[maxi];
nums[maxi] = nums[vertex];
nums[vertex] = tmp;
vertex = maxi;
}
}
void heap_sort(vector<int> &nums, int len) {
// 先初始化一個 heap 結構
for(int i = ((nums.size() - 1) - 1) / 2; i >= 0; i--) {
down_heap(nums, i, len);
}
for(int i = nums.size() - 1;i >= 1;i--) {
// 每次將最大的元素塞到最後，最後一個元素與第 0 個元素交換，
// 然後以長度減一的狀態再從頂部做一次 down_heap
int tmp = nums[0];
nums[0] = nums[i];
nums[i] = tmp;
down_heap(nums, 0, i);
}
}
vector<int> sortArray(vector<int>& nums) {
heap_sort(nums, nums.size());
return nums;
}
};Time Complexity :
→ average case :O(NlogN)
→ worst case : O(NlogN)
Space Complexity : O(1)
Stable : No
reference :
https://web.ntnu.edu.tw/~algo/Sort.html
https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#C
TODO :
→ [ — ] 試著證明 heap sort 為 unstable
→ [ — ] 試著用 pointer，而不是陣列來表示 heap sort
( Optional ) sorting : Fibonacci-heap
Johnson’s algorithms 會需要使用 Fibonacci-heap 版本的 Dijkstra’s algorithm。
( Optional ) sorting : bubble sort
( Optional ) sorting : selection sort
( Optional ) sorting : insertion sort
( Optional ) sorting in Linear time : counting sort
( Optional ) sorting in Linear time : radix sort
( Optional ) sorting in Linear time : bucket sort
Tree
tree : lowest common ancestor ( LCA ) : 求兩點的祖先
example problems : LeetCode : 236. Lowest Common Ancestor of a Binary Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(TreeNode *root, TreeNode *p, TreeNode *q, int *parentPfind, int *parentQfind, TreeNode **p2ans) {
int localpfind = false;
int localqfind = false;
if(*p2ans != NULL) {
// 已經找到解，退出 DFS
return;
}
if (root->left) {
dfs(root->left, p, q, &localpfind, &localqfind, p2ans);
}
if (root->right) {
dfs(root->right, p, q, &localpfind, &localqfind, p2ans);
}
if (root == p) {
localpfind = true;
}
if (root == q) {
localqfind = true;
}
if (localpfind) {
*parentPfind = true;
}
if(localqfind) {
*parentQfind = true;
}
if (localpfind &&
localqfind &&
*p2ans == NULL) {
*p2ans = root;
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode *ans = NULL;
TreeNode **p2ans = &ans;
int pfind = false;
int qfind = false;
dfs(root, p, q, &pfind, &qfind, p2ans);
return ans;
}
};Time Complexity :
與 DFS 相同
Space Complexity :
與 DFS 相同，recursive stack 會需要 O(N)。
tree : lowest common ancestor ( LCA ) : 多點的祖先
exmaple problems : LeetCode 1676. Lowest Common Ancestor of a Binary Tree IV
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
/*
當找到某一個目標時，就開始紀錄最低深度的節點
當找完所有節點時，該最低深度節點就是我們想要的解
*/
class Solution {
private:
TreeNode *ans = NULL;
TreeNode *lowest_node = NULL;
int lowest_level = INT_MAX;
int found_num = 0;
public:
void dfs(TreeNode *root, int level, unordered_map<TreeNode *, bool> &um, vector<TreeNode*> &nodes) {
if (ans) {
return;
}
if (um.find(root) != um.end()) {
found_num++;
if (level < lowest_level) {
lowest_level = level;
lowest_node = root;
}
}
if (root->left) {
dfs(root->left, level + 1, um, nodes);
}
if (found_num != 0) {
if(level < lowest_level) {
lowest_level = level;
lowest_node = root;
}
}
if (root->right) {
dfs(root->right, level + 1, um, nodes);
}
if (found_num != 0) {
if(level < lowest_level) {
lowest_level = level;
lowest_node = root;
}
}
if (found_num == nodes.size() &&
ans == NULL) {
ans = lowest_node;
}
}
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*> &nodes) {
unordered_map<TreeNode *, bool> um;
for (int i = 0;i < nodes.size();i++) {
um[nodes[i]] = false;
}
dfs(root, 0, um, nodes);
return ans;
}
};Time Complexity :
與一次 DFS 相同
Space Complexity :
G: 我認為 unordered_map 會用 O(V)，以及 DFS 的 recursive stack 所需的 O(D)
(V 為節點數，E 為邊數，D 為樹的高度)
example problems : LeetCode : 1123. Lowest Common Ancestor of Deepest Leaves
example problems : LeetCode : 865. Smallest Subtree with all the Deepest Nodes
tree : trie
example problem : LeetCode : 208. Implement Trie (Prefix Tree)
typedef struct TrieNode TrieNode;
struct TrieNode {
bool is_leaf;
TrieNode *next[26];
};
class Trie {
private:
TrieNode *trie_root;
public:
Trie() {
trie_root = new TrieNode();
trie_root->is_leaf = 0;
for (int i = 0; i < 26; i++) {
trie_root->next[i] = NULL;
}
}
void insert(string word) {
TrieNode *nown = trie_root;
for (int i = 0; i < word.size(); i++) {
if (nown->next[word[i] - 'a'] == NULL) {
TrieNode *newn = new TrieNode();
newn->is_leaf = false;
for(int j = 0;j < 26;j++) {
newn->next[j] = NULL;
}
nown->next[word[i] - 'a'] = newn;
}
nown = nown->next[word[i] - 'a'];
}
nown->is_leaf = true;
}
bool search(string word) {
TrieNode *nown = trie_root;
for(int i = 0;i < word.size();i++) {
if (nown->next[word[i] - 'a'] == NULL) {
return false;
}
nown = nown->next[word[i] - 'a'];
}
return nown->is_leaf;
}
bool startsWith(string prefix) {
TrieNode *nown = trie_root;
for(int i = 0;i < prefix.size();i++) {
if (nown->next[prefix[i] - 'a'] == NULL) {
return false;
}
nown = nown->next[prefix[i] - 'a'];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/Complexity :
m is the key length
Time Complexity :
insert : O(m)
searching for a key : O(m)
searching for a prefix : O(m)
Space Complexity :
insert : O(m)
searching for a key : O(1)
searching for a prefix : O(1)
Reference :
https://leetcode.com/problems/implement-trie-prefix-tree/solutions/127843/implement-trie-prefix-tree/
example problem : LeetCode : 642. Design Search Autocomplete System
TODO
Time Complexity :
Space Complexity :
example problem : LeetCode : 14. Longest Common Prefix
example problem : LeetCode 211 . Add and Search Word — Data structure design
TODO
example problem : LeetCode : 212. Word Search II
TODO
Graph
graph : breadth-first search
example problems : LeetCode : 100. Same Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
/*
* 使用 BFS 去遍尋這兩棵樹，並在每個節點去比對
* 兩棵樹是否相同
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) {
return true;
} else if(!p || !q) {
return false;
}
queue<TreeNode *> q1;
queue<TreeNode *> q2;
q1.push(p);
q2.push(q);
while(!q1.empty() || !q2.empty()) {
TreeNode *n1 = q1.front();
TreeNode *n2 = q2.front();
q1.pop();
q2.pop();
if(n1->val != n2->val) {
return false;
}
if(n1->left && n2->left) {
q1.push(n1->left);
q2.push(n2->left);
} else if(n1->left || n2->left) {
return false;
}
if(n1->right && n2->right) {
q1.push(n1->right);
q2.push(n2->right);
} else if(n1->right || n2->right) {
return false;
}
}
if(q1.size() != q2.size()) {
return false;
}
return true;
}
};Time Complexity :
→ 假如圖是用 Adjacency Matrix 的話，複雜度就是 O(V*V)
→ 假如圖是用 Adjacency Lists 表示的話，複雜度就是 O(V*E)
Space Complexity :TODO
G: 我認為 Queue 會需要 O(V) 的空間複雜度
reference :
https://web.ntnu.edu.tw/~algo/Graph.html#6
TODO :
證明空間複雜度
example problem : LeetCode279. Perfect Squares
example problem : LeetCode1443. Minimum Time to Collect All Apples in a Tree
example problem : LeetCode433. Minimum Genetic Mutation
example problem : LeetCode529. Minesweeper
example problem : LeetCode1345. Jump Game IV
example problem : LeetCode1129. Shortest Path with Alternating Colors
example problem : LeetCode1519. Number of Nodes in the Sub-Tree With the Same Label
example problem : LeetCode269. Alien Dictionary
graph : depth-first search
example problems : LeetCode : 100. Same Tree
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool dfs(TreeNode *r1, TreeNode *r2) {
bool result = true;
if(r1->val != r2->val) {
return false;
}
if(r1->left && r2->left) {
result &= dfs(r1->left, r2->left);
} else if(r1->left || r2->left){
return false;
}
if(r1->right && r2->right) {
result &= dfs(r1->right, r2->right);
} else if(r1->right || r2->right){
return false;
}
return result;
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) {
return true;
} else if(!p || !q) {
return false;
}
return dfs(p, q);
}
};
Time Complexity :
→ 假如圖是用 Adjacency Matrix 的話，複雜度就是 O(V*V)
→ 假如圖是用 Adjacency Lists 表示的話，複雜度就是 O(V*E)
Space Complexity :
G: 我認為 Stack 會需要 O(V) 的空間複雜度
reference :
https://web.ntnu.edu.tw/~algo/Graph.html#6
example problem : LeetCode834. Sum of Distances in Tree
example problem : LeetCode1339. Maximum Product of Splitted Binary Tree
example problem : LeetCode1443. Minimum Time to Collect All Apples in a Tree
example problem : LeetCode529. Minesweeper
example problem : LeetCode472. Concatenated Words
example problem : LeetCode1519. Number of Nodes in the Sub-Tree With the Same Label
example problem : LeetCode124. Binary Tree Maximum Path Sum
graph : tree edge, back edge, forward edge, cross edge
有向圖 DFS Forest
→ Tree Edge : 樹上的邊，就是 DFS Forest 上的所有的邊
→ Back Edge：連向祖先的邊，”並不在 DFS Forest 內”，”會形成環”
→ Forward Edge：連向孫子節點的邊，”並不在 DFS Forest 內”
→ Cross Edge：樹之間的邊，”並不在 DFS Forest 內”，”可能形成環”
無向圖 DFS Forest
→ Tree Edge : 樹上的邊，就是 DFS Forest 上的所有的邊
→ Back Edge：連向祖先的邊，”並不在 DFS Forest 內”，”會形成環”
( 我認為：不會有 forward edge， forward edge 在無向圖的情況下，會變成 back edge )
InT[x] : 節點 x 進入遞迴的時刻
FinishT[x] : 節點 x 退出遞迴的時刻
( i , j ) is a tree edge or a forward edge : InT[i] < InT[j] < FinishT[j] < FinishT[i]
→ i 是 j 的父母，祖先節點
( i, j ) is a back edge : InT[j] < InT[i] < FinishT[i] < FinishT[j]
→ j 是 i 的祖先節點 ( 包含父母節點 )。
( i, j ) is a cross edge : InT[j] < FinishT[j] < InT[i] < FinishT[i]
→ 與 j 相關的節點已經遍尋完畢了，且 i 指向一個已經被遍尋完畢的樹的節點。
reference :
Graph — 演算法筆記
graph : Cycle Detection : Floyd’s Cycle Finding Algorithm
我猜這個方法只能用在每個節點的 out-degree 都為 1 的情況，不過這個方式真的很高效，也很炫炮。
example problems : LeetCode : 141. Linked List Cycle
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *rabbit = head;
ListNode *turtle = head;
for(;rabbit && turtle;) {
rabbit = rabbit->next;
if(rabbit) {
rabbit = rabbit->next;
}
turtle = turtle->next;
if (rabbit &&
rabbit == turtle) {
return true;
}
}
return false;
}
};Time Complexity :
O(N)
Space Complexity :
O(1)
example problems : LeetCode : 142. Linked List Cycle II
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while(1) {
if (fast == NULL ||
slow == NULL) {
return NULL;
}
fast = fast->next;
if(fast) {
fast = fast->next;
}
slow = slow->next;
if (fast == NULL ||
slow == NULL) {
return NULL;
}
if(fast == slow) {
slow = head;
while(slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
}
return NULL;
}
};Time Complexity :
O(N)
Space Complexity :
O(1)
explanation :
這個原理就需要理解一下數學原理了 XD。總而言之，將整個帶著循環的 Linked-List 分成循環段以及非循環段，令循環段長度為 λ，非循環段長度為 N，則快指針以及慢指針會在 λ-N的地方會合。
所以當快慢指針會合後，將慢指針調回起點，然後兩個指針以相同速率前進，會合的地方就是循環段起點。
example problems : LeetCode : 287. Find the Duplicate Number
class Solution {
public:
// 將每個陣列的元素視為指向的 index
// 然後使用 Floyd's Cycle Finding Algorithm
int findDuplicate(vector<int>& nums) {
int slowp = 0;
int fastp = 0;
while (1) {
slowp = nums[slowp];
fastp = nums[nums[fastp]];
if (slowp == fastp) {
break;
}
}
fastp = 0;
while(1) {
slowp = nums[slowp];
fastp = nums[fastp];
if (slowp == fastp) {
break;
}
}
return slowp;
}
};Time Complexity :
O(N)
Space Complexity :
O(1)
explanation :
原理與 LeetCode : 142. Linked List Cycle II 相同。
reference :
https://medium.com/@orionssl/%E6%8E%A2%E7%B4%A2-floyd-cycle-detection-algorithm-934cdd05beb9
graph : Cycle Detection : Undirected Graph
TODO
reference :
https://www.geeksforgeeks.org/detect-cycle-undirected-graph/
graph : Cycle Detection : Directed Graph
example problems : LeetCode : 1059. All Paths from Source Lead to Destination
class Solution {
public:
bool dfs(int index, unordered_map<int, vector<int>> &g, unordered_map<int, int> &state, int dest) {
if(index == dest) {
return true;
}
// 最後的點不是 dest
if(0 == g[index].size()) {
return false;
}
vector<int> &edges = g[index];
for(int i = 0;i < edges.size();i++) {
if(0 == state[edges[i]]) {
state[edges[i]] = 1;
bool res = dfs(edges[i], g, state, dest);
if(!res) {
return false;
}
state[edges[i]] = 2;
} else if(1 == state[edges[i]]) {
// back edge
return false;
} else if(2 == state[edges[i]]) {
// Cross Edge
}
}
return true;
}
bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
unordered_map<int, vector<int>> g;
for(int i = 0;i < edges.size();i++) {
g[edges[i][0]].push_back(edges[i][1]);
}
// destination 不能有 outgoing edge
if(0 != g[destination].size()) {
return false;
}
// 檢查從 source 開始有無環
// state :
// --> 0 : not visit
// --> 1 : visiting
// --> 2 : visited
unordered_map<int, int> state;
// 從 source 到 dest
return dfs(source, g, state, destination);
}
};Time Complexity :
與經典 DFS 相同
Space Complexity :
與經典 DFS 相同
reference :
https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
graph : topological sort
example problems : LeetCode : 210. Course Schedule II : BFS version
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree = vector<int>(numCourses, 0);
unordered_map<int, vector<int>> g;
for(int i = 0;i < prerequisites.size();i++) {
inDegree[prerequisites[i][0]]++;
g[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
queue<int> q;
for(int i = 0;i < numCourses;i++) {
if(0 == inDegree[i]) {
q.push(i);
}
}
vector<int> toPoSort;
/*
其實就是 BFS
每遍尋一個點，就把該點連得上的點的 inDegree 減一
並且把 inDegree 變為 0 的點加進 Queue 裡
*/
while(!q.empty()) {
int nown = q.front();
toPoSort.push_back(nown);
q.pop();
vector<int> &v = g[nown];
for(int i = 0;i < v.size();i++) {
inDegree[v[i]]--;
if(0 == inDegree[v[i]]) {
q.push(v[i]);
}
}
}
/*
假如在 toPo 裡的點的個數，不等於 numCourses
代表該圖有環
*/
return toPoSort.size() == numCourses ? toPoSort : vector<int>(0);
}
};Time Complexity :
時間複雜度跟一次圖的遍尋相同
→ 假如圖是用 Adjacency Matrix 的話，複雜度就是 O(V*V)
→ 假如圖是用 Adjacency Lists 表示的話，複雜度就是 O(V + E)
Space Complexity :
O(V+E)
reference :
https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html#2
example problems : LeetCode : 210. Course Schedule II : DFS version
class Solution {
public:
// DFS topological sort
bool dfs(int nown, vector<vector<int>> &g, vector<int> &tmp, vector<int> &visited) {
for(int i = 0;i < g[nown].size();i++) {
if(visited[g[nown][i]] == 0) {
visited[g[nown][i]] = 1;
if(!dfs(g[nown][i], g, tmp, visited)) {
return false;
}
} else if(visited[g[nown][i]] == 1) {
// detect cycle
return false;
}
}
visited[nown] = 2;
tmp.push_back(nown);
return true;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g = vector<vector<int>>(numCourses);
vector<int> visited = vector<int>(numCourses, 0);
vector<int> tmp;
vector<int> ans;
for(int i = 0;i < prerequisites.size();i++) {
g[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
for(int i = 0;i < numCourses;i++) {
if(visited[i] == 0) {
visited[i] = 1;
if(!dfs(i, g, tmp, visited)) {
return ans;
}
}
}
while(!tmp.empty()) {
ans.push_back(tmp.back());
tmp.pop_back();
}
return ans;
}
};Time Complexity :
時間複雜度跟一次圖的遍尋相同
→ 假如圖是用 Adjacency Matrix 的話，複雜度就是 O(V*V)
→ 假如圖是用 Adjacency Lists 表示的話，複雜度就是 O(V*E)
Space Complexity : TODO
我個人認為 Stack 本身會需要 O(V)，最差狀況就是這張圖是一個 Linked-List。
TODO :
→ [ — ] 證明 Space Complexity
graph : Strongly Connected Components
example problem : geeksforgeeks : Strongly Connected Components
class Solution
{
void dfs(int nown, vector<vector<int>> &g, vector<int> &tmp, vector<bool> &visited) {
for(int i = 0;i < g[nown].size();i++) {
if(!visited[g[nown][i]]) {
visited[g[nown][i]] = true;
dfs(g[nown][i], g, tmp, visited);
}
}
tmp.push_back(nown);
}
public:
//Function to find number of strongly connected components in the graph.
int kosaraju(int V, vector<int> adj[])
{
vector<vector<int>> g = vector<vector<int>>(V);
vector<vector<int>> gt = vector<vector<int>>(V);
vector<int> tmp;
vector<int> sorted;
vector<bool> visited = vector<bool>(V, false);
for(int i = 0;i < V;i++) {
for(int j = 0;j < adj[i].size();j++) {
g[i].push_back(adj[i][j]);
}
}
// 1. dfs, get the finish time of every vertex
for(int i = 0;i < V;i++) {
if(!visited[i]) {
visited[i] = true;
dfs(i, g, tmp, visited);
}
}
while(!tmp.empty()) {
sorted.push_back(tmp.back());
tmp.pop_back();
}
// 2. get gt
for(int i = 0;i < g.size();i++) {
for(int j = 0;j < g[i].size();j++) {
gt[g[i][j]].push_back(i);
}
}
// 3. do DFS, and get all the SCC
visited = vector<bool>(V, false);
int ans = 0;
for(int i = 0;i < sorted.size();i++) {
if(!visited[sorted[i]]) {
ans++;
visited[sorted[i]] = true;
dfs(sorted[i], gt, tmp, visited);
}
}
return ans;
}
};
// solution 2
public:
//Function to find number of strongly connected components in the graph.
/*
1. 用 dfs 取得 dfs 遍尋的順序。
2. 透過原圖 g，取得每個邊方向相反的 gt
3. 將 dfs 遍尋的順序倒置
4. 照著這個順序在 gt 內進行 dfs
5. 此時這個 dfs forest 裡，dfs tree 的數量，就是 SCC 的數量
*/
void dfs(int nown, vector<bool> &visited, vector<int> &order,
vector<vector<int>> &g, bool record_order) {
for (int i = 0;i < g[nown].size();i++) {
if (!visited[g[nown][i]]) {
visited[g[nown][i]] = true;
dfs(g[nown][i], visited, order, g, record_order);
}
}
if (record_order) {
order.push_back(nown);
}
}
int kosaraju(int V, vector<vector<int>>& adj)
{
vector<vector<int>> gt = vector<vector<int>>(V);
vector<bool> visited = vector<bool>(V, false);
vector<int> order;
// get the order of dfs visiting
for (int i = 0;i < V;i++) {
if (!visited[i]) {
visited[i] = true;
dfs(i, visited, order, adj, true);
}
}
// get the gt
for (int i = 0;i < adj.size();i++) {
for (int j = 0;j < adj[i].size();j++) {
gt[adj[i][j]].push_back(i);
}
}
// get the number of SCC
visited = vector<bool>(V, false);
int ans = 0;
for (int i = order.size() - 1;i >= 0;i--) {
if (!visited[order[i]]) {
visited[order[i]] = true;
ans++;
dfs(order[i], visited, order, gt, false);
}
}
return ans;
}algorighm :
- 先來一個 DFS，算出每個節點離開的時間
這裡其實不需要真的算出每個節點離開的時間，只需要知道他們的順序就好。所以也不需要真的去做排序 O(N*(LOG N))，只需要把節點遍尋完的順序記下來就可以了。 - 將圖倒置
- 從最晚離開的點開始 DFS 被倒置的圖，此時生成的 DFS forest 就是一個個 strongly connected component
Time Complexity :
O(V+E) ， 與 DFS 的時間複雜度相同
Space Complexity :
O(V)
Reference :
演算法筆記： strongly connected component
https://web.ntnu.edu.tw/~algo/ConnectedComponent.html#2
TODO :
[ — ] 證明該算法的正確性，可參考 CLRS 。
example problem : LeetCode : 207. Course Schedule
這題不需要用 SCC 來解，但是可以用來練習 SCC。
graph : minimum spanning trees : Kruskal
example problem : LeetCode : 1135. Connecting Cities With Minimum Cost
1. 對邊進行 sort
2. 由小到大把邊的兩點加入同一個 set
3. 假如兩個節點在同一個 set，則丟棄這條邊
4. 假如這條邊沒有被丟棄，則加上這條邊的權重
5. 總合為 MST 的權重，沒全部沒被丟棄的邊則為 MST
bool compare_edge(vector<int> &a, vector<int> &b) {
return a[2] <= b[2];
}
class Solution {
public:
vector<int> p;
int disjoint_set_find(int x) {
if (p[x] == x) {
return x;
}
p[x] = disjoint_set_find(p[x]);
return p[x];
}
void disjoint_set_union(int x, int y) {
x = disjoint_set_find(x);
y = disjoint_set_find(y);
p[x] = y;
}
int minimumCost(int n, vector<vector<int>>& connections) {
int ans = 0;
int conn = 0;
p = vector<int> (n + 1);
for (int i = 0;i < n + 1;i++) {
p[i] = i;
}
sort(connections.begin(), connections.end(), compare_edge);
for (int i = 0;i < connections.size();i++) {
if (disjoint_set_find(connections[i][0]) ==
disjoint_set_find(connections[i][1])) {
continue;
}
disjoint_set_union(connections[i][0], connections[i][1]);
conn++;
ans += connections[i][2];
}
return conn == n - 1 ? ans : -1;
}
};Time Complexity :
O (|E| * (log V))
Space Complexity :
xxx
example problem : LeetCode : 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
// TODO : 效能太差了
bool edge_sort(vector<int> &a, vector<int> &b) {
return a[2] < b[2];
}
class Solution {
private:
int disjoint_set_find(int x, vector<int> &p) {
if (p[x] == x) {
return x;
}
p[x] = disjoint_set_find(p[x], p);
return p[x];
}
void disjoint_set_union(int x, int y, vector<int> &p) {
x = disjoint_set_find(x, p);
y = disjoint_set_find(y, p);
p[x] = y;
return;
}
// function :
// --> 0 : normal mst
// --> 1 : delete an edge
// --> 2 : add an edge into list in the beginning
// e :
// --> the edge that will be delete or add into list
int mst(int n, vector<vector<int>> &edges, int function, vector<int> &e) {
vector<int> p = vector<int>(n);
int sum = 0;
for(int i = 0;i < n;i++) {
p[i] = i;
}
if(function == 2) {
sum += e[2];
disjoint_set_union(e[0], e[1], p);
}
for (int i = 0;i < edges.size();i++) {
if ((function == 1 || function == 2) &&
edges[i] == e) {
continue;
}
int x = disjoint_set_find(edges[i][0], p);
int y = disjoint_set_find(edges[i][1], p);
if(x != y) {
sum += edges[i][2];
disjoint_set_union(x, y, p);
}
}
return sum;
}
public:
vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
vector<vector<int>> ans = vector<vector<int>>(2);
vector<bool> critical = vector<bool>(edges.size(), false);
for(int i = 0;i < edges.size();i++) {
edges[i].push_back(i);
}
sort(edges.begin(), edges.end(), edge_sort);
// 1. 跑一次 MST ， 取得 MST 的 total weight
int sum = mst(n, edges, 0, edges[0]);
// 2. 遍尋每個邊，尋找 critical edges
for(int i = 0;i < edges.size();i++) {
int localsum = mst(n, edges, 1, edges[i]);
if(localsum != sum) {
critical[i] = true;
ans[0].push_back(edges[i][3]);
}
}
// 3. 遍尋除了 critical edges 以外的每個邊，尋找 Pseudo-Critical Edges
for(int i = 0;i < edges.size();i++) {
if(critical[i]) {
continue;
}
int localsum = mst(n, edges, 2, edges[i]);
if(localsum == sum) {
ans[1].push_back(edges[i][3]);
}
}
return ans;
}
};Time Complexity :
G: 每一次的 Kruskal 需要 O(E *(lg V)) 的時間複雜度。
這邊做了 2 * E + 1 次的 Kruskal，所以我猜這題的時間複雜度為 O(E * E * (lg V))
Space Complexity :
G : O (V + E)
disjoint-set 需要 O (V)，並且儲存的答案的 ans 需要 O(E)
Reference :
https://www.tenlong.com.tw/products/9780262033848
graph : minimum spanning trees : Prim
example problem : LeetCode : 1135. Connecting Cities With Minimum Cost
typedef struct Node Node;
struct Node {
int n;
int p;
};
bool compare_node(Node &a, Node &b) {
return a.p > b.p;
}
class Solution {
public:
int minimumCost(int n, vector<vector<int>>& connections) {
vector<bool> visited = vector<bool>(n + 1, false);
vector<int> d = vector<int>(n + 1, INT_MAX);
// parent
vector<int> p = vector<int>(n + 1, -1);
vector<vector<Node>> g = vector<vector<Node>> (n + 1);
int num_vertex = 0;
int sum = 0;
for(int i = 0;i < connections.size();i++) {
g[connections[i][0]].push_back({connections[i][1], connections[i][2]});
g[connections[i][1]].push_back({connections[i][0], connections[i][2]});
}
priority_queue<Node, vector<Node>, decltype(&compare_node)> pq(compare_node);
d[1] = 0;
pq.push({1, 0});
while(!pq.empty()) {
Node nown = pq.top();
pq.pop();
if(visited[nown.n]) {
continue;
}
visited[nown.n] = true;
num_vertex++;
printf("nown.n : %d\n", nown.n);
vector<Node> &es = g[nown.n];
for (int i = 0;i < es.size();i++) {
if (es[i].p < d[es[i].n] &&
/* 須確保該點還在 pq 裡面 */
!visited[es[i].n]) {
d[es[i].n] = es[i].p;
p[es[i].n] = nown.n;
pq.push({es[i].n, es[i].p});
}
}
}
if (num_vertex != n) {
return -1;
}
for(int i = 1;i <= n;i++) {
printf("d[%d] : %d\n", i, d[i]);
sum += d[i];
}
return sum;
}
};Time complexity :
O(E *(lg V)) : 與 Kruskal 相同。
假如 min-priority queue 是用 Fibonacci Heap 來實作，會更快。
Space complexity :
Guess : 原本應該只需 O(|V|) 的空間複雜度，但因為在這題，我又額外將它整理成 g，需要 O(|V| + |E|) 的空間複雜度。
( Optional ) graph : detected negative weight cycle in a weighted directed graph
graph : single-source shortest paths : The Bellman-Ford Algorithm
可處理有負邊，有負環的情況。
1. 初始化一個陣列 d，令 d[x]代表 起點 到 x點 的距離
2. 每一個有向邊， a->b ， d[a] 代表 起點 到 a點 的距離
d[b] 代表 起點 到 b點 的距離
令 |a->b| 代表有向邊 a->b 的長度
3. 假如 d[a] + |a->b| < d[b]，代表 起點 到 b點 有一個更短的捷徑
於是我們可以 d[b] = d[a] + |a->b|
這個過程就叫做 Relax
4. 遍尋一張圖的所有的邊，嘗試對每一個有向邊的終點進行 relax，就是一次的 bellman-ford 循環
5. 當一張圖有 v 個節點，我們就進行 v — 1 輪的 bellman-ford 循環。因為當圖上有 v 個節點的時候，從 src節點 到 dst節點，在”沒有負環的情況下”，最多會有 v — 1 個邊。
6. 假如當我們在第 v 輪仍能繼續 relax，代表該圖有負環，單源最短路徑為無限小。
example problems : LeetCode : 787. Cheapest Flights Within K Stops
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
vector<int> d1 = vector<int>(n, INT_MAX);
vector<int> d2 = vector<int>(n, INT_MAX);
d1[src] = 0;
d2[src] = 0;
for(int i = 0;i < K + 1;i++) {
for(int j = 0;j < flights.size();j++) {
if(d1[flights[j][0]] == INT_MAX) {
continue;
}
// 注意這邊要用 d2 去比，不然結果會被洗掉
if(d2[flights[j][1]] > d1[flights[j][0]] + flights[j][2]) {
d2[flights[j][1]] = d1[flights[j][0]] + flights[j][2];
}
}
for(int j = 0;j < d1.size();j++) {
d1[j] = d2[j];
}
}
return d1[dst] == INT_MAX ? -1 : d1[dst];
}
};explanation :
這題蠻妙的，原本 Bellmon-ford 會進行 |V |— 1 輪的 RELAX。而這裡只進行 K 輪的 RELAX，代表我們停了 K 站。
Time Complexity :
G: O(K * E)。原本的 Bellmon-ford 會是 O(V * E)，但這裡會用 K 去取代 V。
Space Complexity :
G: O(V + E)，會需要 adjacency-list 去記住這張圖。
此外還需要一張 unordered-map，用 O(V+E) 的空間去記錄每條 edge 的權重。需要 O(V) 去紀錄 v.d ( 從 source 到某點的距離。 )
graph : Single-Source Shortest Path : in directed acyclic graphs
Algorithm :
1. 拓樸排序，取得每一個點的拓樸排序順序
2. 依照拓樸排序的順序，對該點延伸出去的邊進行 RELAX
limitation :
不可以有環，只能在 directed acyclic graphs ( DAG )使用
Time Complexity :
O(V+E)
Space Complexity :
G : O(V) ， 需要保存每一個節點與 source 的距離。
graph : single-source shortest paths : Dijkstra’s Algorithm
預設邊沒有負數的權重
example problems : LeetCode : 1514. Path with Maximum Probability
// TODO : 效能太差
typedef struct Node Node;
struct Node {
int n; // node
double suc;
};
bool compare_node(Node &a, Node &b) {
return a.suc <= b.suc;
}
class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
unordered_map<int, double> um;
vector<double> d = vector<double>(n, 0);
unordered_map<int, vector<Node>> g;
vector<bool> visited = vector<bool>(n, false);
d[start] = 1;
for(int i = 0;i < edges.size();i++) {
g[edges[i][0]].push_back({edges[i][1], succProb[i]});
g[edges[i][1]].push_back({edges[i][0], succProb[i]});
}
// Max-Priority Queue
//priority_queue<Node, vector<Node>, bool (*)(Node &, Node &)> pq(compare_node);
priority_queue<Node, vector<Node>, decltype(&compare_node)> pq(compare_node);
pq.push({start, 1});
while(!pq.empty()) {
Node nown = pq.top();
pq.pop();
if (visited[nown.n]) {
continue;
}
vector<Node> &es = g[nown.n];
for(int i = 0;i < es.size();i++) {
// RELAX
if (d[nown.n] * es[i].suc > d[es[i].n]) {
d[es[i].n] = d[nown.n] * es[i].suc;
pq.push(es[i]);
}
}
}
return d[end];
}
};Time Complexity :
O((|E| + |V)|) * log(V)) — 因本例題使用二分堆來實作，假如使用 Fibonacci-heap 就可以更快。
Space Complexity :
TODO
note :
Dijkstra 的實作中，會需要使用到 min-priority queue，並且會需要減少在 queue 中間的元素的值。
然而在使用 C++ 解題時，會發現到 C++ 的 priority queue 並沒有這個操作。這時候可以簡單地做一個 workaround。 多次 Push 同一個節點進 priority-queue，並且在 pop 節點出來時，額外判斷該點是不是被 pop 過了。有被 pop 過就不要去處理它。
Question :
[1]假如有負邊，但沒有負環，該演算法也成立嗎？
Reference :
https://leetcode.com/problems/path-with-maximum-probability/solutions/732293/dijkstra-s-algorithm-implementation-c/
https://zh.wikipedia.org/zh-tw/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95#%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6
graph : All-Pairs Shortest Paths : The Floyd-Warshall algorithms
在一張圖中，有三個點，a, b, c，a → b → c。
g[a][b] 代表目前從 a 到 b 的最短距離，g[b][c] 代表目前從 b 到 c 的最短距離。
所以 g[a][b] + g[b][c] 會是 g[a][c] 其中一個可能的解法。
Floyd-Warshall 使用了三層迴圈，最外層迴圈去遍尋所有中間點 b，再來是遍尋所有的起點 a ，以及終點 c。
這個算法有三個點需要練習。
- 算出每個 pair 的最短路徑
- 能夠印出各個最短路徑上的每個節點
- 使用該算法計算出 Transitive Closure
example problem : LeetCode : 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
雖然這題沒有要求印出路徑，不過還是順便練習一下。
於是這題練習了 1. 算出每個 pair 的最短路徑，2.印出各個最短路徑上的每個節點。
// TODO : 效能太差
class Solution {
public:
void print_path(int x, int y, vector<vector<int>> &pg) {
if (x >= pg.size() ||
y >= pg.size()) {
printf("path not exist!\n");
return;
} else if (pg[x][y] == INT_MAX) {
printf("%d cannot reach %d\n", x, y);
return;
}
vector<int> v;
v.push_back(y);
while(pg[x][y] != x) {
v.push_back(pg[x][y]);
y = pg[x][y];
}
v.push_back(x);
for(int i = v.size() - 1;i >= 0;i--) {
printf("%d ", v[i]);
}
printf("\n");
}
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
vector<vector<int>> g = vector<vector<int>>(n, vector<int>(n, INT_MAX));
int ans = 0;
// predecessor graph
// just for practice
//vector<vector<int>> pg = vector<vector<int>>(n, vector<int>(n, INT_MAX));
for (int i = 0;i < edges.size();i++) {
// construct graph
g[edges[i][0]][edges[i][1]] = edges[i][2];
g[edges[i][1]][edges[i][0]] = edges[i][2];
// construct predecessor graph
/*
pg[edges[i][0]][edges[i][1]] = edges[i][0];
pg[edges[i][1]][edges[i][0]] = edges[i][1];
*/
}
// floyd-warshall
// 記得 k 要在最外面 ( TODO : 證明
for(int k = 0;k < n;k++) {
for(int i = 0;i < n;i++) {
for(int j = 0;j < n;j++) {
if (g[i][k] == INT_MAX ||
g[k][j] == INT_MAX) {
continue;
}
if (g[i][k] + g[k][j] < g[i][j]) {
g[i][j] = g[i][k] + g[k][j];
// 我猜：從 i 要到 j，需經過 i->k ， 再經過 k->j
// 所以從 i 要到 j 的前一站，會是 k->j
//pg[i][j] = pg[k][j];
}
}
}
}
int minVal = INT_MAX;
for(int i = 0;i < n;i++) {
int localnum = 0;
for(int j = 0;j < n;j++) {
if(i == j) {
continue;
}
if(g[i][j] <= distanceThreshold) {
localnum++;
}
}
if (localnum <= minVal) {
minVal = localnum;
ans = i;
}
}
// practice print path
/*
for(int i = 0;i < n;i++) {
for(int j = 0;j < n;j++) {
if(i == j) {
continue;
}
print_path(i, j, pg);
}
}
*/
return ans;
}
};Time Complexity :
O(|V|³)
Space Complexity :
G : O(|V|²) ， 需要有個二維陣列去存每個 pairs 的權重。
example problem : LeetCode. 1462. Course Schedule IV
這題應該就是 Transitive Closure 了，詢問點 A 是否到達的了點 B。
// Transitive closure ?
class Solution {
public:
vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
vector<vector<bool>> g = vector<vector<bool>>(numCourses, vector<bool>(numCourses, false));
vector<bool> ans;
for(int i = 0;i < prerequisites.size();i++) {
g[prerequisites[i][0]][prerequisites[i][1]] = true;
}
// floyd-warshall : transitive closure
for (int k = 0;k < numCourses;k++) {
for(int i = 0;i < numCourses;i++) {
for(int j = 0;j < numCourses;j++) {
g[i][j] = g[i][j] || (g[i][k] && g[k][j]);
}
}
}
for(int i = 0;i < queries.size();i++) {
if(g[queries[i][0]][queries[i][1]]) {
ans.push_back(true);
} else {
ans.push_back(false);
}
}
return ans;
}
};Time Complexity :
O(|V|³)
Space Complexity :
G : O(|V|²) ， 需要有個二維陣列去存每個 pairs 是否能抵達。
( Optional ) graph : All-Pairs Shortest Paths : Johnson’s algorithm for sparse graphs
相較於 Floyd-Warshall， Johnson’s algorithm 適用於稀疏的圖。
example problem : LeetCode : 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
graph : maximum flow : the ford-fulkerson method & the Edmonds-Karp algorithm
ford-fulkerson method : 先把原本的 graph 轉換成合法的 residual network，然後不斷的尋找 augmenting path，當 residual network 已經不存在 augmenting path 後，代表我們已經找到最大流了。此時只要計算從 source 節點往外流出的流量，就可以知道最大流的流量。
複雜度：O(|E| * |f|)， |f| 為最大流的流量， |E| 為邊的數量。
Edmonds-Karp algorithm :使用 BFS 去尋找 augmenting path。
複雜度： O(|E| * |V|²)
example problem : https://www.geeksforgeeks.org/maximum-bipartite-matching/
→ 內容與 `graph : maximum flow : maximum bipartite matching` 相同
example problem : https://leetcode.com/problems/maximum-students-taking-exam/description/ ??
→ 內容與 `graph : maximum flow : maximum bipartite matching` 相同
( Optional ) graph : maximum flow : Push-relabel algorithms
( Optional ) graph : maximum flow : The relabel-to-front algorithm
graph : maximum flow : maximum bipartite matching
class Solution {
public:
int maximumMatch(vector<vector<int>>&G){
vector<vector<vector<int>>> rg = vector<vector<vector<int>>>(G.size() + G[0].size() + 2);
for(int i = 0;i < G.size();i++) {
for(int j = 0;j < G[i].size();j++) {
rg[i].push_back({(int)G.size() + j, G[i][j]});
rg[G.size() + j].push_back({i, 0});
}
}
// add source into the residual graph
// source : G.size() + G[0].size()
// sink : G.size() + G[0].size() + 1
for(int i = 0;i < G.size();i++) {
rg[G.size() + G[0].size()].push_back({i, 1});
rg[i].push_back({(int)G.size() + (int)G[0].size(), 0});
}
// add sink into the residual graph
for(int i = 0;i < G[0].size();i++) {
rg[(int)G.size() + i].push_back({(int)G.size() + (int)G[0].size() + 1, 1});
rg[(int)G.size() + (int)G[0].size() + 1].push_back({(int)G.size() + i, 0});
}
while(1) {
// 1. BFS, find the augmenting path
queue<int> q;
vector<int> parent = vector<int>((int)G.size() + (int)G[0].size() + 2, -1);
parent[(int)G.size() + (int)G[0].size()] = G.size() + G[0].size();
q.push((int)G.size() + (int)G[0].size());
bool find_sink = false;
int nown;
while(!q.empty()) {
int nown = q.front();
q.pop();
for(int i = 0;i < rg[nown].size();i++) {
if(rg[nown][i][1] > 0 &&
parent[rg[nown][i][0]] == -1) {
q.push(rg[nown][i][0]);
parent[rg[nown][i][0]] = nown;
if(rg[nown][i][0] == G.size() + G[0].size() + 1) {
find_sink = true;
break;
}
}
}
if(find_sink) {
break;
}
}
if(!find_sink) {
break;
}
// 2. find the minimum value
// 因為題目的關係，所以每個 edge 的 capacity 都是 1
// 3. add the minimum value to residual graph
nown = G.size() + G[0].size() + 1;
while(nown != G.size() + G[0].size()) {
int pren = parent[nown];
for(int i = 0;i < rg[pren].size();i++) {
if(rg[pren][i][0] == nown) {
rg[pren][i][1]--;
break;
}
}
for(int i = 0;i < rg[nown].size();i++) {
if(rg[nown][i][0] == pren) {
rg[nown][i][1]++;
}
}
nown = pren;
}
}
// 4. get the answer
int ans = 0;
for(int i = 0;i < rg[G.size() + G[0].size() + 1].size();i++) {
ans += rg[G.size() + G[0].size() + 1][i][1];
}
return ans;
}
};
//// solution 2
class Solution {
public:
int maximumMatch(vector<vector<int>>&G){
vector<vector<int>> rn; // residual network
rn = vector<vector<int>> (G.size() + G[0].size() + 2,
vector<int>(G.size() + G[0].size() + 2, 0));
// bipartite graph
for (int i = 0;i < G.size();i++) {
for (int j = 0;j < G[0].size();j++) {
rn[i][G.size() + j] = G[i][j];
}
}
// source : G.size() + G[0].size()
// sink : G.size() + G[0].size() + 1
// add source
for (int i = 0;i < G.size();i++) {
rn[G.size() + G[0].size()][i] = 1;
}
// add sink
for (int i = 0;i < G[0].size();i++) {
rn[G.size() + i][G.size() + G[0].size() + 1] = 1;
}
while(1) {
vector<int> parent = vector<int>(G.size() + G[0].size() + 2, -1);
parent[G.size() + G[0].size()] = G.size() + G[0].size();
queue<int> q;
bool find_sink = false;
q.push(G.size() + G[0].size());
// BFS find the augmenting path
while(!q.empty()) {
int now = q.front();
q.pop();
if (now == (G.size() + G[0].size() + 1)) {
find_sink = true;
break;
}
for (int i = 0;i < rn[now].size();i++) {
if (rn[now][i] == 1 && parent[i] == -1) {
parent[i] = now;
q.push(i);
}
}
}
if (!find_sink) {
break;
}
// fix the value in the residual network
int now = G.size() + G[0].size() + 1;
int nowp;
while(now != (G.size() + G[0].size())) {
nowp = parent[now];
rn[nowp][now] -= 1;
rn[now][nowp] += 1;
now = nowp;
}
}
int ans = 0;
for (int i = 0;i < rn[0].size();i++) {
ans += rn[G.size() + G[0].size() + 1][i];
}
return ans;
}
};
// solution 3
int maximumMatch(vector < vector < int >> & G) {
int src = G.size() + G[0].size();
int dst = G.size() + G[0].size() + 1;
int rn_size = G.size() + G[0].size() + 2;
// residual network
vector < vector < int >> rn = vector < vector < int >> (rn_size, vector < int > (rn_size, 0));
for (int i = 0; i < G.size(); i++) {
for (int j = 0; j < G[0].size(); j++) {
rn[i][G.size() + j] = G[i][j];
}
}
// add source
for (int i = 0; i < G.size(); i++) {
rn[src][i] = 1;
}
// add dst
for (int i = 0; i < G[0].size(); i++) {
rn[G.size() + i][dst] = 1;
}
while (1) {
vector < int > parent = vector < int > (rn_size, -1);
queue < int > q;
bool find_dst = false;
q.push(src);
parent[src] = src;
// find augmenting path with BFS
while (!q.empty()) {
int nown = q.front();
q.pop();
for (int i = 0; i < rn[nown].size(); i++) {
if (rn[nown][i] > 0 &&
parent[i] == -1) {
parent[i] = nown;
q.push(i);
if (i == dst) {
find_dst = true;
break;
}
}
}
if (find_dst) {
break;
}
}
if (!find_dst) {
break;
}
int nown = dst;
while (parent[nown] != nown) {
rn[parent[nown]][nown] -= 1;
rn[nown][parent[nown]] += 1;
nown = parent[nown];
}
}
int ans = 0;
for (int i = G.size(); i < rn_size; i++) {
if (rn[dst][i] > 0) {
ans++;
}
}
return ans;
}Time Complexity :
Guess :
Ford-Fulkerson algorithm ( 在 CLRS 內由 Ford-Fulkerson method 衍生而來的演算法 ) : O(|E| * |f|)。其中 |f| 代表了最大流的值。因為每次尋找 augmenting path 需要對 graph 衍生出的 residual graph 進行一次 BFS 或是 DFS 。原本進行一次 DFS 或是 BFS 需要 O(|V| + |E|) 的時間複雜度。而因為目前是處理 maximum flow 問題下的圖，所以一次 DFS 或是 BFS 的時間複雜度為 O (|E|)。需要進行 |f| 次的 DFS 或是 BFS ，所以時間複雜度為 O(|E| * |f|)。
Edmons-Karp algorithm : O(|V| * |E|²)
在 Maximum Bipartite Match 的問題，我們只需要用到 Ford-Fulkerson algorithm 來看時間複雜度，因為在 Bipartite Graph下，|f| 最大為 O(|V|)，可得時間複雜度為 O(|V| * |E|)。
Space Complexity :
G : residual graph 需要 O(|V| + |E|) 的空間複雜度。
example problem : LeetCode : 1349. Maximum Students Taking Exam
這題是求該圖的 Maximum Independent Set。要尋找 Maximum Independent Set 是 NP-complete 問題，但假如該圖是 Bipartite Graph 的話，則可用 Maximum-Flow 的觀點去做，時間複雜度可以到 O(|V|*|E|)
從上圖可以看到，當我們求得 Maximum Bipartite match 的數量時，也同時取得 Maximum Independent Set 的數量。假如 N = 總點數， N — Maximum Bipartite Match 的數量 = Maximum Independent Set 的數量。因為每一個 Bipartite Match ，代表我們都必去要去掉一個點。
另外一個性質是 Maximum Bipartite Match 的數量 == Minimum Vertex Cover 的數量。( Kőnig’s theorem )
class Solution {
public:
int X[6] = {0, 0, -1, -1, 1, 1};
int Y[6] = {-1, 1, -1, 1, -1, 1};
int maxStudents(vector<vector<char>>& seats) {
int total_seat = 0;
int row = seats.size();
int col = seats[0].size();
int source = seats.size() * seats[0].size();
int sink = seats.size() * seats[0].size() + 1;
// residual graph
// 把 source 跟 sink 也都加進這張圖裡
// source : seats.size() * seats[0].size()
// sink : seats.size() * seats[0].size() + 1
vector<vector<vector<int>>> rg = vector<vector<vector<int>>>(seats.size() * seats[0].size() + 2);
// 將此圖視為一個 bipartite graph
// odd col 為一群，even col 為另外一群
// source 指向所有在 odd col 的節點
// 只需要將 odd col 指向 even col 即可，互指的話
// 會違反 maximum flow 的假設
for(int i = 0;i < seats.size();i++) {
for(int j = 0;j < seats[0].size();j++) {
if(seats[i][j] == '#') {
continue;
} else {
total_seat++;
}
if(j % 2 == 0) {
// 將 even col 指向 sink
rg[i * col + j].push_back({sink, 1});
rg[sink].push_back({i * col + j, 0});
} else {
// 將 source 指向 odd col
rg[source].push_back({i * col + j, 1});
rg[i * col + j].push_back({source, 0});
for(int k = 0;k < 6;k++) {
int nowx = i + X[k];
int nowy = j + Y[k];
// 將 odd col 指向 even col
if(nowx >= 0 && nowx < seats.size() &&
nowy >= 0 && nowy < seats[0].size() &&
seats[nowx][nowy] == '.') {
rg[i * col + j].push_back({nowx * col + nowy, 1});
rg[nowx * col + nowy].push_back({i * col + j, 0});
}
}
}
}
}
while(1) {
// BFS 尋找 augmenting path
vector<int> parent = vector<int>(seats.size() * seats[0].size() + 2, -1);
queue<int> q;
int nown;
bool find_sink = false;
q.push(source);
parent[source] = source;
while(!q.empty()) {
int nown = q.front();
q.pop();
for(int i = 0;i < rg[nown].size();i++) {
if(rg[nown][i][1] > 0 &&
parent[rg[nown][i][0]] == -1) {
parent[rg[nown][i][0]] = nown;
q.push(rg[nown][i][0]);
if(rg[nown][i][0] == sink) {
find_sink = true;
break;
}
}
}
if (find_sink) {
break;
}
}
if (!find_sink) {
break;
}
// 找出 path 上最小的 capacity
// --> 因為大家的 edge 都是 unit，所以一定會是 1
// 調整 residual graph
nown = sink;
while(nown != source) {
int pren = parent[nown];
for(int i = 0;i < rg[pren].size();i++) {
if(rg[pren][i][0] == nown) {
rg[pren][i][1]--;
break;
}
}
for(int i = 0;i < rg[nown].size();i++) {
if(rg[nown][i][0] == pren) {
rg[nown][i][1]++;
break;
}
}
nown = pren;
}
}
// 算出 Maximum bipartite match
int maximum_match = 0;
for(int i = 0;i < rg[sink].size();i++) {
maximum_match += rg[sink][i][1];
}
for(int i = 0;i < rg.size();i++) {
for(int j = 0;j < rg[i].size();j++) {
if(i < seats.size() * seats[0].size() &&
seats[i / col][i % col] == '#') {
continue;
}
}
}
// 解就是全部的空座位減掉 Maximum Bipartite Match 的數量
return total_seat - maximum_match;
}
};Time Complexity :
Guess : 令 |V| = seats.size() * seats[0].size(), |E| = odd col 連向 even col 的編的數目。
O (|V| * |E|)
Space Complexity :
Guess : 令 |V| = seats.size() * seats[0].size(), |E| = odd col 連向 even col 的編的數目。
O(|V| + |E|)
https://zh.wikipedia.org/wiki/%E9%9C%8D%E7%88%BE%E5%A9%9A%E9%85%8D%E5%AE%9A%E7%90%86
TODO :
[ — ] 延伸閱讀 Max Independent Set
[ — ] 延伸閱讀 Min Vertex Cover
graph : Hungarian Algorithm
example problem : LeetCode : 1349. Maximum Students Taking Exam
( Optional ) graph : maximum independent set
graph : Articulation Vertex
graph : Articulation Bridge
interval problems
這裡的大部分內容，都是參考自 https://hackmd.io/@wiwiho/cp-note/%2F%40wiwiho%2FCPN-range-query 。
interval problems : Prefix Sum ( 前綴和 )
適合使用在 “區間查詢，不會進行任何修改的情況”
限制：進行任何修改都會很慢
example problem : LeetCode 303. Range Sum Query — Immutable
class NumArray {
public:
vector<int> prefix_sum;
NumArray(vector<int>& nums) {
prefix_sum = vector<int>(nums.size());
int sum = 0;
for(int i = 0;i < nums.size();i++) {
sum += nums[i];
prefix_sum[i] = sum;
}
}
int sumRange(int left, int right) {
if(left == 0) {
return prefix_sum[right];
}
return prefix_sum[right] - prefix_sum[left - 1];
}
};Time Complexity :
初始化 : O(N)
查詢：O(1)
Space Complexity :
O(N)
interval problems : 差分序列
適合使用在 “只進行一次 (或少次) 查詢，並可頻繁進行區間修改的情況”
限制：進行任何查詢都會很慢
example problem : LeetCode : 370. Range Addition
class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> diff = vector<int>(length, 0);
vector<int> ans = vector<int>(length, 0);
for(int i = 0;i < updates.size();i++) {
diff[updates[i][0]] += updates[i][2];
if(updates[i][1] != length - 1) {
diff[updates[i][1] + 1] -= updates[i][2];
}
}
int sum = 0;
for(int i = 0;i < diff.size();i++) {
sum += diff[i];
ans[i] = sum;
}
return ans;
}
};Time Complexity :
區間修改：O(1)
單點查詢：O(N)
Space Complexity:
O(N)
interval problems : sparse table ( 稀疏表 )
適合使用在 “區間查詢，不會進行任何修改的情況”。可以發現這裡適用情況跟 Prefix Sum 很像，但 Prefix Sum 不好做區間最大值，但稀疏表可以。
限制：進行任何修改都會很慢
example problem : LeetCode : 239. Sliding Window Maximum
class Solution {
public:
int look_up(vector<vector<int>> &sparse_table, int left, int right) {
int k = floor(log2(right - left + 1));
int left_ans = sparse_table[left][k];
int right_ans = sparse_table[right - (1 << k) + 1][k];
return max(sparse_table[left][k],
sparse_table[right - (1 << k) + 1][k]);
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
int max_log = floor(log2(nums.size()));
// 記得 max_log 需要 + 1
vector<vector<int>> sparse_table = vector<vector<int>>(nums.size(), vector<int>(max_log + 1, 0));
// create sparse table
for(int i = 0;i < nums.size();i++) {
sparse_table[i][0] = nums[i];
}
for(int j = 1;j <= max_log;j++) {
for(int i = 0;i + (1 << (j - 1)) < nums.size();i++) {
sparse_table[i][j] = max(sparse_table[i][j - 1], sparse_table[i + (1 << (j - 1))][j - 1]);
}
}
for(int i = 0;i + k - 1 < nums.size();i++) {
ans.push_back(look_up(sparse_table, i, i + k - 1));
}
return ans;
}
};Time Complexity :
建立稀疏表 ：O(n * log (n))
區間查詢：O(1)
Space Complexity :
Guess : 稀疏表本身為 O(n * log(n))
example problem : ZeroJudge d539
我的寫法在大測資的時候會 TLE，再麻煩大神指點了 QQ
#include <iostream>
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
int n;
cin >> n;
vector<int> input(n, 0);
for(int i = 0;i < n;i++) {
cin >> input[i];
}
int len = n;
int max_log = floor(log2(n));
// create sparse table
vector<vector<int>> sparse_table = vector<vector<int>>(n, vector<int>(max_log + 1));
for (int i = 0; i < len; i++) {
sparse_table[i][0] = input[i];
}
for (int j = 1; j <= max_log; j++) {
for (int i = 0; i + (1 << (j - 1)) < len; i++) {
sparse_table[i][j] = max(sparse_table[i][j - 1],
sparse_table[i + (1 << (j - 1))][j - 1]);
}
}
cin >> n;
for(int i = 0;i < n;i++) {
int a, b;
int ans;
int k;
cin >> a;
cin >> b;
int left = min(a, b) - 1;
int right = max(a, b) - 1;
k = floor(log2(right - left + 1));
ans = max(sparse_table[left][k],
sparse_table[right - (1 << k) + 1][k]);
printf("%d\n", ans);
}
return 0;
}Time Complexity :
建立稀疏表 ：O(n * log (n))
區間查詢：O(1)
Space Complexity :
Guess : 稀疏表本身為 O(n * log(n))
Note :
[ — ] ‘⌊’ 是 floor function ( 下取整函數 )，對應到 C++ 內的 floor(x)，’⌈’ 是 ceiling function ( 上取整函數 )，對應到 C++ 內的 ceil(x)。
Question :
[ — ] 是不是能夠直接用 segment tree 取代？
Guess : 就查詢的效能來說，sparse table 還是勝過 segment tree 的。
Reference :
https://leetcode.com/problems/sliding-window-maximum/solutions/2671970/sparse-table/
interval problems : segment tree ( 線段樹 )
example problem : LeetCode : 307. Range Sum Query — Mutable
class NumArray {
private:
vector<int> segment_tree;
int input_size = 0;
// l, r : 代表目前該節點所代表的範圍
// vertex : 代表該節點的 index
void build_segment_tree(int l, int r, int vertex, vector<int> &nums) {
if(l == r) {
segment_tree[vertex] = nums[l];
return;
}
int mid = (l + r) / 2;
build_segment_tree(l, mid, vertex * 2 + 1, nums);
build_segment_tree(mid + 1, r, vertex * 2 + 2, nums);
segment_tree[vertex] = segment_tree[vertex * 2 + 1] + \
segment_tree[vertex * 2 + 2];
}
// l,r : 該節點所代表的範圍
void modifyOnePoint(int l, int r, int vertex, int pos, int val) {
// 當 l == r，代表我們找到了想要修改的節點。
if(l == r) {
segment_tree[vertex] = val;
return;
}
int mid = (l + r) / 2;
if(pos <= mid) {
modifyOnePoint(l, mid, vertex * 2 + 1, pos, val);
} else {
modifyOnePoint(mid + 1, r, vertex * 2 + 2, pos, val);
}
// 調整所有被修改的節點的祖先節點
segment_tree[vertex] = segment_tree[vertex * 2 + 1] + \
segment_tree[vertex * 2 + 2];
}
// nowl, nowr : vertex 所代表的範圍
// lookUpL, lookUpR : 想要搜索的範圍
int lookUpInterval(int nowl, int nowr, int vertex,
int lookUpL, int lookUpR) {
if(nowl == lookUpL && nowr == lookUpR) {
return segment_tree[vertex];
}
int mid = (nowl + nowr) / 2;
if(lookUpR <= mid) {
return lookUpInterval(nowl, mid, vertex * 2 + 1,
lookUpL, lookUpR);
} else if(lookUpL > mid) {
return lookUpInterval(mid + 1, nowr, vertex * 2 + 2,
lookUpL, lookUpR);
} else {
int res = lookUpInterval(nowl, mid, vertex * 2 + 1,
lookUpL, mid);
res += lookUpInterval(mid + 1, nowr, vertex * 2 + 2,
mid + 1, lookUpR);
return res;
}
return 0;
}
public:
NumArray(vector<int>& nums) {
input_size = nums.size();
segment_tree = vector<int>(4 * nums.size());
build_segment_tree(0, nums.size() - 1, 0, nums);
}
void update(int index, int val) {
modifyOnePoint(0, input_size - 1, 0, index, val);
}
int sumRange(int left, int right) {
return lookUpInterval(0, input_size - 1, 0,
left, right);
}
};Time Complexity :
建構 segment tree：O(N)
區間查詢 : O(log N)
單點修改：O(log N)
Space Complexity :
O(N)
interval problems : segment tree ( 線段樹 )+ lazy propagation ( 懶人標記 )
example problem : LeetCode 715. Range Module
typedef struct Node Node;
struct Node {
int val;
// 需要另外一個 bool 變數
// 去看現在有無 lazytag
// 因為假如只看 lazytag ， 會不知道是被設為 0 ，或是沒有 lazytag
bool islazy;
int lazytag;
Node *left;
Node *right;
};
class RangeModule {
public:
Node *sgt;
void modify(Node *nown, int nowl, int nowr,
int ml, int mr, int val) {
// nowl != nowr 代表非葉節點
if (nowl != nowr) {
if (!nown->left) {
nown->left = new Node();
}
if (!nown->right) {
nown->right = new Node();
}
} else {
// 已經到葉節點了
// 稍微思考一下會發現，當 nowl == nowr 的時候
// 理當 ml == mr && ml == nowl
nown->val = val;
nown->islazy = false;
return;
}
// lazytag propagate
if (nown->islazy) {
nown->val = nown->lazytag ? (nowr - nowl + 1) : 0;
nown->left->islazy = true;
nown->left->lazytag = nown->lazytag;
nown->right->islazy = true;
nown->right->lazytag = nown->lazytag;
nown->islazy = false;
}
if (nowl == ml &&
nowr == mr) {
nown->val = val ? (nowr - nowl + 1) : 0;
int mid = (nowl + nowr) / 2;
nown->left->islazy = true;
nown->left->lazytag = val;
nown->right->islazy = true;
nown->right->lazytag = val;
return;
}
// 遍尋左子樹以及右子樹
int mid = (nowl + nowr) / 2;
if (mr <= mid) {
modify(nown->left, nowl, mid, ml, mr, val);
} else if(ml > mid) {
modify(nown->right, mid + 1, nowr, ml, mr, val);
} else {
modify(nown->left, nowl, mid, ml, mid, val);
modify(nown->right, mid + 1, nowr, mid + 1, mr, val);
}
// 把左子樹跟右子樹的結果返回
int temp = 0;
if (nown->left->islazy) {
temp += nown->left->lazytag ? (mid - nowl + 1) : 0;
} else {
temp += nown->left->val;
}
if (nown->right->islazy) {
temp += nown->right->lazytag ? (nowr - (mid + 1) + 1) : 0;
} else {
temp += nown->right->val;
}
nown->val = temp;
}
int lookup(Node *nown, int nowl, int nowr, int ll, int lr) {
if (nowl != nowr) {
if (!nown->left) {
nown->left = new Node();
}
if (!nown->right) {
nown->right = new Node();
}
} else {
if (nown->islazy) {
nown->val = nown->lazytag;
nown->islazy = false;
}
return nown->val;
}
if (nown->islazy) {
nown->val = nown->lazytag ? (nowr - nowl + 1) : 0;
nown->left->islazy = true;
nown->left->lazytag = nown->lazytag;
nown->right->islazy = true;
nown->right->lazytag = nown->lazytag;
nown->islazy = false;
}
if (nowl == ll &&
nowr == lr) {
return nown->val;
}
int mid = (nowl + nowr) / 2;
if (lr <= mid) {
return lookup(nown->left, nowl, mid,
ll, lr);
} else if(ll > mid) {
return lookup(nown->right, mid + 1, nowr,
ll, lr);
}
return lookup(nown->left, nowl, mid, ll, mid) +
lookup(nown->right, mid + 1, nowr, mid + 1, lr);
}
RangeModule() {
sgt = new Node();
}
void addRange(int left, int right) {
modify(sgt, 0, 1000000000,
left, right - 1, 1);
}
bool queryRange(int left, int right) {
int ans = lookup(sgt, 0, 1000000000,
left, right - 1);
return ans == right - left;
}
void removeRange(int left, int right) {
modify(sgt, 0, 1000000000,
left, right - 1, 0);
}
};
/**
* Your RangeModule object will be instantiated and called as such:
* RangeModule* obj = new RangeModule();
* obj->addRange(left,right);
* bool param_2 = obj->queryRange(left,right);
* obj->removeRange(left,right);
*/Time Complexity :
建構 segment tree：O(N)
區間查詢 : O(log N)
單點修改：O(log N)
區間修改：O(log N)
Space Complexity :
O(N)
example problem : zeroJudge d799
TODO :
[ — ] 效能太差了，需要研究一下其他人是怎麼實作 lazy propagate 的。
[ — ] 理解 segment tree & lazy propagate 的原理。
interval problems : multi-dimensional segment tree (多維線段樹)
example problem : leetcode 308. Range Sum Query 2D — Mutable
Time Complexity :
xxx
Space Complexity :
xxx
interval problems : Binary Indexed Tree ( fenwick tree )
example problem : leetcode 307 Range Sum Query — Mutable
// 取得最小的 BIT
// e.g. LOWBIT(0b110100)，返回值會是 (0b100)
#define LOWBIT(x) (x & -x)
class NumArray {
private:
vector<int> orig;
vector<int> bit;
void __modify(int pos, int diff, vector<int> &bit) {
for(;pos < bit.size();pos += LOWBIT(pos)) {
bit[pos] += diff;
}
}
void modify(int pos, int val, vector<int> &orig, vector<int> &bit) {
int diff = val - orig[pos];
orig[pos] = val;
pos += 1;
__modify(pos, diff, bit);
}
int query(int pos, vector<int> &bit) {
pos += 1;
int res = 0;
for(;pos >= 1;pos -= LOWBIT(pos)) {
res += bit[pos];
}
return res;
}
void initialize(vector<int> &orig, vector<int> &bit) {
for(int i = 0;i < orig.size();i++) {
__modify(i + 1, orig[i], bit);
}
}
public:
NumArray(vector<int>& nums) {
orig = nums;
bit = vector<int>(orig.size() + 1, 0);
initialize(orig, bit);
}
void update(int index, int val) {
modify(index, val, orig, bit);
}
int sumRange(int left, int right) {
if(left == 0) {
return query(right, bit);
}
return query(right, bit) - query(left - 1, bit);
}
};Time Complexity :
建構 BIT : O(N * log(N))
單點修改：O(log(N))
前綴和查詢：O(log(N))
Space Complexity :
O(N)
interval problems : Binary Indexed Tree ( fenwick tree ) + 動態開點
example problem : LeetCode : 493. Reverse Pairs
// 動態開點線段樹 + 單點修改
// 每次都看看，在此之前有多少大於 nums[i] * 2 的數
// 加起來就是解
#define LL long long
#define BASE 2147483649LL
#define MAXVAL (BASE * 2)
#define LOWBIT(x) ((x) & (-x))
class Solution {
private:
unordered_map<LL, int> bit;
void modify(LL pos, LL val) {
for(LL i = pos;i <= MAXVAL;i += LOWBIT(i)) {
bit[i] += val;
}
}
LL query(LL pos) {
LL tmp = 0;
for(LL i = pos;i > 0;i -= LOWBIT(i)) {
tmp += bit[i];
}
return tmp;
}
public:
int reversePairs(vector<int>& nums) {
int res = 0;
for(LL i = 0;i < nums.size();i++) {
res += (query(MAXVAL) - query(((LL)nums[i] * 2 + BASE)));
modify(nums[i] + BASE, 1);
}
return res;
}
};Time Complexity :
xxx
Space Complexity :
xxx
interval problems : Binary Indexed Tree ( fenwick tree ) + 差分序列
example problem : LeetCode : 307. Range Sum Query — Mutable
Time Complexity :
xxx
Space Complexity :
xxx
Reference :
BIT + 差分序列 : https://fdgkhdkgh.medium.com/algorithms-data-structures-%E5%8D%80%E9%96%93%E5%95%8F%E9%A1%8C%E9%9B%86%E9%8C%A6-4-binary-indexed-tree-fenwick-tree-d00a986f3072
interval problems : multi-dimensional Binary Indexed Tree
example problem : LeetCode 308. Range Sum Query 2D — Mutable
#define LOWBIT(x) (x & -x)
class NumMatrix {
public:
vector<vector<int>> bit;
vector<vector<int>> ori;
void __modify(int x, int y, int diff) {
for (int i = x;i < bit.size();i += LOWBIT(i)) {
for (int j = y;j < bit[0].size();j += LOWBIT(j)) {
bit[i][j] += diff;
}
}
}
void modify(int x, int y, int val) {
int diff = val - ori[x][y];
ori[x][y] = val;
x++;
y++;
__modify(x, y, diff);
}
int lookup(int x, int y) {
int ans = 0;
x++;
y++;
for (int i = x;i >= 1;i -= LOWBIT(i)) {
for (int j = y;j >= 1;j -= LOWBIT(j)) {
ans += bit[i][j];
}
}
return ans;
}
NumMatrix(vector<vector<int>>& matrix) {
bit = vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
ori = matrix;
for (int i = 0;i < matrix.size();i++) {
for (int j = 0;j < matrix[0].size();j++) {
__modify(i + 1, j + 1, matrix[i][j]);
}
}
}
void update(int row, int col, int val) {
modify(row, col, val);
}
int sumRegion(int row1, int col1, int row2, int col2) {
int a = lookup(row2, col2);
int b = lookup(row1 - 1, col1 - 1);
int c = lookup(row2, col1 - 1);
int d = lookup(row1 - 1, col2);
return (a + b) - (c + d);
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* obj->update(row,col,val);
* int param_2 = obj->sumRegion(row1,col1,row2,col2);
*/Time Complexity :
Update : O(log(N) * log (M))
Query : O(log(N) * log(M))
Build : O(N * M * log(N) * log (M))
Space Complexity :
O(N * M)
Binary Search
example problems : LeetCode 704. Binary Search ( easy )
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};example problems : LeetCode 1011. Capacity To Ship Packages Within D Days
class Solution {
public:
int count_days(vector<int>& weights, int w) {
int now_sum = 0;
int d = 0;
for (int i = 0;i < weights.size();i++) {
if (weights[i] > w) {
return INT_MAX;
}
now_sum += weights[i];
if (now_sum == w) {
d++;
now_sum = 0;
} else if(now_sum > w) {
d++;
now_sum = weights[i];
}
}
if (now_sum > 0) {
d++;
}
return d;
}
int shipWithinDays(vector<int>& weights, int days) {
int left = 0;
int right = weights.size() * 500 + 1;
while(left < right) {
int mid = (left + right) / 2;
int d = count_days(weights, mid);
if (d <= days) {
right = mid;
} else {
left = mid + 1;
}
}
// 終止條件設為 right
// 原因是 right 始終會是可行的解 ( d <= days )
// 且在最後，會是可行解中， d 最逼近 days 的那個
return right;
}
};example problems : LeetCode 4. Median of Two Sorted Arrays
example problems : LeetCode 2187. Minimum Time to Complete Trips ( medium )
// medium or hard ... ?
#define LL long long
class Solution {
public:
long long minimumTime(vector<int>& time, int totalTrips) {
LL left = 0;
LL right = 0;
for (int i = 0;i < time.size();i++) {
right = max(right, (LL)time[i]);
}
right *= totalTrips;
while (left <= right) {
LL mid = (left + right) / 2;
LL tmp = 0;
for (int i = 0;i < time.size();i++) {
tmp += mid / time[i];
}
if (tmp >= totalTrips) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
};example problems : LeetCode 540. Single Element in a Sorted Array
Dynamic Programming
DP : rod cutting
example problem : https://blog.csdn.net/csdnLeoMa/article/details/100523476
/*
問題描述: 有一根鋼條長 n ， 且有一個陣列 p， p[i] 等於長度為 i 的鋼條可以賣多少錢
求長度為 n 的鋼條，最多能賣多少錢
*/
vector<int> r = vector<int>(n, INT_MIN);
int cut_rod(p, n) {
if (n == 0) {
return 0;
}
if (r[n] >=0) {
return r[n];
}
int q = INT_MIN;
for (int i = 1;i < n;i++) {
q = max(q, p[i] + cut_rod(p, n - i));
}
r[n] = q;
return q;
}
DP : 0/1 knapsack problem
Reference :
[ — ] https://web.ntnu.edu.tw/~algo/KnapsackProblem.html
/*
問題描述：背包重量有限，每件物品都有其重量以及價值
嘗試拿走最大價值的物品組合。
*/
// n 代表目前是第幾個物品。
// w 代表目前背包還能裝多少重量的東西。
// weight[n] 代表第 n 個物品的重量。
// cost[n] 代表第 n 個物品的價值。
c(n, w) = max( c(n-1, w), c(n-1, w-weight[n]) + cost[n] )DP : Longest Common Subsequence
example problem : LeetCode : 1143. Longest Common Subsequence
class Solution {
public:
int dfs(int i1, int i2, string &t1, string &t2, vector<vector<int>> &dp) {
if (i1 < 0|| i2 < 0) {
return 0;
} else if (dp[i1][i2] != INT_MIN) {
return dp[i1][i2];
}
dp[i1][i2] = dfs(i1 - 1, i2, t1, t2, dp);
dp[i1][i2] = max(dp[i1][i2], dfs(i1, i2 - 1, t1, t2, dp));
if (t1[i1] == t2[i2]) {
dp[i1][i2] = max(dp[i1][i2], dfs(i1 - 1, i2 - 1, t1, t2, dp) + 1);
}
return dp[i1][i2];
}
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp = vector<vector<int>>(text1.size(), vector<int>(text2.size(), INT_MIN));
return dfs(text1.size() - 1, text2.size() - 1, text1, text2, dp);
}
};( Optional ) DP : matrix-chain multiplication
misc
example problem : LeetCode 5. Longest Palindromic Substring
/*
這是 O(N^2) 的解法，應可更快，有 O(N) 的解法
*/
class Solution {
public:
int maxval = 0;
int maxleft = -1;
int maxright = -1;
int dfs(int left, int right, string &s, vector<vector<int>> &dp) {
if (left > right) {
dp[left][right] = 0;
return 0;
} else if (left == right) {
dp[left][right] = 1;
if (dp[left][right] > maxval) {
maxval = dp[left][right];
maxleft = left;
maxright = right;
}
return 1;
} else if (left == right - 1 &&
s[left] == s[right]) {
dp[left][right] = 2;
if (dp[left][right] > maxval) {
maxval = dp[left][right];
maxleft = left;
maxright = right;
}
return 2;
}
if(dp[left][right] != -1) {
return dp[left][right];
}
dfs(left, right - 1, s, dp);
dfs(left + 1, right, s, dp);
if (s[left] == s[right]) {
int tmp = dfs(left + 1, right - 1, s, dp);
if (tmp == 0) {
dp[left][right] = 0;
} else {
dp[left][right] = tmp + 2;
}
} else {
dp[left][right] = 0;
}
if (dp[left][right] > maxval) {
maxval = dp[left][right];
maxleft = left;
maxright = right;
}
return dp[left][right];
}
string longestPalindrome(string s) {
vector<vector<int>> dp = vector<vector<int>>(s.size(), vector<int>(s.size(), -1));
dfs(0, s.size() - 1, s, dp);
return s.substr(maxleft, maxright - maxleft + 1);
}
};example problem : LeetCode 516. Longest Palindromic Subsequence
/*
TODO: 空間還能更加優化。
*/
class Solution {
public:
int ans = INT_MIN;
int dfs(int left, int right, vector<vector<int>> &dp, string &s) {
if (left > right) {
dp[left][right] = 0;
return 0;
} else if (left == right) {
dp[left][right] = 1;
ans = max(ans, 1);
return 1;
} else if (left == right - 1 &&
s[left] == s[right]) {
dp[left][right] = 2;
ans = max(ans, 2);
return 2;
} else if (dp[left][right] != INT_MIN) {
return dp[left][right];
}
int tmp = 0;
if (s[left] == s[right]) {
dp[left][right] = dfs(left + 1, right - 1, dp, s) + 2;
}
dp[left][right] = max(dp[left][right], dfs(left + 1, right, dp, s));
dp[left][right] = max(dp[left][right], dfs(left, right - 1, dp, s));
ans = max(ans, dp[left][right]);
return dp[left][right];
}
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp = vector<vector<int>> (s.size(), vector<int>(s.size(), INT_MIN));
dfs(0, s.size() - 1, dp, s);
return ans;
}
};example problems : LeetCode 300. Longest Increasing Subsequence
/*
dp property
1. First, we need some function or array that represents the answer to the problem from a given state.
2. We need a way to transition between states
3. We need a base case.
TODO : 有更複雜的算法可壓低時間複雜度
*/
class Solution {
public:
int ans = 1;
int dfs(int n, vector<int> &dp, vector<int> &nums) {
if (dp[n] > 0) {
return dp[n];
}
int tmp = 0;
for (int i = n - 1;i >= 0;i--) {
if (nums[n] > nums[i]) {
tmp = max(tmp, dfs(i, dp, nums));
}
}
dp[n] = tmp + 1;
ans = max(ans, dp[n]);
return dp[n];
}
int lengthOfLIS(vector<int>& nums) {
vector<int> dp = vector<int>(nums.size(), 0);
dp[0] = 1;
for (int i = 1;i < nums.size();i++) {
dfs(i, dp, nums);
}
return ans;
}
};example problem : LeetCode121. Best Time to Buy and Sell Stock
class Solution {
public:
int maxProfit(vector<int>& prices) {
int min_val = prices[0];
int max_profit = 0;
for (int i = 0;i < prices.size();i++) {
min_val = min(min_val, prices[i]);
max_profit = max(max_profit, prices[i] - min_val);
}
return max_profit;
}
};example problem : LeetCode 122. Best Time to Buy and Sell Stock II
example problem : LeetCode 123. Best Time to Buy and Sell Stock III
example problem : LeetCode 188. Best Time to Buy and Sell Stock IV
example problem : LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
example problem : LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee
example problem : LeetCodee 322. Coin Change
// TODO : 好慢...
class Solution {
public:
int dfs(int nown, vector<int> &coins, int amount, vector<vector<int>> &dp) {
if (dp[nown][amount] != INT_MAX) {
return dp[nown][amount];
} else if (nown == 0) {
if (amount % coins[nown] != 0) {
// -1 代表沒辦法完全找開
dp[nown][amount] = -1;
return dp[nown][amount];
}
dp[nown][amount] = amount / coins[nown];
return dp[nown][amount];
}
int base = 0;
int n = 0;
int minval = INT_MAX;
while (base <= amount) {
int tmp = dfs(nown - 1, coins, amount - base, dp);
if (tmp != -1) {
minval = min(minval, tmp + n);
}
base += coins[nown];
n++;
}
dp[nown][amount] = (minval == INT_MAX ? -1 : minval);
return dp[nown][amount];
}
int coinChange(vector<int>& coins, int amount) {
vector<vector<int>> dp = vector<vector<int>>(coins.size(), vector<int>(amount + 1, INT_MAX));
int ans = dfs(coins.size() - 1, coins, amount, dp);
return ans;
}
};example problem : LeetCode 2218. Maximum Value of K Coins From Piles
example problem : LeetCode 42. Trapping Rain Water
class Solution {
public:
// dynamic programming
int trap(vector<int>& height) {
// 從左邊看過來最高點
vector<int> fromleft = vector<int>(height.size(), 0);
// 從右邊看過來最高點
vector<int> fromright = vector<int>(height.size(), 0);
int ans = 0;
int nowmax = 0;
for (int i = 0;i < height.size();i++) {
nowmax = max(nowmax, height[i]);
fromleft[i] = nowmax;
}
nowmax = 0;
for (int i = height.size() - 1;i >= 0;i--) {
nowmax = max(nowmax, height[i]);
fromright[i] = nowmax;
}
for (int i = 0;i < height.size();i++) {
ans += min(fromleft[i], fromright[i]) - height[i];
}
return ans;
}
};example problem : LeetCode 53. Maximum Subarray
example problem : LeetCode 22. Generate Parentheses
example problem : LeetCode 70. Climbing Stairs
example problem : LeetCode 926. Flip String to Monotone Increasing
example problem : LeetCode 1626. Best Team With No Conflicts
example problem : LeetCode 198. House Robber
example problem : LeetCode 790. Domino and Tromino Tiling
example problem : LeetCode 446. Arithmetic Slices II — Subsequence
example problem : LeetCode 834. Sum of Distances in Tree
example problem : LeetCode 279. Perfect Squares
example problem : LeetCode 416. Partition Equal Subset Sum
example problem : LeetCode : 343. Integer Break
example problem : LeetCode : 1547. Minimum Cost to Cut a Stick
example problem : LeetCode : 887. Super Egg Drop
Greedy
Divide and Conquer
String
example problem : LeetCode13. Roman to Integer
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> um;
um['I'] = 1;
um['V'] = 5;
um['X'] = 10;
um['L'] = 50;
um['C'] = 100;
um['D'] = 500;
um['M'] = 1000;
vector<int> sta;
for (int i = 0;i < s.size();i++) {
int nowval = um[s[i]];
while (!sta.empty() &&
nowval > sta.back()) {
nowval -= sta.back();
sta.pop_back();
}
sta.push_back(nowval);
}
int ans = 0;
while(!sta.empty()) {
ans += sta.back();
sta.pop_back();
}
return ans;
}
};example problem : LeetCode3. Longest Substring Without Repeating Characters
class Solution {
public:
int lengthOfLongestSubstring(string s) {
queue<char> q;
vector<int> num = vector<int>(256, 0);
int ans = 0;
for (int i = 0;i < s.size();i++) {
q.push(s[i]);
num[s[i]]++;
while(num[s[i]] > 1) {
num[q.front()]--;
q.pop();
}
ans = max(ans, (int)q.size());
}
return ans;
}
};example problem : LeetCode412. Fizz Buzz
example problem : LeetCode926. Flip String to Monotone Increasing
example problem : LeetCode22. Generate Parentheses
example problem : LeetCode273. Integer to English Words
example problem : LeetCode899. Orderly Queue
example problem : LeetCode93. Restore IP Addresses
example problem : LeetCode49. Group Anagrams
example problem : LeetCode68. Text Justification
example problem : LeetCode212. Word Search II
example problem : LeetCode6. Zigzag Conversion
example problem : LeetCode17. Letter Combinations of a Phone Number
example problem : LeetCode2306. Naming a Company
Hash
hash table
example problem : LeetCode1010. Pairs of Songs With Total Durations Divisible by 60
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
vector<int> t = vector<int> (501, 0);
int ans = 0;
for(int i = 0;i < time.size();i++) {
t[time[i]]++;
}
for (int i = 1;i <= 500;i++) {
int base = 60;
while(base <= 1000) {
int target = base - i;
if (target >= 1 &&
target <= 500 &&
target >= i) {
if (target == i) {
long long tmp = ((long long)t[i] * (long long)(t[i] - 1)) / 2;
ans += tmp;
} else {
ans += t[target] * t[i];
}
}
base += 60;
}
}
return ans;
}
};example problem : LeetCode2244. Minimum Rounds to Complete All Tasks
example problem : LeetCode149. Max Points on a Line
example problem : LeetCode974. Subarray Sums Divisible by K
example problem : LeetCode904. Fruit Into Baskets
example problem : LeetCode2306. Naming a Company
example problem : LeetCode433. Minimum Genetic Mutation
example problem : LeetCode491. Non-decreasing Subsequences
example problem : LeetCode1443. Minimum Time to Collect All Apples in a Tree
hash function
example problem : LeetCode706. Design HashMap
example problem : LeetCode1960. Maximum Product of the Length of Two Palindromic Substrings
rolling hash
example problem : LeetCode1044. Longest Duplicate Substring
example problem : LeetCode718. Maximum Length of Repeated Subarray
Stack / Queue
stack
example problem : LeetCode 20. Valid Parentheses
class Solution {
public:
bool isValid(string s) {
vector<char> st;
for(int i = 0;i < s.size();i++) {
if (s[i] == '(' ||
s[i] == '[' ||
s[i] == '{') {
st.push_back(s[i]);
} else {
if (st.empty()) {
return false;
}
if (s[i] == ')') {
if (st.back() == '(') {
st.pop_back();
} else {
return false;
}
} else if (s[i] == ']') {
if (st.back() == '[') {
st.pop_back();
} else {
return false;
}
} else if (s[i] == '}') {
if (st.back() == '{') {
st.pop_back();
} else {
return false;
}
}
}
}
return st.size() == 0 ? true : false;
}
};example problem : LeetCode394. Decode String
example problem : LeetCode234. Palindrome Linked List
example problem : LeetCode1472. Design Browser History
stack : monotonic stack
example problem : LeetCode42. Trapping Rain Water
class Solution {
public:
// monotonic stack
// vector<pair<int, int>> sta;
// pair<高度, 該高度的數量>
int trap(vector<int>& height) {
vector<pair<int, int>> sta;
int ans = 0;
for (int i = 0;i < height.size();i++) {
vector<pair<int, int>> tmp;
int maxval = 0;
// 蒐集比自己矮或是等高的
while (!sta.empty() &&
sta.back().first <= height[i]) {
maxval = max(maxval, sta.back().first);
tmp.push_back(sta.back());
sta.pop_back();
}
// 假如最後會遇到比自己高的，則
// 在田雨水的時候，用自己的高度為基準
if (!sta.empty() &&
sta.back().first > height[i]) {
maxval = height[i];
}
// 填雨水與求解
int nown = 1;
for (int j = 0;j < tmp.size();j++) {
ans += (maxval - tmp[j].first) *
tmp[j].second;
nown += tmp[j].second;
}
sta.push_back({height[i], nown});
}
return ans;
}
};example problem : LeetCode907. Sum of Subarray Minimums
example problem : LeetCode739. Daily Temperatures
example problem : LeetCode84. Largest Rectangle in Histogram
example problem : LeetCode901. Online Stock Span
queue
example problem : LeetCode362. Design Hit Counter
class HitCounter {
public:
queue<int> q;
HitCounter() {
}
void hit(int timestamp) {
q.push(timestamp);
}
int getHits(int timestamp) {
while(!q.empty() &&
q.front() + 300 <= timestamp) {
q.pop();
}
return q.size();
}
};
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter* obj = new HitCounter();
* obj->hit(timestamp);
* int param_2 = obj->getHits(timestamp);
*/example problem : LeetCode387. First Unique Character in a String
queue : monotonic
example problem : LeetCode2444. Count Subarrays With Fixed Bounds
example problem : LeetCode239. Sliding Window Maximum
example problem : LeetCode918. Maximum Sum Circular Subarray
example problem : LeetCode1499. Max Value of Equation
Priority-Queue
example problem : LeetCode1834. Single-Threaded CPU
#define LL long long
bool compare_pq (vector<int> &a, vector<int> &b) {
if (a[1] == b[1]) {
return a[2] >= b[2];
}
return a[1] > b[1];
}
class Solution {
public:
LL global_time = 1;
vector<int> getOrder(vector<vector<int>>& tasks) {
// 需要有個 global t ， 代表目前時間是多少了
// task 需要被 enqueue time 給 排序
// pq 需要先排序 task lenght ， 再被 index 排序
vector<vector<int>> t_enqueue_t;
priority_queue<vector<int>, vector<vector<int>>, decltype(&compare_pq)> pq(compare_pq);
vector<int> ans;
for (int i = 0;i < tasks.size();i++) {
t_enqueue_t.push_back({tasks[i][0], tasks[i][1], i});
/*
0 : enqueue time
1 : task time
2 : task index
*/
}
sort(t_enqueue_t.begin(), t_enqueue_t.end());
int t_enqueue_t_i = 0;
while (t_enqueue_t_i < t_enqueue_t.size()) {
pq.push(t_enqueue_t[t_enqueue_t_i]);
global_time = t_enqueue_t[t_enqueue_t_i][0];
t_enqueue_t_i++;
while(!pq.empty()) {
vector<int> now = pq.top();
pq.pop();
ans.push_back(now[2]);
global_time += (LL)now[1];
while(t_enqueue_t_i < t_enqueue_t.size() &&
(LL)t_enqueue_t[t_enqueue_t_i][0] <= global_time) {
pq.push(t_enqueue_t[t_enqueue_t_i++]);
}
}
}
return ans;
}
};example problem : LeetCode912. Sort an Array
example problem : LeetCode1675. Minimize Deviation in Array
example problem : LeetCode253. Meeting Rooms II
example problem : LeetCode502. IPO
linked-list
linked-list : LRU ( Least Recently Used ) Cache
example problems : LeetCode 146. LRU Cache
typedef struct Node Node;
struct Node {
int val;
int key;
Node *pre;
Node *next;
};
class LRUCache {
public:
Node *head = NULL;
int capa;
int now_capa = 0;
unordered_map<int, Node *> key2Node;
void insertHead(Node *n) {
if(!head) {
head = n;
head->next = head;
head->pre = head;
return;
}
Node *next = head;
Node *pre = head->pre;
n->next = next;
n->pre = pre;
pre->next = n;
next->pre = n;
/* 記得要更新 head */
head = n;
}
void removeNode(Node *n) {
Node *pre = n->pre;
Node *next = n->next;
if (pre == n) {
head = NULL;
}
pre->next = next;
next->pre = pre;
/* 記得要更新 head */
if (n == head) {
head = next;
}
}
LRUCache(int capacity) {
capa = capacity;
}
int get(int key) {
if (key2Node.find(key) == key2Node.end()) {
return -1;
}
Node *n = key2Node[key];
removeNode(n);
insertHead(n);
return n->val;
}
void put(int key, int value) {
if (key2Node.find(key) == key2Node.end()) {
Node *n = new Node();
n->val = value;
n->key = key;
key2Node[key] = n;
now_capa++;
insertHead(n);
if (now_capa > capa) {
Node *remove_node = n->pre;
removeNode(remove_node);
key2Node.erase(remove_node->key);
delete remove_node;
now_capa--;
}
} else {
Node *n = key2Node[key];
n->val = value;
removeNode(n);
insertHead(n);
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/linked-list : Cycle Detection : Floyd’s Cycle Finding Algorithm
→ 這部分在 graph : Cycle Detection : Floyd’s Cycle Finding Algorithm 有提到過了。
Misc
example problems : LeetCode 206. Reverse Linked List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) {
return NULL;
} else if (head->next == NULL) {
return head;
}
ListNode *pre = NULL;
ListNode *now = head;
ListNode *next = head->next;
while(now != NULL) {
now->next = pre;
pre = now;
now = next;
if (next) {
next = next->next;
}
}
return pre;
}
};example problems : LeetCode 2. Add Two Numbers
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = NULL;
ListNode *phead = NULL;
ListNode *pl1 = l1;
ListNode *pl2 = l2;
bool carry = false;
while(pl1 && pl2) {
ListNode *newn = new ListNode();
newn->val = pl1->val + pl2->val;
if (carry) {
newn->val++;
}
if (newn->val >= 10) {
newn->val -= 10;
carry = true;
} else {
carry = false;
}
if (head == NULL) {
head = newn;
phead = newn;
} else {
phead->next = newn;
phead = phead->next;
}
pl1 = pl1->next;
pl2 = pl2->next;
}
while (pl1) {
ListNode *newn = new ListNode();
newn->val = pl1->val;
if (carry) {
newn->val++;
}
if (newn->val >= 10) {
carry = true;
newn->val -= 10;
} else {
carry = false;
}
if (head == NULL) {
head = newn;
phead = newn;
} else {
phead->next = newn;
phead = phead->next;
}
pl1 = pl1->next;
}
while (pl2) {
ListNode *newn = new ListNode();
newn->val = pl2->val;
if (carry) {
newn->val++;
}
if (newn->val >= 10) {
carry = true;
newn->val -= 10;
} else {
carry = false;
}
if (head == NULL) {
head = newn;
phead = newn;
} else {
phead->next = newn;
phead = phead->next;
}
pl2 = pl2->next;
}
if (carry) {
ListNode *newn = new ListNode();
newn->val = 1;
phead->next = newn;
}
return head;
}
};example problems : LeetCode 21. Merge Two Sorted Lists
example problems : LeetCode 23. Merge k Sorted Lists
example problems : LeetCode 460. LFU Cache
example problems : LeetCode 234. Palindrome Linked List
example problems : LeetCode 1472. Design Browser History
example problems : LeetCode 328. Odd Even Linked List
example problems : LeetCode 876. Middle of the Linked List
Two Pointers
example problem : LeetCode1. Two Sum
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int, int>> ns;
for(int i = 0;i < nums.size();i++) {
ns.push_back({nums[i], i});
}
sort(ns.begin(), ns.end());
int left = 0;
int right = nums.size() - 1;
while(left < right) {
int tmp = ns[left].first + ns[right].first;
if (tmp == target) {
return {ns[left].second, ns[right].second};
} else if (tmp > target) {
right--;
} else {
left++;
}
}
return {};
}
};example problems : LeetCode 167. Two Sum II — Input Array Is Sorted
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size() - 1;
while (left < right) {
int tmp = numbers[left] + numbers[right];
if (tmp == target) {
return {left + 1, right + 1};
} else if (tmp > target) {
right--;
} else {
left++;
}
}
return {};
}
};example problems : LeetCode15. 3Sum
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0;i < nums.size() - 2;i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = nums[i] * -1;
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int tmp = nums[left] + nums[right];
if (tmp == target) {
ans.push_back({nums[i], nums[left], nums[right]});
left++;
// 避免重複選用相同的解
while (left < right &&
nums[left] == nums[left - 1]) {
left++;
}
} else if (tmp > target) {
right--;
} else {
left++;
}
}
}
return ans;
}
};example problems : LeetCode42. Trapping Rain Water
example problems : LeetCode31. Next Permutation
class Solution {
public:
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void reverse(int left, int right, vector<int> &nums) {
while(left < right) {
swap(&nums[left], &nums[right]);
left++;
right--;
}
}
void nextPermutation(vector<int>& nums) {
for (int i = nums.size() - 1;i >= 1;i--) {
// 1. 找出遞減的區間
if (nums[i - 1] < nums[i]) {
// 2. 在遞減的區間中，找出略大於自己的數
int j = nums.size() - 1;
while(nums[i - 1] >= nums[j]) j--;
swap(&nums[i - 1], &nums[j]);
// 3. 將原本遞減的區間進行排序，變成遞增
reverse(i, nums.size() - 1, nums);
return;
}
}
// 假如整個陣列都是遞減，則需要對整個陣列進行排序
reverse(0, nums.size() - 1, nums);
}
};example problems : LeetCode11. Container With Most Water
example problems : LeetCode2035. Partition Array Into Two Arrays to Minimize Sum Difference
example problems : LeetCode 234. Palindrome Linked List
example problems : LeetCode253. Meeting Rooms II
example problems : LeetCode443. String Compression
example problems : LeetCode26. Remove Duplicates from Sorted Array
example problems : LeetCode189. Rotate Array
Sliding Window
example problem : LeetCode3. Longest Substring Without Repeating Characters
example problem : LeetCode904. Fruit Into Baskets
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> um;
int left = 0;
int right = 1;
um[fruits[left]]++;
int maxsize = 1;
while(left < fruits.size() && right < fruits.size()) {
um[fruits[right]]++;
right++;
// 超過兩種水果，把 sliding window 縮小
while (um.size() > 2) {
um[fruits[left]]--;
if (um[fruits[left]] == 0) {
um.erase(fruits[left]);
}
left++;
}
// 保留最大可行的 sliding window 大小
maxsize = max(maxsize, right - left);
}
return maxsize;
}
};example problem : LeetCode239. Sliding Window Maximum
example problem : LeetCode567. Permutation in String
example problem : LeetCode438. Find All Anagrams in a String
example problem : LeetCode1493. Longest Subarray of 1’s After Deleting One Element
example problem : LeetCode2444. Count Subarrays With Fixed Bounds
example problem : LeetCode76. Minimum Window Substring
example problem : LeetCode424. Longest Repeating Character Replacement
example problem : LeetCode658. Find K Closest Elements
Disjoint-Set
disjoint-set : Union Find
example problems : LeetCode 200. Number of Islands
TODO :
[ — ] 研究一下 Union-Find 的時間複雜度
bit operations
math
math : 大數運算
example problem : LeetCode 415. Add Strings
class Solution {
public:
void reverse(string &s) {
int left = 0;
int right = s.size() - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
string addStrings(string num1, string num2) {
string ans;
reverse(num1);
reverse(num2);
int length = max(num1.size(), num2.size());
bool c = false;
for (int i = 0;i < length;i++) {
char tmp = 0;
if (i < num1.size() && i < num2.size()) {
tmp += (num1[i] - '0') + (num2[i] - '0') + '0';
} else if (i < num1.size()) {
tmp += (num1[i]);
} else {
tmp += (num2[i]);
}
if (c) {
tmp += 1;
}
if (tmp > '9') {
tmp -= 10;
c = true;
} else {
c = false;
}
ans.push_back(tmp);
}
if (c) {
ans.push_back('1');
}
reverse(ans);
return ans;
}
};example problem : LeetCode 2. Add Two Numbers
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = NULL;
ListNode *phead = NULL;
ListNode *pl1 = l1;
ListNode *pl2 = l2;
bool carry = false;
while(pl1 && pl2) {
ListNode *newn = new ListNode();
newn->val = pl1->val + pl2->val;
if (carry) {
newn->val++;
}
if (newn->val >= 10) {
newn->val -= 10;
carry = true;
} else {
carry = false;
}
if (head == NULL) {
head = newn;
phead = newn;
} else {
phead->next = newn;
phead = phead->next;
}
pl1 = pl1->next;
pl2 = pl2->next;
}
while (pl1) {
ListNode *newn = new ListNode();
newn->val = pl1->val;
if (carry) {
newn->val++;
}
if (newn->val >= 10) {
carry = true;
newn->val -= 10;
} else {
carry = false;
}
if (head == NULL) {
head = newn;
phead = newn;
} else {
phead->next = newn;
phead = phead->next;
}
pl1 = pl1->next;
}
while (pl2) {
ListNode *newn = new ListNode();
newn->val = pl2->val;
if (carry) {
newn->val++;
}
if (newn->val >= 10) {
carry = true;
newn->val -= 10;
} else {
carry = false;
}
if (head == NULL) {
head = newn;
phead = newn;
} else {
phead->next = newn;
phead = phead->next;
}
pl2 = pl2->next;
}
if (carry) {
ListNode *newn = new ListNode();
newn->val = 1;
phead->next = newn;
}
return head;
}
};example problem : 43. Multiply Strings
class Solution {
public:
string multiply(string num1, string num2) {
vector<int> n1;
vector<int> n2;
vector<int> n_result;
for (int i = num1.size() - 1;i >= 0;i--) {
n1.push_back(num1[i] - '0');
}
for (int i = num2.size() - 1;i >= 0;i--) {
n2.push_back(num2[i] - '0');
}
n_result = vector<int> (n1.size() + n2.size() + 1, 0);
for (int i = 0;i < n1.size();i++) {
for (int j = 0;j < n2.size();j++) {
n_result[i + j] += (n1[i] * n2[j]) % 10;
n_result[i + j + 1] += (n1[i] * n2[j]) / 10;
}
}
for (int i = 0;i < n_result.size() - 1;i++) {
if (n_result[i] >= 10) {
n_result[i + 1] += n_result[i] / 10;
n_result[i] %= 10;
}
}
while (!n_result.empty() &&
n_result.back() == 0) {
n_result.pop_back();
}
string ans;
for (int i = n_result.size() - 1;i >= 0;i--) {
ans.push_back(n_result[i] + '0');
}
return ans.size() == 0 ? "0" : ans;
}
};math : 快速冪取模
example problem : LeetCode 372. Super Pow
#define MOD (1337)
class Solution {
public:
void divide2(vector<int> &b) {
for (int i = b.size() - 1;i >= 0;i--) {
if (b[i] & 1) {
if (i > 0) {
b[i - 1] += 10;
}
}
b[i] /= 2;
}
while(!b.empty() && b.back() == 0) {
b.pop_back();
}
}
int fastPow(int a, vector<int> &b) {
if (b.size() == 0) {
return 1;
} else if (b.size() == 1 && b[0] == 1) {
return a;
}
bool odd = (b[0] & 1) ? true : false;
divide2(b);
int half = fastPow(a, b);
int tmp;
tmp = half % MOD;
tmp = (tmp * (half % MOD)) % MOD;
if (odd) {
tmp = (tmp * (a % MOD)) % MOD;
}
return tmp;
}
int superPow(int a, vector<int>& b) {
int left = 0;
int right = b.size() - 1;
// reverse the b array
// 讓我們可以更容易對該陣列除以 2
while (left < right ) {
int tmp = b[left];
b[left] = b[right];
b[right] = tmp;
left++;
right--;
}
// do the fastPow
return fastPow(a, b);
}
};math : GCD
example problem : LeetCode 914. X of a Kind in a Deck of Cards
class Solution {
public:
int gcd(int x, int y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
bool hasGroupsSizeX(vector<int>& deck) {
map<int, int> m;
for (int i = 0;i < deck.size();i++) {
m[deck[i]]++;
}
int now = 0;
for (auto it = m.begin();it != m.end();it++) {
now = gcd(now, it->second);
}
return now > 1;
}
};Note :
[ — ] gcd(0, 10) = 10
math : LCM
example problem : LeetCode 1201. Ugly Number III
// LCM + Binary Search
#define LL long long
class Solution {
public:
LL gcd(LL x, LL y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
LL lcm(LL x, LL y) {
return x * y / gcd(x, y);
}
int nthUglyNumber(int n, int a, int b, int c) {
// num / a + num / b + num / c
// 是 a, b 的公倍數則 -1
// 是 b, c 的公倍數則 -1
// 是 a, c 的公倍數則 -1
// 是 a, b, c 的公倍數則 + 1
// 最後可得該數為第幾個數
LL left = 1;
LL right = 2000000000;
LL lcm_ab = lcm(a, b);
LL lcm_bc = lcm(b, c);
LL lcm_ac = lcm(a, c);
LL lcm_abc = lcm(a, b);
lcm_abc = lcm(lcm_abc, c);
while(left <= right) {
LL mid = (left + right) / 2;
LL nth = mid / a + mid / b + mid / c -
mid / lcm_ab - mid / lcm_bc - mid / lcm_ac +
mid / lcm_abc;
if (nth == n &&
(mid % a == 0 || mid % b == 0 || mid % c == 0)) {
return mid;
} else if (nth < n) {
left = mid + 1;
} else {
// 當 nth == n ， 但 mid 卻不是 a, b, c 的倍數的時候，
// 需要將他減小。
right = mid - 1;
}
}
return 0;
}
};example problem : LeetCode 878. Nth Magical Number
Note :
[ — ] LCM(a, b) * GCD(a, b) = a * b
math : Sqrt(x)
example problem : LeetCode 69. Sqrt(x)
#define LL long long
class Solution {
public:
int mySqrt(int x) {
LL left = 0;
LL right = x;
LL mid = 0;
while(left <= right) {
mid = (left + right) / 2;
LL tmp = mid * mid;
if (tmp == x) {
return mid;
} else if (tmp < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 因為最後會停在 left == right + 1
// 我們希望取小的數，所以 return right
return right;
}
};math : Pow(x, n) ( 快速冪 )
example problem : LeetCode 50. Pow(x, n)
將指數分為左半邊以及右半邊，算過的指數不再重複算。
#define LL long long
class Solution {
public:
double fastPow(double x, LL ln) {
if (ln == 0) {
return 1;
} else if (ln == 1) {
return x;
}
double half = fastPow(x, ln / 2);
if (ln & 1) {
return half * half * x;
}
return half * half;
}
double myPow(double x, int n) {
double ans = x;
LL ln = n;
if (n < 0) {
x = 1 / x;
ln = -1 * ln;
}
return fastPow(x, ln);
}
};Rejection Sampling
example problem : LeetCode 470. Implement Rand10() Using Rand7()
設計一個更大的版面，落在該版面上的機率，需要每個元素都相同，並且把不感興趣的範圍通通都丟掉 ( rejection )。
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution {
public:
int rand10() {
while (1) {
int i = rand7();
int j = rand7();
i--;
j--;
int tmp = i * 7 + j;
if (tmp >= 1 && tmp <= 10) {
return tmp;
}
}
return 0;
}
};( Optional ) example problem : LeetCode 478. Generate Random Point in a Circle
Array Problems
example problem : LeetCode56. Merge Intervals
class Solution {
public:
bool isOverlap(vector<int> &a, vector<int> &b) {
if (b[0] <= a[1] &&
b[1] >= a[0]) {
return true;
}
return false;
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for (int i = 0;i < intervals.size();i++) {
vector<int> newi = intervals[i];
while (!ans.empty() &&
isOverlap(ans.back(), newi)) {
newi = {min(ans.back()[0], newi[0]), max(ans.back()[1], newi[1])};
ans.pop_back();
}
// 假如沒有半次 overlap，就把 intervals 給 push 進去
// 假如有 overlap，就把新的範圍給 push 進去
ans.push_back(newi);
}
return ans;
}
};example problem : LeetCode121. Best Time to Buy and Sell Stock
example problem : LeetCode1207. Unique Number of Occurrences
example problem : LeetCode1010. Pairs of Songs With Total Durations Divisible by 60
example problem : LeetCode2244. Minimum Rounds to Complete All Tasks
example problem : LeetCode53. Maximum Subarray
example problem : LeetCode587. Erect the Fence
example problem : LeetCode149. Max Points on a Line
example problem : LeetCode974. Subarray Sums Divisible by K
example problem : LeetCode1480. Running Sum of 1d Array
example problem : LeetCode54. Spiral Matrix
example problem : LeetCode380. Insert Delete GetRandom O(1)
example problem : LeetCode217. Contains Duplicate
example problem : LeetCode560. Subarray Sum Equals K
Backtracking Problems
example problem : LeetCode : 46. Permutations
class Solution {
public:
vector<vector<int>> ans;
void backtrack(vector<int> &nums, vector<bool> &visited, vector<int> &tmp) {
if (tmp.size() == nums.size()) {
ans.push_back(tmp);
return;
}
for (int i = 0;i < nums.size();i++) {
if (!visited[i]) {
visited[i] = true;
tmp.push_back(nums[i]);
backtrack(nums, visited, tmp);
tmp.pop_back();
visited[i] = false;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> visited = vector<bool>(nums.size(), false);
vector<int> tmp;
backtrack(nums, visited, tmp);
return ans;
}
};example problem : LeetCode : 51. N-Queens
class Solution {
public:
vector<vector<string>> ans;
int X[3] = {-1, -1, -1};
int Y[3] = {-1, 0, 1};
bool checkg(int nowx, int nowy, vector<string> &g) {
for (int i = 0;i < 3;i++) {
int newx = nowx + X[i];
int newy = nowy + Y[i];
while (newx >= 0 && newx < g.size() &&
newy >= 0 && newy < g[nowx].size()) {
if (g[newx][newy] == 'Q') {
return false;
}
newx += X[i];
newy += Y[i];
}
}
return true;
}
void back_track(vector<string> &g, int nowd, int targetd) {
if (nowd == targetd) {
ans.push_back(g);
return;
}
for (int i = 0;i < g[nowd].size();i++) {
g[nowd][i] = 'Q';
if (checkg(nowd, i, g)) {
back_track(g, nowd + 1, targetd);
}
g[nowd][i] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> g = vector<string>(n, string(n, '.'));
back_track(g, 0, n);
return ans;
}
};MISC
customize the vector sorting function
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
// a <= b --> 小的數會在前面
// a >= b --> 大的數會在前面
bool compare_vec(vector<int> &a, vector<int> &b) {
return a[2] <= b[2];
}
int main(int argc, char *argv[]) {
vector<vector<int>> test;
test.push_back({1, 2, 3});
test.push_back({1, 2, 2});
test.push_back({3, 2, 1});
sort(test.begin(), test.end(), compare_vec);
for (int i = 0;i < test.size();i++) {
printf("%d\n", test[i][2]);
}
return 0;
}customize the priority queue sorting function
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
/* 大的數會先被 pop */
/*
bool compare_vec(vector<int> &a, vector<int> &b)
{
return a[2] <= b[2];
}
*/
/* 小的數會先被 pop */
bool compare_vec(vector<int> &a, vector<int> &b)
{
return a[2] >= b[2];
}
int main(int argc, char *argv[]) {
priority_queue<vector<int>, vector<vector<int>>, decltype(&compare_vec)> test(compare_vec);
test.push({1, 2, 3});
test.push({3, 2, 2});
test.push({3, 2, 1});
while(!test.empty()) {
vector<int> top = test.top();
printf("%d\n", top[2]);
test.pop();
}
return 0;
}customize the ordered-map sorting function
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
/* 小的數會先被遍尋到 */
bool compare_vec(vector<int> a, vector<int> b)
{
return a[2] <= b[2];
}
/* 大數會先被遍尋到 */
/*
bool compare_vec(vector<int> a, vector<int> b)
{
return a[2] >= b[2];
}
*/
int main(int argc, char *argv[]) {
map<vector<int>, int, decltype(&compare_vec)> test(compare_vec);
vector<int> a = {1, 2, 3};
test[a] = 10;
a = {3, 2, 2};
test[a] = 20;
a = {3, 2, 1};
test[a] = 30;
for (auto it = test.begin();it != test.end();it++) {
vector<int> tmp = it->first;
for (int i = 0;i < tmp.size();i++) {
printf("%d ", tmp[i]);
}
printf(" : %d\n", it->second);
}
return 0;
}LeetCode Google 題庫
example problem : LeetCode 388. Longest Absolute File Path
/*
將字串使用 '有限狀態機' 進行處理後，裝成 stack
並對 stack 進行下一步的處理
*/
class Solution {
public:
int lengthLongestPath(string input) {
int state = -1;
int tab_num = 0;
string tmpstr;
vector<vector<int>> v;
bool isFile = false;
/*
0 : string length
1 : string depth
2 : string type
--> 0 : dir
--> 1 : file
*/
for (int i = 0;i < input.size();i++) {
if ((input[i] >= 'a' && input[i] <= 'z') ||
(input[i] >= 'A' && input[i] <= 'Z') ||
(input[i] >= '0' && input[i] <= '9') ||
input[i] == '.' || input[i] == ' ') {
state = 0;
} else if (input[i] == '\n') {
state = -1;
v.push_back({(int)tmpstr.size(), tab_num, isFile});
tmpstr.clear();
tab_num = 0;
isFile = false;
} else if (input[i] == '\t') {
state = 1;
} else {
state = -1;
}
if (state == 0) {
if (input[i] == '.') {
isFile = true;
}
tmpstr.push_back(input[i]);
} else if (state == 1) {
tab_num++;
}
}
v.push_back({(int)tmpstr.size(), tab_num, isFile});
int maxlen = 0;
int nowlen = 0;
vector<vector<int>> stack;
for (int i = 0;i < v.size();i++) {
while (!stack.empty() &&
stack.back()[1] >= v[i][1]) {
nowlen -= (stack.back()[0]);
stack.pop_back();
// 扣掉斜線
if (!stack.empty()) {
nowlen -= 1;
}
}
// 加上斜線
if (!stack.empty()) {
nowlen += 1;
}
stack.push_back(v[i]);
nowlen += stack.back()[0];
if (stack.back()[2] == 1) {
maxlen = max(maxlen, nowlen);
}
}
return maxlen;
}
};