- KMP
- Manacher
- Array
- Concurrency
- Greedy
- Tree
- Tree Relevant
- Math
- String
- Hash Table
- Hash Table
- Bit Manipulation
- Stack
- Queue
- Heap
- Linked List
- Two Pointer
- Sort
- Recursion
- Binary Search
- Binary Search Tree
- Depth First Search
- Backtracking
- Dynamic Programming
- Regular Expression Summary
- Sliding Window
- Graph
- Design
- Bash
🔍 ⭐ good algorithm
💥 : hard problem
✏️ smart code design
🎅: good question
❌: not good designed question
几个单独算法:
- Trie
- Union Find
C++
- c++ vector 可以作为map的key，但不能作为unordered_map的Key
- C++
unordered_set的insert 的return 的pair.second 可以告诉有没有insert 成功，如果原来就有，return false, 如果unordered_set 之前没有,return true比如 2101. Detonate the Maximum Bombs
complexity O(m+n), 不是kmp pattern search是O(mn)
作为suffix 放后面, 作为prefix 放前面，比如 a ("abc") + b("bcd") = 最小包含两个是的 = "abcd" , 用kmp时候, b (prefix) + "# + a (suffix)
/*
kmp的逻辑比如
text: a b c d a b x a b c d a b c d a b c y
pattern: a b c d a b c y
^
|
not match
check if any suffix is also preffix, 发现 abcdab 中 ab 即是prefix 也是suffix
就可以不用从头搜寻从 a b 开始, move pattern like this
text: a b c d a b x a b c d a b c d a b c y
pattern: a b c d a b c y then check if x and a are the same
text: a b c d a b x a b c d a b c d a b c y
pattern: a b c d a b c y
^
|
not match
check if any suffix is also preffix, 发现 abc即是prefix 也是suffix ,
no reason to compare abc again move pattern like this
text: a b c d a b x a b c d a b c d a b c y
pattern: a b c d a b c y
calculate pattern's longgest prefix which is a suffix. lps[i]表示在index i结束 prefix也是suffix最大长度
For the pattern “AAAA”, lps[] is [0, 1, 2, 3]
For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
For the pattern "aacaabdaacaac: lps is [0, 1, 0, 1, 2, 0, 0, 1, 2, 3, 4, 5, 3]
a a c a a b d a a c a a c -> 到 c, j = 5, 不match, pattern[j]!=pattern[i] => j = prefix[j-1] = prefix[4] = 2 => ve pattern[2] == pattern[i]
0 1 0 1 2 0 0 1 2 3 4 5
*/
int kmp(const string &text, const string & pattern){
vector<int>prefix = computeLps(pattern);
int j = 0;
for(int i = 0; i<text.size(); i++){ //i start from 0
while(j>0 && pattern[j]!=text[i])
j = prefix[j-1];
if(pattern[j] == text[i])
j++;
if(j == pattern.size()){
cout<<" pattern match at index="<<i - j + 1<<endl;
j = lps[j-1]; //注意j 跳到上lps[j-1]
/*
比如 text = a b a b a b a b
pattern = a b a b
| => move j to 2
v
pattern a b a b
*/
}
}
}
vector<int>computeLps(const string& pattern){
vector<int>lps(pattern.size()); //p 记录 longest proper prefix which is also a suffix.
//A proper prefix is a prefix with a whole string not allowed.
// For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC”, and “ABC”.
int j = 0; //表示最长prefix 也是suffix的index
for(int i = 1; i<pattern.size(); i++){ // ** i start from 1
while(j>0 && pattern[j]!= pattern[i]){
j = lps[j-1];
}
if(pattern[j] ==pattern[i])
j++;
//else j = 0;
lps[i] = j;
}
return lps;
}
vector<int>computeLps(const string& pattern){
vector<int>lps(pattern.size()); //p 记录 longest proper prefix which is also a suffix.
for(int i = 1; i<pattern.size(); i++){ // ** i start from 1
while(j>0 && pattern[j]!= pattern[i]){
j = lps[j-1];
}
j = lps[i] = j+ (pattern[j] ==pattern[i]);
}
return lps;
}
void kmp2(const string& pattern, const string& text, vector<int>&res){
string combine = pattern + "@" + text;
int pattern_size = pattern.size();
vector<int>lps(combine.size(), 0);
int j = 0;
for(int i = 1; i < combine.size(); ++i){
while(j > 0 && combine[i]!=combine[j])
j = lps[j-1];
if (combine[i] == combine[j])
++j;
lps[i] = j;
}
for(int i = pattern.size()+1; i<combine.size(); ++i){
if(lps[i] == pattern.size()){
cout<<"find match at text index "<< i - 2*pattern_size<<endl;
res.push_back(i-2*pattern_size);
}
}
return;
}| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 028. Implement strStr() | O(n+k) | O(k) | Easy | kmp algorithm: prefix array[i]表示i点的最长的prefix 也是suffix长度 比如"ABA", 第三个a的最长的prefix 也是suffix 的长度是1 A 而prefix array[i], 作为index, 是当前最长prefix 也是suffix 的下一位 |
| 214. Shortest Palindrome | O(n) | O(n) | Hard | ⭐⭐ 可以把此题换一种问法: 以index0 开始最长palindrome 的长度, 最长的开始最长palindrome后面的reverse +s = 答案
|
| 459. Repeated Substring Pattern | O(n) | O(n) | Easy | ⭐KMP return 条件 |
| 686. Repeated String Match | O(n+m) | O(n) | Medium | ⭐⭐
|
| 796. Rotate String | O(n) | O(1) | Easy | ⭐ 两种kmp的解,
|
| 1392. Longest Happy Prefix | O(n) | O(n) | Hard | Easy KMP, Rabin-Karp Algorithm (rolling hash) |
| 1397. Count Number of Teams | O(m*n) | O(m) | Hard | DFS /DP + KMP Hard problem💥 |
| 1408. String Matching in an Array | O(n) | O(n) | Easy | KMP, Rolling Hash |
| 2800. Shortest String That Contains Three Strings | O(a+b+c) | O(a+b+c) | Medium | |
| 3008. Find Beautiful Indices in the Given Array II | O(n+ max(na, nb)) | O(na+nb) | Hard | ⭐ KMP + Two pointers |
| 3031. Minimum Time to Revert Word to Initial State II | O(n) | O(n) | Hard | ⭐⭐⭐ kmp, z function |
| 3036. Number of Subarrays That Match a Pattern II | O(mn) | O(n) | Hard |
complexity O(n),
/*
https://segmentfault.com/a/1190000008484167
manacher 算法：
建一个新的string 开头用$, 结尾用^(为了防止越界), 中间用#
这样可以把偶回文 和 奇回文 都转化成奇数，比如
如此，s 里起初有一个偶回文abba和一个奇回文opxpo，被转换为#a#b#b#a#和#o#p#x#p#o#，长度都转换成了奇数。
p[i] 表示以i为中小心的最长回文半径
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
s_new[i] $ # a # b # b # a # h # o # p # x # p # ^
p[i] 1 1 2 1 2 5 2 1 2 1 2 1 2 1 2 1 4 1 2 1
两个int mx，和id, right 代表以 center 为中心的最长回文的右边界，也就是mx = center + p[center]。
mx是在当前回文右侧外的第一个点 mx点不包括在当前回文内
假设我们现在求p[i]，也就是以 i 为中心的最长回文半径，如果i < mx：
if (i < right)
p[i] = min(p[2 * center - i], right - i);
2 * center - i为 i 关于 center 的对称点 ( j+i = 2*center)，而p[j]表示以 j 为中心的最长回文半径，
因此我们可以利用p[j]来加快查找。
e.g1 . min(p[2 * center - i], right - i);
比如 c b c d c b z
- - | right
center
p[第一个b] = 3
第二个b的
p[2 * center - i] = p [第一个b] = 3， 现在以b 作为中心，右侧没有c，所以 不能等于 3
right - i = 1 ✅
e.g2. min(p[2 * center - i], right - i);
比如 a b c d c b a d
- _ | right
center
还是在 第二个b 点
p[2 * center - i] = p [第一个b] = 1，✅
right - i = 2
*/
string manacher(const string& s){
string s_new;
init(s, s_new);
vector<int>p(s_new.size());
int right = -1, center = -1;
int max_len = -1, max_center = -1;
for(int i = 1; i<s_new.size()-1; ++i){
if(i < right){
p[i] = min(p[2*center - i], right - i);
} else{
p[i] = 1;
}
while(s_new[i + p[i]] == s_new[i-p[i]] )
++p[i];
if (p[i] > right){
right = p[i];
center = i;
}
if (p[i] > max_len){
max_len = p[i];
max_center = i;
}
}
return s.substr((max_center - max_len)/2, max_len - 1);
}
void init(const string& s, string& res){
res = "$#";
for(auto c: s){
res += c;
res += '#';
}
res += "^";
}| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 005.Longest Palindromic Substring | O(n) | O(n) | Medium | ⭐ manacher(马拉车算法) |
| 214. Shortest Palindrome | O(n) | O(n) | Hard | ⭐ 可以把此题换一种问法: 以index0 开始最长palindrome 的长度, 最长的开始最长palindrome后面的reverse +s = 答案
|
| 647. Palindromic Substrings | O(n) | O(n) | Medium | ⭐⭐⭐ sum(sum(dp, [])) sum 2d array
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 102. Binary Tree Level Order Traversal | O(n) | O(n) | Medium | |
| 103. Binary Tree Zigzag Level Order Traversal | O(n) | O(n) | Medium | |
| 117. Populating Next Right Pointers in Each Node II | O(n) | O(1) | Medium | Traverse through next instead of Traverse from top to down |
| 269. Alien Dictionary | O(n) | O(1) | Medium | ⭐⭐⭐Topological sort |
| 310. Minimum Height Trees | O(n) | O(n) | Medium | |
| 743. Network Delay Time | O(E *logV) | O(E + V) | Medium | Dijkstra's Algorithm |
| 787. Cheapest Flights Within K Stops | O(E * logV) | O(E + V) | Medium | ⭐⭐⭐ Dijkstra's Algorithm |
| 1091. Shortest Path in Binary Matrix | O(n^2) | O(n^2) | Medium | |
| 1197. Minimum Knight Moves | O(n*m) | O(n*m) | Hard |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 015. 3 Sum | O(n^2) | O(1) | Medium | 🔍问题关键是sort + skip duplicate |
| 016. 3 Sum Closest | O(n^2) | O(1) | Medium | 🔍sort + two pointer，根据three sum 和sorted list移动两个pointers |
| 018. 4 Sum | O(n^3) | O(1) | Medium | 🔍sort + two pointer，思路和015. 3 Sum 一样 |
| 026. Remove Duplicates from Sorted Array | O(n) | O(1) | Easy | Two pointer |
| 027. Remove Element | O(n) | O(1) | Easy | Two pointer |
| 031. Next Permutation | O(n) | O(1) | Medium | 跟556. Next Greater Element III 思路类似, C++可以用is_sorted_until + upper_bound() |
| 041. First Missing Positive | O(n) | O(1) | Hard | 🔍先置换, 把每个元素放在合适位置，再看A[i] == i+1 ? 不等于 return i+1, 最后如果还没return, return size +1 |
| 048. Rotate Image | O(n^2) | O(1) | Medium | 🔍
|
| 054. Spiral Matrix | O(m*n) | O(1) | Medium | 🔍定义 up, down, left, right 四个边界，每次loop 在最外围的一圈 |
| 059. Spiral Matrix II | O(n^2) | O(1) | Medium | 🔍思路跟048. Rotate Image 和 054. Spiral Matrix 类似 |
| 066. Plus One | O(n) | O(1) | Easy | |
| 073. Set Matrix Zeroes | O(m*n) | O(1) | Medium | 🔍two pass:1. 把如果matrix[i][j] == 0, 把matrix[i][0] 和matrix[0][j] 设为0, 如果第一列设0之前，有数为0，设col0 = 0。 2.从下往上loop, 碰到matrix[i][0]] or matrix[0][j] 为0, matrix[i][j] = 0, if col0 == 0, matrix[i][0] = 0 |
| 080. Remove Duplicates from Sorted Array II | O(n) | O(1) | Medium | |
| 118. Pascal's Triangle | O(n^2) | O(1) | Easy | |
| 119. Pascal's Triangle II | O(n^2) | O(1) | Easy | Easy DP |
| 121. Best Time to Buy and Sell Stock | O(n) | O(1) | Easy | |
| 128. Longest Consecutive Sequence | O(n) | O(n) | Hard | 🔍
|
| 169. Majority Element | O(n) | O(1) | Easy | |
| 189. Rotate Array | O(n) | O(1) | Easy | |
| 215. Kth Largest Element in an Array | O(n) ~ O(n^2) | O(1) | Medium | 🔍
|
| 228. Summary Ranges | O(n) | O(1) | Medium | |
| 229. Majority Element II | O(n) | O(1) | Medium | 🔍Boyer-Moore Majority Vote algorithm |
| 238. Product of Array Except Self | O(n) | O(1) | Medium | 🔍res[i]表示 nums[0: i-1]的乘积，right 记录从结尾到nums[i+1: end]的乘积. 最后res[i] = res[i] * right; 也可以用left, right One Pass |
| 240. Search a 2D Matrix II | O(n+m) | O(1) | Medium | 🔍sorted matrix题目的关键是从第一行最后一个开始，如果当前数比想要的大, --col, 如果当前数比想要的小，++row |
| 289. Game of Life | O(m * n) | O(1) | Medium | 🔍跟238. Product of Array Except Self有一点点类似，先变化matrix到想要的格式, 然后再做transform到结果: 把下一代活的 |
| 334. Increasing Triplet Subsequence | O(n) | O(1) | Medium | 🔍用两个数表示b, c, c表示当前最小, b表示当前第二小, 当i都大于这两个数，return true, 不用担心i只更新更新c, 因为答案必须要迈过b |
| 370. Range Addition | O(n) | O(n) | Medium | prefix array |
| 384. Shuffle an Array | O(n) | O(n) | Medium | C++ srand(time(NULL)); rand(); uniform_int_distribution |
| 396. Rotate Function | O(n) | O(1) | Medium | 🔍mathematical induction F(k) = F(k-1) + sum - nBk[-k] |
| 412. Fizz Buzz | O(n) | O(1) | Easy | |
| 414. Third Maximum Number | O(n) | O(1) | Easy | |
| 419. Battleships in a Board | O(n*m) | O(1) | Medium | 🔍看源头，if [i][j] = 'X' 且 [i-1][j] 和 [i][j-1] 如果都不是X，count += 1 |
| 442. Find All Duplicates in an Array | O(n) | O(1) | Medium |
|
| 448. Find All Numbers Disappeared in an Array | O(n) | O(1) | Medium | 思路与442. Find All Duplicates in an Array一模一样，两种方法也一样 |
| 565. Array Nesting | O(n) | O(1) | Medium | DFS, 把visit的点变为-1, nest array是循环，所以起点无论是哪个点进入都可以得到完整的循环, 比如 a->b->c->d->a 不会有 a->b->c->d->b |
| 566. Reshape the Matrix | O(m*n) | O(1) | Easy | |
| 581. Shortest Unsorted Continuous Subarray | O(n) | O(1) | Easy | 🔍
|
| 605. Can Place Flowers | O(n) | O(1) | Easy | |
| 661. Image Smoother | O(n) | O(1) | Easy | 跟289. Game of Life思路一样， 一点不一样的是把下一代的数右移8个bit, 之后再第二次pass matrix, 每个点>>8 左移8个bits |
| 665. Non-decreasing Array | O(n) | O(1) | Easy | 🔍两种operation: 1.nums[i-1] = nums[i] (降), nums[i] = nums[i-1] (升), 降优于升 |
| 667. Beautiful Arrangement II | O(n) | O(1) | Meidum | 🔍brainstorm |
| 670. Maximum Swap | O(n) | O(1) | Medium | 🔍
|
| 674. Longest Continuous Increasing Subsequence | O(n) | O(1) | Easy | |
| 697. Degree of an Array | O(n) | O(n) | Easy | |
| 845. Longest Mountain in Array | O(n) | O(1) | Medium | 🐸 |
| 918. Maximum Sum Circular Subarray | O(n) | O(1) | Medium | 🎅🎅 Kadane's algorithm |
| 957. Prison Cells After N Days | O(k*(N, 2^k)) | O(k) | Medium | |
| 974. Subarray Sums Divisible by K | O(n) | O(n) | Medium | ⭐⭐C++ 余数可能是负数，python的余数不会是负数 |
| 997. Find the Town Judge | O(n+t) | O(n) | Easy | 🎅 In-degree, out-degree |
| 1375. Bulb Switcher III | O(n) | O(1) | Medium | |
| 1380. Lucky Numbers in a Matrix | O(m*n) | O(m+n) | Easy | zip(*m)获得column in list, set intersection |
| 1389. Create Target Array in the Given Order | O(n^2) | O(1) | Easy | ❌ |
| 1394. Find Lucky Integer in an Array | O(n) | O(n) | Easy | :pencil2: Loop C++ Map Key Value |
| 1583. Count Unhappy Friends | O(n^2) | O(n) | Medium | bad description, better description-for-a-bad-framed-question-%3A() |
| 2373. Largest Local Values in a Matrix | O(n) | O(1) | Easy | |
| 3030. Find the Grid of Region Average | O(9*n*m) | O(n*m) | Medium | |
//
void helper(TreeNode* root, vector<int>&res){
if(!root) {return;}
//res.push_back(root->val); pre order
helper(root->left, res);
//res.push_back(root->val); in order
helper(root->right, res);
//res.push_back(root->val); post order
return;
}
//Inorder Traversal
//stack,
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
TreeNode *cur = root;
if(!root) return {};
vector<int>res;
stack<TreeNode *>stk;
while(cur || !stk.empty()){ //cur 比如只有右面的，stack只存之后需要返回的 ； !stk.empty() 是看是不是有接下来返回的node，比如到最左侧node 需要返回
if(cur){
//res.push_back(cur->val); pre order, post order
stk.push(cur);
cur = cur->left;
}else{//切换到之前的top
cur = stk.top(); stk.pop();
res.push_back(cur->val); // in order;
cur = cur->right;
}
}
return res;
}
};
//Postorder: 先right 再left 最后reverse
//postorder 是把tree mirror后的pre order
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int>res;
TreeNode* cur = root;
while(cur ||!stk.empty()){
if(cur){
res.push_back(cur->val);
stk.push(cur);
cur = cur->right;
}else{
cur = stk.top(); stk.pop();
cur = cur->left;
}
}
reverse(res.begin(), res.end());
return res;
}
};
//Morris: 流程图见, 094. Binary Tree Inorder Traversal.cpp
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>res;
TreeNode* cur = root;
while(cur){
if(!cur->left)
{
//res.push_back(cur->val); //Inorder, preorder
cur = cur->right; //cover所有没有left tree的点
}else{
TreeNode* pre = cur->left;
while(pre->right && pre->right!=cur)
pre = pre->right;
if(pre->right){ //表示cur的left 已经全部visit完成，又回到cur了
//res.push_back(cur->val); //Inorder
pre->right = NULL; //cover剩下其他的点
cur = cur->right;
}
else{
//res.push_back(cur->val); //Pre-order
pre->right = cur;
cur = cur->left;
}
}
}
return res;
}
};
//PostOrder
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int>res;
TreeNode* cur = root;
while(cur){
if(!cur->right){
res.push_back(cur->val);
cur = cur->left;
}else{
TreeNode* pre = cur->right;
while(pre->left && pre->left != cur)
pre = pre->left;
if(pre->left){
pre->left = NULL;
cur = cur->left;
}else{
res.push_back(cur->val);
pre->left = cur;
cur = cur->right;
}
}
}
reverse(res.begin(), res.end());
return res;
}
};
//如果有right child, 经过root 两次
//112. Path Sum https://leetcode.com/problems/path-sum/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
stack<TreeNode*>stk;
TreeNode* cur = root, *pre = nullptr;
while(cur || !stk.empty()){
if(cur){
stk.push(cur);
sum -= cur->val;
cur = cur->left;
}else{
cur = stk.top();
if(!cur->right && !cur->left && sum == 0)
return true;
if(cur->right && cur->right != pre){
cur = cur->right;
}
else{
pre = cur;
sum += cur->val;
cur = nullptr;
stk.pop();
}
}
}
return false;
}
};
//In order traversal, 不同于之前的iterative 解, 这是每个node 都先被push 进stack, 只有return back时候才pop
/*
详见 236. Lowest Common Ancestor of a Binary Tree
https://github.com/beckswu/Leetcode/blob/master/DFS/236.%20Lowest%20Common%20Ancestor%20of%20a%20Binary%20Tree.cpp#L32，
1
/
2
\
3
最上面的inorder 的 stack 到3时候是 [1，3
下面解的stack 是 到3是 [1,2,3]
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//iterative, path comparing
if(!root ) return root;
vector<TreeNode*> path;
if(root)
path.push_back(root); //temp是stack，元素是从root到现在node上的路径
TreeNode *prev = nullptr;
while(!path.empty()){
root=temp.back();
if(!root->left && !root->right || !root->right && prev==root->left || root->right && prev==root->right){
path.pop_back();
prev=root;
}
else{
if(!root->left || prev==root->left) path.push_back(root->right);
else path.push_back(root->left);
}
}
}
};
TreeNode* helper(TreeNode** head ){
int val = *head; //获取值, 比如值是5,
TreeNode** cur = head; //
head = &((*head)->left); //不会影响之前cur的值， 把head assign 一个新object, 之前绑定head的地址(cur)的object 并没有删除
*head = (*head)->left; //会影响cur的值， *head 取地址, 改变head这个地址绑定的值, 因为cur 和head地址一样 , 所以cur的值也改变
return cur;
}
//比如:
void helper(int *p){
int *newp = p;
*p = 5; //会影响newp的值, 因为newp 和 p地址一样，更改的p的值， newp自动会更改
p = new int(10); // 不会更改newp 的值, 因为p的地址被换掉了, 之前绑定p的地址并没有删除
}
BIT tree (Binary Index Tree)
/*
array 3 2 -1 6 5 4 -3 3 7 2 3
index 0 1 2 3 4 5 6 7 8 9 10
BIT Tree �Visulation (tree 的index = array index + 1)
0 (0)
/ | | \
/ / \ \
3 (0,0) 5 (0,1) 10 (0,3) 19 (0,7) -> 存的是它左侧所有属于同一个parent的leaf 和
1 2 4 8 比如 tree index = 6 存的是 array (4,5) 的点
| | \ | \
-1 (2,2) 5(4,4) 9 (4, 5) 7 (8,8) 9 (8, 9)
3 5 6 9 10
| |
-3 (6,6) 3 (10,10)
7 11
Get Parent (把最右侧的bit remove掉，比如 1010 -> 1000, 111->110)
1) 2's complement (= negate 所有bit + 1)
2) AND it with original number
3) subtract from original number
Parent(7)
1) 7 (111) complement + 1 = 000 + 1 = 001
2) 111 & 001 = 001
3) 111 - 001 = 110 (6)
Get Next:
1) 2's complement (= negate 所有bit + 1)
2) AND it with original number
3) Add from original number
Get Next(2) move 到最右侧的bit + 1位，且把后面bit 全部抹掉 0011 -> 0100, 0101 -> 0110, 0110 -> 1000
1) 的 2's complement 0011 的negate 是1100 + 1 = 1101
2) 1100 & 0011 = 1
3） 0011 + 1 = 0100
*/
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 094. Binary Tree Inorder Traversal | O(n) | O(1) | Medium | 😍🔍Morris Traversal, 现在点连在 left-child 最右侧的node 右侧, 因为最右侧的node 最后visit |
| 099 Recover Binary Search Tree | O(n) | O(1) | Hard | 🔍😚 调换node 之间第一个最错误的（也是最大的prev），和最后一个错误（也是最小的cur），💡顺序一定是inorder，由小到大 |
| 144. Binary Tree Preorder Traversal | O(n) | O(1) | Medium | Morris Traversal,注意preorder 与inorder push 进vector的顺序的区别 |
| 145. Binary Tree Postorder Traversal | O(n) | O(1) | Hard | = 先right 再left 的 inorder traversal 🔍Morris Traversal |
| 208. Implement Trie (Prefix Tree) | O(n) | O(1) | Medium | Trie |
| 211. Add and Search Word - Data structure design | O(min(n, h)) | O(min(n, h)) | Medium | Trie + DFS |
| 226. Invert Binary Tree | O(n) | O(h), O(w)) | Easy | 👽 不可以 left = invert(right); right = invert(left);, 因为left 在invert right时候改变 |
| 297. Serialize and Deserialize Binary Tree | O(n) | O(h) | Hard | ✏️ostringstream & istringstream 用法, BFS－> pointer of pointer 存pointer 地址 |
| 307. Range Sum Query - Mutable | O(n), O(logn) | O(n) | Medium | ✏️ BIT & Segment Tree; BIT tree 需要arr作为参照物,每次根据val-arr[i]的update, update过后arr[i] = val Similar Question: |
| 314. Binary Tree Vertical Order Traversal | O(n) | O(n) | Medium | minRemoveToMakeValid |
| 426. Convert Binary Search Tree to Sorted Doubly Linked List | O(n) | O(n) | Medium | |
| 538. Convert BST to Greater Tree | O(n) | O(h) | Easy | 😍注意Python BFS |
| 543. Diameter of Binary Tree | O(n) | O(h) | Easy | 🔍先尽可能dfs，再比较height 会更快 |
| 563. Binary Tree Tilt | O(n) | O(n) | Easy | ❌思路跟543. Diameter of Binary Tree 一样 |
| 572. Subtree of Another Tree | O(m * n) | O(h) | Easy | 😍 seralization |
| 606. Construct String from Binary Tree | O(n) | O(h) | Easy | ❌ Easy Recursion |
| 617. Merge Two Binary Trees | O(n) | O(h) | Easy | 😍 |
| 623. Add One Row to Tree | O(n) | O(h) | Medium | 😚 |
| 637. Average of Levels in Binary Tree | O(n) | O(h) | Easy | ❌ |
| 652. Find Duplicate Subtrees | O(n) | O(n) | Medium | 😍🔍 Seralization(String的memory 是 O(n^2)) / Hash, C++ 有定义hash. 注: 无须seralize 完整后再寻找, analysis |
| 653. Two Sum IV - Input is a BST | O(n) | O(h) | Easy | 😍🔍可以考怎么写 BST Iterator |
| 654. Maximum Binary Tree | O(n) | O(h) | Medium | 😍🔍💡 descending stack:
|
| 655. Print Binary Tree | O(n) | O(h) | Medium | Math找规律 |
| 662. Maximum Width of Binary Tree | O(n) | O(h) | Medium | ❌ Math 找规律, 逻辑跟655. Print Binary Tree类似 |
| 677. Map Sum Pairs | O(n) | O(t) | Medium | ❌Simple Trie |
| 684. Redundant Connection | O(n) | O(n) | Medium | 🔍Union Find 如果两个node 连接之前发现parent 已经一样，表示之前两个nodes已经连接，如果再连接edge，会构成cycle |
| 685. Redundant Connection II | O(n) | O(n) | Hard | Union Find 注意构成tree 的条件, 不能有一个child 连上两个parent, 然后去掉这个child一个链，保证都是一个child对应一个parent, 再看有没有cycle, 没有cycle表示去链去成功了, 有cycle 表示去链去错了 |
| 687. Longest Univalue Path | O(n) | O(h) | Easy | 😍 Really good Recussive Question! |
| 699. Falling Squares | O(nlogn) | O(n) | Hard | 😍Good Question! 若想找点属于 哪个范围之中 比如 3∈ (1,5) or (7,9) , 用map + binary search
|
| 814. Binary Tree Pruning | O(n) | O(h) | Medium | 😍Really good question! |
| 850. Rectangle Area II | O(nlogn) | O(h) | Hard | 🔍💡跟699. Falling Squares思路有点像, 根据height一层一层的算当层长方体面积,算完面积后更新上一层的底curx |
| 863. All Nodes Distance K in Binary Tree | O(n) | O(h) | Medium | 😍😍Really good question! 不必纠结于one pass, 需要child -> parent map |
| 865. Smallest Subtree with all the Deepest Nodes | O(n) | O(h) | Medium | 🔍 若left, right child 都是最深的, 则root为 最深的node |
| 889. Construct Binary Tree from Preorder and Postorder Traversal | O(n) | O(h) | Medium | 😍😍
|
| 1008. Construct Binary Search Tree from Preorder Traversal | O(n) | O(h) | Medium | 🎅Stack, Recursion, Morris Traversal |
| 1110. Delete Nodes And Return Forest | O(n) | O(n) | Medium | |
| 1028. Recover a Tree From Preorder Traversal | O(n) | O(h) | Hard | 😚 stack / DFS, stack逻辑类似889. Construct Binary Tree from Preorder and Postorder Traversal |
| 1409. Queries on a Permutation With Key | O(nlogn) | O(n) | Medium | ⭐⭐⭐相当于问queries[i] 前面有几个数 思路 How to Build FenwickTree Double BIT tree size, move forward Similar Question: |
| 2458. Height of Binary Tree After Subtree Removal Queries | O(n) | O(n) | Hard | ⭐⭐⭐ 把左边高度带到右边，把右边高度带到左边, lru_cache, @functools.cache |
| 1825. Finding MK Average | O(nlogn) | O(n) | Hard | BIT, Fenwick Tree Similar Question: |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 588. Design In-Memory File System |
|
O(n) | Hard | |
| 1268. Search Suggestions System | O(M) | O(n) | Medium | |
| 3045. Count Prefix and Suffix Pairs II | O(n*max(l)) | O(n*max(l)) | Hard | ⭐⭐⭐⭐
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 006. ZigZag Conversion | O(n) | O(n) | Medium |
|
| 008. String to Integer (atoi) | O(n) | O(1) | Easy | C++可以用find_first_not_of |
| 014. Longest Common Prefix | O(n) | O(1) | Easy | loop所有数第0位到第i位，直到不相同,返回str[0].substr(0,i) |
| 038. Count and Say | O(n * 2^n) | O(n2^n) | Easy | C++ find_if + bind1st |
| 043. Multiply Strings | O(m*n) | O(m+n) | Medium | C++ transform, 必须都从个位数(也就是string的最后一位开始算, 否则carry可能会超过10), back_inserter, 相当于按照原来从头到尾顺序push back |
| 058. Length of Last Word | O(n) | O(1) | Easy | C++ find if or find if + bind1st or string find_last_not_of + find_last_of |
| 065. Valid Number | O(n) | O(1) | Hard | |
| 067. Add Binary | O(n) | O(1) | Easy | string 加法, 跟415. Add Strings 和306. Addictive Number 类似 |
| 068. Text Justification | O(n) | O(1) | Hard | 跟725. Split Linked List in Parts 类似 |
| 125. Valid Palindrome | O(n) | O(1) | Easy | C++ 跳过非isalnum的 |
| 151. Reverse Words in a String | O(n) | O(1) | Medium | 先reverse所有的, 再reverse单个每个词, 记录总共len,最后用来截取, C++ find_first_not_of + find_first_of |
| 165. Compare Version Numbers | O(n) | O(1) | Medium | c++ 算当前version1,2的substr的数，如果其中一个碰到结尾，设当前数位0。 c, 可以用c_str() + strtol; python3 zip(*itertools.zip_longest(*splits, fillvalue=0)) |
| 242. Valid Anagram | O(n) | O(1) | Easy | 经典面试题 |
| 273. Integer to English Words | O(1) | O(1) | Hard | 无聊的recursion |
| 306. Addictive Number | O(n^3) | O(n) | Medium | recursion 从index0开始试所有的digit可能性直到成功, 比如开始是一位+两位, 还是三位+两位 , 需要一个string add的help function; python 可以用itertools.combination + startswith, 跟067. Add Binary 和415. Add Strings 类似, 只不过多个recursion |
| 383. Ransom Note | O(n) | O(n) | Easy | Hash map |
| 405. Convert a Number to Hexadecimal | O(n) | O(1) | Easy | 最后结果需要reverse，因为先插入最小的，注意负数的, -1>>4 = -1, 所以while加个条件 res.length()!=sizeof(int)*2 |
| 408. Valid Word Abbreviation | O(n) | O(1) | Easy | |
| 415. Add Strings | O(n) | O(1) | Easy | string加法，跟067. Add Binary 和306. Addictive Number 类似 |
| 420. Strong Password Checker | O(n) | O(1) | Hard | Brain Storm 详见C++ code 解释 |
| 434. Number of Segments in a String | O(n) | O(1) | Easy | 🔍, 根据s[i] 和 s[i-1]判断, or s[i] 和 s[i+1]判断 |
| 443. String Compression | O(n) | O(1) | Easy | two pointer + num reverse |
| 468. Validate IP Address | O(1) | O(1) | Medium | 注意IPv4 和IPv6的定义(c++ code里), 判断一个char是不是符合十六进制用isxdigit(c) |
| 520. Detect Capital | O(1) | O(1) | Easy | C++ count_if; Python istitle()看是不是只有首字母大写 |
| 521. Longest Uncommon Subsequence I | O(min(a, b)) | O(1) | Easy | 题出的神经病，逗你玩儿 |
| 522. Longest Uncommon Subsequence II | _O(l * n^2) _ | O(1) | Medium | 🔍按照字母长度sort, 然后一个一个看str，有没有在list中有subsequence，没有的话, return 这个str长度,直到全部search完, return -1 or C++ equal_range + count_if , python 可以iter() |
| 524. Longest Word in Dictionary through Deleting | O((d * l) * logd) | O(1) | Medium | 按照字母长度sort,如果长度一样，按照alphabet sort, 找到第一个符合的 🔍python, max with key, min with key, filter, iter + next with default |
| 539. Minimum Time Difference | O(nlogn) | O(n) | Medium | C++ transform 把所有时间变分钟, 然后按minute sort, 答案就出自所有minute[i+1] - minute[i] or 1440 +minute[0] - minute.back() |
| 541. Reverse String II | O(n) | O(1) | Easy | |
| 551. Student Attendance Record I | O(n) | O(1) | Easy | |
| 556. Next Greater Element III | O(1) | O(1) | Medium | 可以用ascending stack or 两个for loop, 寻找i点往后最后一个比i点大的数(也是比i大,最接近i的数)(index j), swap(s[i], s[j]), 这样s[i]后面的数又大到小排序的, 把i往后的数到end全部reverse后变成Int, 就是答案, 跟031. Next Permutation思路类似 |
| 564. Find the Closest Palindrome | O(l) | O(l) | Hard | Brain Storm: 最接近的pal只可能5中选一, 100..001(l.size()+1), 99..99(l.size()-1), or string的前半部分 +1, +0, -1 加上前半部分的reverse(如果起始长度是奇数，reverse不包括前半部分最后一个，如果长度是偶数，都包括在内) |
| 591. Tag Validator | O(n) | O(n) | Hard | cdata 必须以 已 ]]>结束, recursion 找是不是valid tag, valid cdata, valid tagname |
| 648. Replace Words | O(n) | O(t) | Medium | 🔍 Trie; python 可以用reduce + dict.__getitem__ |
| 657. Judge Route Circle | O(n) | O(1) | Easy | |
| 678. Valid Parenthesis String | O(n) | O(1) | Medium | 🔍Three Solutions
|
| 680. Valid Palindrome II | O(n) | O(1) | Easy | 🔍两个pointer, 检查s[i] == s[j]?, 遇到不等时，再看s[i+1, j], or s[i, j-1]是不是pal |
| 681. Next Closest Time | O(1) | O(1) | Medium | |
| 696. Count Binary Substrings | O(n) | O(1) | Easy | manacher(马拉车)算法的变形 |
| 720. Longest Word in Dictionary | O(n) | O(t) | Easy | Trie or 先按长度sort, 长度越短, 排前面, loop word, loop s[i][0,len), 看是不是每个substr都在，都在话insert to hashset & update result |
| 722. Remove Comments | O(n) | O(k) | Medium | |
| 791. Custom Sort String | O(n) | O(k) | Medium | 可以当经典面试题, 三种解法:
|
| 804. Unique Morse Code Words | O(n) | O(n) | Easy | Easy one unordered_set |
| 806.Number of Lines To Write String | O(n) | O(1) | Easy | Easy one but stupid question description |
| 809. Expressive Words | O(n+s) | O(1) | Medium | Two pointer: 如果word[i]!=S[j] 的时候， 看S的j-1, j, j+1是不是连续是三个，若不是，再看过去是不是连续三个，若不是，break |
| 816. Ambiguous Coordinates | O(n^3) | O(n) | Medium | 🔍选择小数点的关键是 不能左面位0， 右面结束也是0，比如00.1230不可以,但是即使左面等于0， 右面最后也不可以是0 |
| 819. Most Common Word | O(n+m) | O(m+n) | Easy | |
| 820. Short Encoding of Words | O(n) | O(t) | Medium |
|
| 824. Goat Latin | O(n + w^2) | O(l) | Easy | stringstream 作为string output |
| 831. Masking Personal Information | O(1) | O(1) | Easy | C++ transform 把所有字母都小写, s[0] 变成string 可以用 s.substr(0,1) or string(1,S[0]) |
| 833. Find And Replace in String | O(m+n) | O(n) | Medium | 先sort indexes,然后从后往前loop S,这样可以保持S前面的index不变, python 可以用zip + startswith |
| 839. Similar String Groups | O(n^2 * l) | O(n) | Easy | 🔍 Union Find Disjoint Set with Rank Heuristic, string 所在位置为index |
| 848. Shifting Letters | O(n) | O(1) | Medium | 加的时候及时%26, 小心overflow |
| 859. Buddy Strings | O(n) | O(1) | Easy | 判断条件: 1.长度不一样，false，2. 如果a == b，有没有重复的字母，有的话true, 没有false, 3, 如果不一样的位置个数不等于2, 或者a[diff[0]]!=b[diff[1]] or a[diff[1]]!=a[diff[1]] 返回false, 否则是true |
| 953. Verifying an Alien Dictionary | O(n*l) | O(1) | Easy | |
| 1374 Generate a String With Characters That Have Odd Count | O(n) | O(1) | Easy | ❌ |
| 1410. HTML Entity Parser | O(n) | O(t) | Medium | |
| 1417. Reformat The String | O(n) | O(1) | Easy | |
| 2272. Substring With Largest Variance | O(n) | O(1) | Hard | ⭐⭐Kadane's Algorithm |
| summary |
|---|
reference reference2
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 136. Single Number | O(n) | O(1) | Easy | 用xor ^, Python Reduce one line |
| 137. Single Number II | O(n) | O(1) | Medium | 🔍
|
| 190. Reverse Bits | O(1) | O(1) | Easy | 一位一位reverse bit, res每次向左移动一位，n向右移动一位 |
| 191. Number of 1 Bits | O(n) | O(1) | Easy | n = n & (n-1); |
| 201. Bitwise AND of Numbers Range | O(1) | O(1) | Medium | 一位一位比较digit，直到移动k位m=n, 那么此时的digit是bitwise and的结果, res = m<<k |
| 231. Power of Two | O(1) | O(1) | Easy | n = n & (n-1); |
| 260. Single Number III | O(n) | O(1) | Medium | 🔍两个pass,第一个pass, 通过Xor需要区分a 和 b的数 c(是a与b右面第一位不一样的数), 第二次pass, 通过c&nums[i]判断做xor, 找到a和b (binary 负数) |
| 268. Missing Number | O(n) | O(1) | Medium | Math, Swap, Xor |
| 318. Maximum Product of Word Lengths | O(n^2) | O(n) | Medium | 🔍可以用bit来判断两个string是不是有重合的字母, 用数字表示string, a是第一位被set，z是第26位被set, |
| 342. Power of Four | O(1) | O(1) | Easy | 4^n = (3+1)^n, 除了判断(n&n-1) , 还要判断n-1 是不是可以整除3 |
| 371. Sum of Two Integers | O(1) | O(1) | Easy | （a&b)<<1 表示需要相加进位的（两个1相加）, a ^ b 表示相加不进位（保留单个1） |
| 389. Find the Difference | O(1) | O(1) | Easy | 🔍找两个string唯一不同不同的char可以通过 xor |
| 393. UTF-8 Validation | O(n) | O(1) | Easy | 用count判断是不是起点, count==0 是起点 |
| 421. Maximum XOR of Two Numbers in an Array | O(nlogk) | O(n) | Medium | 🔍
|
| 461. Hamming Distance | O(1) | O(1) | Easy | 判断有多少bit, 与191. Number of 1 Bits和 231. Power of Two类似 |
| 462 Minimum Moves to Equal Array Elements II | O(nlogn) | O(1) | Medium | 🔍Meeting point, 先sort，然后逐个用最大减去最小, e.g [3,6,9], 不管中间点在哪，都要磨平9-3=6的差距 |
| 476. Number Complement | O(1) | O(1) | Easy | |
| 477. Total Hamming Distance | O(nlogk) | O(1) | Easy | 由第32位到第0位，loop每个bit，数当前bit位为1的个数为bitcount, 结果 res+= bitcount*(size-countsize), 与421. Maximum XOR of Two Numbers in an Array类似 |
| 645. Set Mismatch | O(n) | O(1) | Easy |
|
| 693. Binary Number with Alternating Bits | O(1) | O(1) | Easy | 🔍 |
| 762. Prime Number of Set Bits in Binary Representation | O(R-L) | O(1) | Easy | loop[L,R],数每个数多少个bit，因为log2(10^6) < 16, 事先把所有的prime存到hash set里面, 看现在bit数是不是质数，if so res++, 还可以用 __builtin_popcountl(n); bitset<32>(n).count() |
| 1835. Find XOR Sum of All Pairs Bitwise AND | O(n) | O(1) | Hard | |
| 2317. Maximum XOR After Operations | O(n) | O(1) | Medium | ⭐ ✏️ c++ reduce |
| 2354. Number of Excellent Pairs | O(n) | O(1) | Hard | ⭐ bits(num1 OR num2) + bits(num1 AND num2) = bits(num1) + bits(num2) |
| 2506. Count Pairs Of Similar Strings | O(n) | O(n) | Easy | |
| 2897. Apply Operations on Array to Maximize Sum of Squares | O(n) | O(1) | Hard | ⭐⭐ |
| 3022. Minimize OR of Remaining Elements Using Operations | O(n) | O(1) | Hard | ⭐⭐⭐ |
| C++ 0b表示binary number，比如0b10 = 2, 0b111 = 7 python 0b表示binary number，比如0b10 = 2, 0b111 = 7
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 001 Two Sum | O(n) | O(n) | Easy | |
| 036. Valid Sudoku | O(9*9) | O(9) | Medium | 🔍 用bit比较快，比如i在横着第2行出现, row[2] |
| 049. Group Anagrams | O(n * glogg) | O(n) | Medium | 经典 面试题, python list不能作为字典的key,但是tuple可以 |
| 149. Max Points on a Line | O(n^2) | O(n) | Hard | 每到一点，算跟别的点的斜率，注意1. 重合的点，2.斜率没有的定义的点, 在每一点都重新建一个hashmap |
| 187. Repeated DNA Sequences | O(n) | O(n) | Medium | 🔍 rolling hash (rabin-karp),
|
| 202. Happy Number | O(k) | O(k) | Easy | 要么是happy number，要么转化过程陷入循环 |
| 204. Count Primes | O(n) | O(n) | Easy | count从小往大后eliminate，注意要尽可能efficient |
| 205. Isomorphic Strings | O(n) | O(1) | Easy | 可以记录相同位置字母出现的上一位，或者把s,t字母相互关联起来, python 可以用find+map or zip+set |
| 217. Contains Duplicate | O(n) | O(n) | Easy | easy one, 可以用sort + unique |
| 219. Contains Duplicate II | O(n) | O(n) | Easy | easy one |
| 249. Group Shifted Strings | O(n) | O(n) | Medium | |
| 290. Word Pattern | O(n) | O(n) | Easy | 思路和205. Isomorphic Strings 一样 |
| 299. Bulls and Cows | O(n) | O(1) | Easy | One pass: 如果guess[i] 和 secret[i]一样, bull++, 不一样，++m[sec[i]], --m[guess[i]] python 可以用两个collectons.Counter相减, 得到重合的set |
| 325. Maximum Size Subarray Sum Equals k | O(n) | O(1) | Medium | Similar Question: |
| 336. Palindrome Pairs | O(n * k^2) | O(n*k) | Hard | 🔍trie |
| 387. First Unique Character in a String | O(n) | O(n) | Easy | 需要 two pass |
| 388. Longest Absolute File Path | O(n) | O(d) | Medium | |
| 409. Longest Palindrome | O(n) | O(1) | Easy | 可以用std::count, 或者可以来回flip map, 当map位true +2 |
| 447. Number of Boomerangs | O(n^2) | O(n) | Easy | 可以用hypot |
| 454. 4Sum II | O(n^2) | O(n) | Medium | 可以把4sum看成two sum, 把A+B的和绑定，把C+D的和绑定，看-C-D是不是在A+B的map里 |
| 473. Matchsticks to Square | O(n * s * 2^n) | O(n * (2^n + s)) | Medium | DFS or Bit Mask |
| 523. Continuous Subarray Sum | O(n) | O(k) | Medium | 🔍求开始数到所有i的和的余数，如果现在这个的余数之前遇到过，表示，两个数之间有数的和正好整除k |
| 525. Contiguous Array | O(n) | O(n) | Medium | 😍把所有的0变成-1， 所以当有sum[i,j] = 0时 => [i,j]中有同等的1 和 0， Similar Question: |
| 532. K-diff Pairs in an Array | O(n) | O(n) | Easy | 🔍one pass解: 两个hashset, lookup 和res, 找的时候既向上数又向下数, 为了避免重复, set(res)只push下限,结果就是res size |
| 554. Brick Wall | O(n) | O(m) | Meidum | 相当于求最多经过砖头缝缝 |
| 560. Subarray Sum Equals K | O(n) | O(k) | Medium | 🔍用hashmap记录每点的rolling sum(0,i)， 那么只需要找(0,i)的sum - k在不在map中，在的话 表示存在一点[0,j] + k = (0,i)的sum， res += map[sum-k] (可能一个sum出现很多遍) Similar Question: |
| 561. Array Partition I | O(n) | O(n) | Easy | Sort or Bucket Sort |
| 575. Distribute Candies | O(n) | O(n) | Easy | 对比set的长度和candies.size()/2的长度, C++可以用bitset |
| 594. Longest Harmonious Subsequence | O(n) | O(n) | Easy | |
| 599. Minimum Index Sum of Two Lists | O((m + n) * l) | O(m * l) | Easy | |
| 609. Find Duplicate File in System | O(n * k) | O(n * k) | Medium | |
| 705. Design HashSet | O(1) | O(n) | Easy | ⭐⭐ |
| 706. Design HashMap | O(1) | O(n) | Easy | ⭐⭐⭐ list find_if, remove_if |
| 721. Accounts Merge | O(nlogn) | O(n) | Medium | 🔍 Union Find, 不能用简单的hash table 找parent, 比如 (1@com, 2@com), (3@com, 4@com), (4@com, 2@com), 不用Union find分成两组 |
| 748. Shortest Completing Word | O(n) | O(1) | Medium | |
| 771. Jewels and Stones | O(n+m) | O(n) | Easy | |
| 811. Subdomain Visit Count | O(n) | O(n) | Easy | |
| 822. Card Flipping Game | O(n) | O(n) | Medium | 先把front[i]和end[i] 一样的插入到hash set, 再loop front & end, 选取不在hash set中最小的 |
| 825. Friends Of Appropriate Ages | O(n+k^2) | O(k) | Medium | 用hash map存age和count, loop两层hashmap, 判断内层和外层key是否满足条件, 满足的话更新结果 |
| 1010. Pairs of Songs With Total Durations Divisible by 60 | O(n) | O(1) | Medium | |
| 1152. Analyze User Website Visit Pattern | O(n^4) | O(n) | Medium | |
| 1347. Minimum Number of Steps to Make Two Strings Anagram | O(n) | O(n) | Medium | |
| 1418 Display Table of Food Orders in a Restaurant | O(n + tlogt + flogf) | O(n) | Medium | ✏️C++ transform |
| 1711. Count Good Meals | O(n) | O(n) | Medium | |
| 2183. Count Array Pairs Divisible by K | O(n^2) | O(n) | Hard | |
| 2347. Best Poker Hand | O(1) | O(1) | Easy | ❌ Python Switch Case |
| 2357. Make Array Zero by Subtracting Equal Amounts | O(n) | O(n) | Easy | |
| [2365. Task Scheduler II | O(n) | O(n) | Easy | ⭐ Python Counter 相加 |
| 2364. Count Number of Bad Pairs | O(n) | O(n) | Medium | |
| 2365. Task Scheduler II | O(n) | O(n) | Medium | ⭐ 公式变形 |
| 2367. Number of Arithmetic Triplets | O(n) | O(n) | Easy | |
| 2374. Node With Highest Edge Score | O(n) | O(n) | Medium | |
| 2661. First Completely Painted Row or Column | O(n*m) | O(n*m) | Medium | |
| 2870. Minimum Number of Operations to Make Array Empty | O(n) | O(1) | Medium | |
| summary |
|---|
sliding windows: windows都是看以当前字母结尾的window. 比较对象target(长度为len), 被比较对象s2
|
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 003. Longest Substring Without Repeating Characters | O(n) | O(n) | Medium | ⭐⭐Sliding Windows |
| 030. Substring with Concatenation of All Words | O((m+n)*k) | O(n*k) | Hard | ⭐⭐⭐Sliding Windows |
| 076. Minimum Window Substring | O(n) | O(k) | Hard | ⭐⭐⭐ |
| 209. Minimum Size Subarray Sum | O(n) | O(1) | Medium | 🔍
|
| 259. 3Sum Smaller | O(n^2) | O(1) | Medium | ⭐⭐ |
| 346. Moving Average from Data Stream | O(1) | O(n) | Easy | |
| 424. Longest Repeating Character Replacement | O(n) | O(1) | Medium | ⭐⭐⭐🔍sliding window: 记录window的初始点, 如果当前长度 - 最大count > k, ++start(保持windows的最大长度), 如果满足，start不变，结果是s.size()-start |
| 438. Find All Anagrams in a String | O(n) | O(1) | Medium | ⭐⭐⭐sliding window: 跟567. Permutation in String思路一样
|
| 567. Permutation in String | O(n) | O(1) | Medium | ⭐⭐⭐sliding Window |
| 643. Maximum Average Subarray I | O(n) | O(1) | Easy | 最简单的sliding window |
| 683. K Empty Slots | O(n) | O(n) | Hard | ⭐⭐⭐
Similar Question |
| 713. Subarray Product Less Than K | O(n) | O(1) | Medium | 🔍 Sliding Window |
| 862. Shortest Subarray with Sum at Least K | O(n) | O(k) | Hard | |
| 763. Partition Labels | O(n) | O(n) | Medium | hashmap/sliding windows |
| 904. Fruit Into Baskets | O(n) | O(1) | Medium | Rephrase Question: return the longest subarray's length which only contains 2 different elements |
| numSubarraysWithSum. Binary Subarrays With Sum | O(n) | O(1) | Medium | |
| 992. Subarrays with K Different Integers | O(n) | O(1) | Medium | |
| 1004. Max Consecutive Ones III | O(n) | O(1) | Medium | |
| 1234. Replace the Substring for Balanced String | O(n) | O(t) | Medium | |
| 1248. Count Number of Nice Subarrays | O(n) | O(k) | Medium | |
| 1358. Number of Substrings Containing All Three Characters | O(n) | O(1) | Medium | |
| 1425. Constrained Subsequence Sum | O(n) | O(1) | Medium | |
| 1493. Longest Subarray of 1's After Deleting One Element | O(n) | O(1) | Medium | |
| 1838. Frequency of the Most Frequent Element | O(logn) | O(1) | Medium | |
| 1839. Longest Substring Of All Vowels in Order | O(n) | O(1) | Medium |
// 438. Find All Anagrams in a String
//s2: "cbaebabacd" s1: "abc"
//Output: 0, 6]
//固定windows长度
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
vector<int>map(26,0);
for(auto i: s1)
map[i-'a']++;
int len = s1.size(), count = s1.size();
vector<int>res;
for(int i = 0; i<s2.size();i++){
if(map[s2[i]-'a']-->0) count--;
if(count == 0) res.push_back(i-len+1);
if(i>=len-1){
if(++map[s2[i-len+1]-'a'] > 0) count++;
}
}
return res;
}
};
//不固定windows长度, 方法一:
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
vector<int>map(26,0);
for(auto i: s1)
map[i-'a']++;
int len = s1.size(), left = 0;
vector<int>res;
for(int i = 0; i<s2.size();i++){
map[s2[i]-'a']--;
if(map[s2[i] - 'a'] <0)
while( map[s2[i]-'a'] < 0) map[s2[left++]-'a']++;
/* or
//correct
while( map[s2[left] - 'a']++ >= 0 )
++left;
++left;
//wrong: 比如 ab: eabc, left 会一直停在0(e)
while( map[s2[left] - 'a'] >= 0 )
map[s2[left++]- 'a']++
*/
if(i-left+1 == len){
res.push_back(left);
}
}
return res;
}
};
//不固定windows长度 方法二:
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
vector<int>map(26,0);
for(auto i: s1)
map[i-'a']++;
int len = s1.size(), left = 0;
vector<int>res;
for(int i = 0; i<s2.size();i++){
map[s2[i]-'a']--;
if(map[s2[i] - 'a'] <0)
while(map[s2[left++]-'a']++ >= 0);
//cout<<i <<" left "<<left<<endl;
if(i-left+1 == len){
res.push_back(left);
}
}
return res;
}
};
/*
"cbaebabacd"
"abc"
DEBUG stdout
0 left 0
1 left 0
2 left 0
3 left 4
4 left 4
5 left 4
6 left 5
7 left 6
8 left 6
9 left 10
*/
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 020. Valid Parentheses | O(n) | O(n) | Easy | ❌注意return true if stack is empty |
| 032. Longest Valid Parentheses | O(1) | O(n) | Hard |
|
| 042. Trapping Rain Water | O(n) | O(1) | Hard | Greedy/Descending Stack |
| 071. Simplify Path | O(n) | O(n) | Medium | ✏️ Split stringstream + getline 可以处理连续的delimiter 比如delimiter是/, 可以parse//c/d// 为c 和d, vectro<string>的 join |
| 084. Largest Rectangle in Histogram | O(n) | O(n) | Hard |
|
| 085. Maximal Rectangle | O(n*m) | O(m) | Hard | ⭐
|
| 101. Symmetric Tree | O(n) | O(h) | Easy | ❌ ⭐ 注: iterative stack push 顺序 |
| 150. Evaluate Reverse Polish Notation | O(n) | O(n) | Medium | ✏️ Python Lambda Function in dictionary 🔍 C++ recursive solution |
| 155. Min Stack | O(n) | O(1) | Easy/Medium | ⭐ Descending Stack: 两个stack,一个用来放正常的顺序，另一个作为min |
| 173. Binary Search Tree Iterator | O(1) | O(h) | Medium | ⭐⭐307. Range Sum Query - Mutable 逻辑类似, 不要先全部走完 |
| 232. Implement Queue using Stacks | O(1), amortized | O(n) | Easy | ⭐ 两个stack in & out, in用来push, top: 假如out为空，dump in to out |
| 224. Basic Calculator | O(n) | O(n) | Hard | |
| 227. Basic Calculator II | O(n) | O(n) | Medium | ❌ 用sign=1记录+, -1记录减, sign = 2 记录*， 3记录除, 上一个sign是乘或除，先进行operation |
| 331. Verify Preorder Serialization of a Binary Tree | O(n) | O(n) | Medium | 😍😍✏️stringstream + getline
|
| 341. Flatten Nested List Iterator | O(n) | O(h) | Medium | 😍😍stack + recursion从最后往前loop, queue从前往后loop, ✏️✏️C++/Python Iterator, 要存iterator, 不能存vector, 因为存vector memory会很大 |
| 385. Mini Parser | O(n) | O(h) | Medium | 遇到',' ']' 把之前的integer add， 比如[-1], [123,456], 遇到']',把现在这个nested list加入上个nested list |
| 394. Decode String | O(n) | O(h) | Medium | 🔍可以看看recursive 的解, 程序设计: 怎么设计一个好的stack, 类似726. Number of Atoms
|
| 456. 132 Pattern | O(n) | O(h) | Medium | 🎅🎅 寻找 s1 < s3 < s2，从后向前，Descending stack, 难点: 理解stack让s2 逐渐变大, 但s3可增也可减, 因为s2减小前就return true了 |
| 503. Next Greater Element II | O(n) | O(n) | Medium | |
| 636. Exclusive Time of Functions | O(n) | O(n) | Medium | 🔍stack 存的是上个job的id |
| 682. Baseball Game | O(n) | O(n) | Easy | ❌bad problem description |
| 726. Number of Atoms | O(n^2) | O(n) | Hard | 类似 394. Decode String |
| 735. Asteroid Collision | O(n) | O(n) | Medium | 🎅 碰撞发生只能是新来的小于0，stack top > 0 |
| 736. Parse Lisp Expression | O(n) | O(n) | Hard | ❌stack需要两个，一个是存string dict(用来储存let的字典), 一个存string vector(用来储存上个string的split), 遇到'(', 如果之前是let, 先存map, 然后push进两个stack, string vector清空，字典不清空 。 遇到')', 算当前的, 把结果push到上个string(stkstring.top()) 的结尾, pop两个stack |
| 739. Daily Temperatures | O(n) | O(n) | Medium | 🔍 Ascending/Descending stack, 可以正向也可以反向 |
| 0901. Online Stock Span | O(n) | O(n) | Medium | |
| 1063. Number of Valid Subarrays | O(n) | O(n) | Hard | Ascending Stack Similar Question: |
| 1762. Buildings With an Ocean View | O(n) | O(n) | Medium | |
| 2281. Sum of Total Strength of Wizards | O(n) | O(n) | Hard | Similar Question: |
| Ascending & Descending Stack 按照 container的顺序进行排序 |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 002. Add Two Numbers | O(n) | O(1) | Medium | |
| 021. Merge Two Sorted Lists | O(n) | O(1) | Easy | |
| 023. Merge k Sorted Lists | O(nklogk) | O(1) | Hard | ⭐ Heap, Divide Conquer, 注: 不能用一直用0作为l 和r比，这样的话，l的size会增加的很快，到最后l size快成位nk了, ✏️ vector 的 make_heap, heap_push, pop_heap |
| 024. Swap Nodes in Pairs | O(n) | O(1) | Easy | ⭐ recursion 解 |
| 025. Reverse Nodes in k-Group | O(n) | O(1) | Hard | 类似206 Reverse Linked List |
| 061. Rotate List | O(n) | O(1) | Medium | |
| 082. Remove Duplicates from Sorted List II | O(n) | O(1) | Medium | |
| 083. Remove Duplicates from Sorted List | O(n) | O(1) | Easy | 不能用recusion, recursion的话会用pass n回linked list，用O(n)space, iterative解space只用O(1),tree可以用recursion原因是它的stack space是O(logn) |
| 138. Copy List with Random Pointer | O(n) | O(1) | Medium | ⭐ 1. 先把每个node复制一个，把复制的贴在被复制的后面 2. loop node(现在长度是2n), 把cur->next->random = cur->random->next，因为cur->random->next是复制cur->random过来的 3. 最后结果就是把每个偶数位的node连接起来，同时要消除偶数的node(长度由2n变回n)，否则结果是修改了原来的node |
| 147. Insertion Sort List | O(n^2) | O(1) | Medium | Sort priority_queue vs multiset comparator |
| 148. Sort List | O(nlogn) | O(logn) | Medium | Sort
|
| 160. Intersection of Two Linked Lists | O(n+m) | O(1) | Easy | 利用的是 lA + lB_1 = lA_1 + lB (lenA + B交点前的长度 = lenB + A交点前的长度), pA，pB 每次都前进一步，pA到end,pA设为Bhead, pB到end,pB设为Aend, 这种尾对头只换一次，第二次pA 或者pB到end 返回NULL(就是没有交点) |
| 203. Remove Linked List Elements | O(n) | O(1) | Easy | remove cur->next |
| 206. Reverse Linked List | O(n) | O(1) | Easy | ⭐⭐⭐ |
| 234. Palindrome Linked List | O(n) | O(1) | Easy | ⭐⭐ revese list前面部分，然后reverse之后，逐个对比前半部分是否等于后半部分的值 |
| 237. Delete Node in a Linked List | O(n) | O(1) | Easy | 把node->next的val提到node val然后delete node->next |
| 328. Odd Even Linked List | O(n) | O(1) | Medium | ⭐⭐⭐
|
| 445. Add Two Numbers II | O(n+m) | O(m+n) | Medium | 用两个stack,把每个list值push 进stack，最后push进的先算 |
| 725. Split Linked List in Parts | O(n) | O(1) | Medium | 每次前进到此次push进vector的最后一位, 然后断链, 第i个vector长度为 n//k + (i< n%k) |
| 817. Linked List Components | O(n+m) | O(m) | Medium | 把vector转化成unordered_set, 然后判断每个val,是不是在unordered_set里面 |
| 1171. Remove Zero Sum Consecutive Nodes from Linked List | O(n) | O(n) | Medium | |
| 1836. Remove Duplicates From an Unsorted Linked List | O(n) | O(n) | Medium | |
| LinkedList 当head, cur 指向同一点, cur = cur->next; | head 不会改变, 但是当cur在head之后，head包含cur, cur = cur->next, head会跳过cur这点 | |||
| two pointer 1.whiLe(fast->next && fast->Next->next) 是找中点, 比如1-2-3-4-5-6，slow最后等于3 2.whiLe(fast && fast->Next) 是找中后一点,比如1-2-3-4-5-6，slow最后等于4, 1-2-3-4-5 最后是3 |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 239. Sliding Window Maximum | O(n) | O(k) | Hard | ⭐⭐⭐ Monoqueue using Deque
|
| 362. Design Hit Counter | O(1) | O(1) | Medium | Should consider remove performance |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
|
||||
| 253. Meeting Rooms II | O(nlogn) | O(n) | Medium | ⭐⭐ |
| 264. Ugly Number II | O(n) | O(1) | Medium | 😍🎅🎅
|
| 295. Find Median from Data Stream | O(nlogn) | O(1) | Medium | 虽是hard, 逻辑简单, 两个heap, minheap, maxheap, ✏️可以看看python heapq用法 heappushpop |
| 313. Super Ugly Number | O(n*k) | O(n+k) | Medium | 类似 264. Ugly Number II |
| 373. Find K Pairs with Smallest Sums | O(k * log(min(n, m, k))) | O(min(n, m, k)) | Medium | 🔍注: 不用hashset, 可不重复push 进heap 🎅不能用two pointer, 比如 [1,7], [2,6], 结果是[1,2],[1,6],[2,7], two pointer给的是[1,2],[1,6],[6,7] ✏️: python itertools.product, itertools.islice O(k) solution |
| 378. Kth Smallest Element in a Sorted Matrix | O(k * log(min(n, m, k))) | O(min(n, m, k)) | Medium | Binary Search, Heap, ZigZag Search |
| 407. Trapping Rain Water II | O(m * n * (logm + logn)) | O(m*n) | Hard | 😍🎅
|
| 632. Smallest Range Covering Elements from K Lists | O(nklogk) | O(k) | Hard | 😍🎅
|
| 759. Employee Free Time | O(klogk) | O(k) | Hard | Heap O(Nlogk) or SweepLine O(klogk) |
| 846. Hand of Straights | O(nlogn) | O(n) | Medium | 🔍
|
| 846. Hand of Straights | O(nlogn) | O(n) | Hard | |
| 973. K Closest Points to Origin | O(n) average | O(1) | Easy | ✏️Quick-Select, Multiset Comparator |
| 1046. Last Stone Weight | O(nlogn) | O(n) | Easy | |
| 1834. Single-Threaded CPU | O(nlogn) | O(n) | Medium | |
| 2402. Meeting Rooms III | O(mlogm + n + mlogn) | O(n) | Hard | |
| 2519. Count the Number of K-Big Indices | O(nlogn) | O(n) | Hard | |
Two pointer 用于
- detect cycle
- sorted array比大小,一个array一个pointer
- linked list找到middle point
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 019. Remove Nth Node From End of List | O(n) | O(1) | Medium | 🔍two pointer, list总长l, 需要remove的index是l-n, slow要前进到l-n-1, 所以先前进n个，再前进到尾部就是l-n-1 |
| 086. Partition List | O(n) | O(1) | Medium | 🔍
|
| 141. Linked List Cycle | O(n) | O(1) | Easy | ❌ |
| 142. Linked List Cycle II | O(n) | O(1) | Medium | 🔍具体数学解释, 类似287. Find the Duplicate Number |
| 143. Reorder List | O(n) | O(1) | Medium | 😚🎅 用fast & slow先找到medium的点，slow到结尾所有的点reverse, 然后p1 = head, p2 = middle后一点，一个p1, 一个p2 插进pointer，就是结果 |
| 167.Two Sum II - Input array is sorted | O(n) | O(1) | Easy | ❌ two pointer, 一个从开始位置，一个从末尾的位置 |
| 283. Move Zeroes | O(n) | O(1) | Easy | ❌ 记录swap后第一个0位置 |
| 287. Find the Duplicate Number | O(n) | O(1) | Easy | 😍🎅 类似142. Linked List Cycle II ,有duplicate一定会有cycle, 难点: 找起点
|
| 344. Reverse String | O(n) | O(1) | Easy | 🔍bit来进行swap |
| 349. Intersection of Two Arrays | O(n+m) | O(min(m, n)) | Easy |
|
| 350.Intersection of Two Arrays II | O(n+m) | O(1) | Easy | ❌
|
| 457. Circular Array Loop | O(n) | O(1) | Medium | ❌array loop必须是单向的, 比如1->2, 2->1 不算是loop，循环array每次两个pointer检查有没有loop,如果没有loop,把这次所有走过的点都标成0,下次不用再走了, 类似141. Linked List Cycle |
| 611. Valid Triangle Number | O(n^2) | O(1) | Medium | 🎅(无法达到O(n))，先sort然后两个pointer,每一个都指向一个边, |
| 777. Swap Adjacent in LR String | O(n) | O(1) | Medium | 🎅 难点是: 寻找left 和 right. R是向前走，L是向后走（swap R 和L都需要X）, 两个pointer，遇到X往前跳 |
| 826. Most Profit Assigning Work | O(mlogm + nlogn) | O(1) | Medium | 😍🔍
|
| 828. Unique Letter String | O(n) | O(1) | Hard | 😍🎅
|
| 838. Push Dominoes | O(n) | O(n) | Medium | 🎅🎅🎅 |
| 844. Backspace String Compare | O(m+n) | O(1) | Easy | 两个pt，都从s,t 从后往前对比 |
| 986. Interval List Intersections | O(m+n) | O(1) | Medium | |
| 1570. Dot Product of Two Sparse Vectors | O(n) | O(n) | Medium | |
| 1750. Minimum Length of String After Deleting Similar Ends | O(n) | O(1) | Easy | |
| 2337. Move Pieces to Obtain a String | O(n) | O(1) | Medium | |
| 2348. Number of Zero-Filled Subarrays | O(n) | O(1) | Medium | |
| 2781. Length of the Longest Valid Substring | O(n^2) | O(k) | Hard | |
| 2825. Make String a Subsequence Using Cyclic Increments | O(n) | O(1) | Medium |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 056. Merge Intervals | O(nlogn) | O(n) | Medium | 类似的题 |
| 057. Insert Interval | O(nlogn) | O(n) | Hard | 类似的题 |
| 075. Sort Colors | O(n) | O(1) | Medium | 🎅 Tri Partition, 小的放前面, 大的放最后 |
| 088. Merge Sorted Array | O(n) | O(1) | Easy | ❌从后往前 |
| 147. Insertion Sort List | O(n^2) | O(1) | Medium | 跟148. Sort List 一样 |
| 148. Sort List | O(nlogn) | O(logn) | Medium | priority_queue vs multiset comparator
|
| 164. Maximum Gap | O(n) | O(n) | Hard | 😍🔍
|
| 164. Maximum Gap | O(n) | O(n) | Hard | 😍🔍
|
| 179. Largest Number | O(nlogn) | O(n) | Medium | ✏️✏️ Python Lambda Sort |
| 218. The Skyline Problem | O(nlogn) | O(logn) | Hard | 😍😍 priority_queue or multiset(看critical point) |
| 252. Meeting Rooms | O(nlogn) | O(1) | Easy | ❌ |
| 274. H-Index | O(n) | O(n) | Medium | ❌counting Sort |
| 315. Count of Smaller Numbers After Self | O(nlogn) | O(n) | Hard | MergeSort, BIT Similar Question: |
| 324. Wiggle Sort II | O(n) average | O(1) | Medium | ❌(1 + 2*index) % (n | 1)保证median左面数map奇数位，mediam右面的数map偶数位
|
| 327. Count of Range Sum | O(nlogn) | O(n) | Hard | MergeSort with Count, BIT Similar Question: |
| 347. Top K Frequent Elements | O(n) | O(n) | Medium | 😍 Bucket Sort, Quick Select,
|
| 406. Queue Reconstruction by Height | O(n * sqrt(n))~O(n^2) | O(n) | Medium | 😚 关键是认清sort的顺序 先把height大的安排了，如果height一样再sort k有小到大。 sqrt(n)解是一样的sort，但是把sort之后的插入到不同的组中，每个组不超过sqrt(n)个元素 |
| 462. Minimum Moves to Equal Array Elements II | O(nlogn) | O(n) | Medium | Medium是最小化Sum of Absolute Deviations; Quick Select: O(n) on average |
| 451. Sort Characters By Frequency | O(n) | O(n) | Medium | Bucket Sort, Quick Select(n-th elements) O(nlogn), priority_queue O(nlogn) |
| 692. Top K Frequent Words | O(nlogk) | O(n) | Medium | Bucket Sort, Quick Select(n-th elements), priority_queue |
| 853. Car Fleet | O(nlogn) | O(n) | Medium | Greedy: sort postion又大到小，再sort到target的时间由小到大 |
| 937. Reorder Data in Log Files | O(nlogn) | O(n) | Medium | stable_partition, string_view |
| 910. Smallest Range II | O(nlogn) | O(1) | Medium | ⭐⭐⭐ |
| 1029. Two City Scheduling | O(n) average | O(n) | Easy | Greedy**,quick select |
| 1170. Compare Strings by Frequency of the Smallest Character | O(q+w) | O(1) | Mediem | Count Sort |
| C++priority_queue<pair<int,int>>pq 先对比first, top是first最大的， constructor: greater<int>是让top返回最小的数,大的数放后面 |
python的heappop()先pop对比first,then second, top是first最小的 | |||
| 1365 How Many Numbers Are Smaller Than the Current Number | O(n+m) | O(m) | Easy | 🔍O(n+m) Solution Counting Sort 🔍Python Counting Sort |
| 1366. Rank Teams by Votes | O(n) | O(1) | Medium | 🔍Python Sort list based on Dictonary value |
| 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts | O(hlogh + vlogv) | O(1) | Medium | |
| 1840. Maximum Building Height | O(nlogn) | O(1) | Hard | |
| 1851. Minimum Interval to Include Each Query | O(nlogn + qlogq) | O(n) | Hard | |
| 2268. Minimum Number of Keypresses | O(n) | O(1) | Medium |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 095. Unique Binary Search Trees II | O(4^n / n^(3/2)) | O(4^n / n^(3/2)) | Medium | 😍 🔍loop start -> end. Generate vector of left subtree 和right subtree, 然后排列组合把他们弄在一起 |
| 096. Unique Binary Search Trees | O(n) | O(1) | Medium | DP, cartesian product 作为root，sum(#left + #right) Catalan number |
| 098. Validate Binary Search Tree | O(n) | O(1) | Medium | 用prev 点, iterative + recurssion |
| 100. Same Tree | O(n) | O(h) | Easy | ❌ |
| 104. Maximum Depth of Binary Tree | O(n) | O(h) | Easy | ❌ |
| 105. Construct Binary Tree from Preorder and Inorder Traversal | O(n) | O(h) | Medium | 😍😍 🔍🔍注意和889. Construct Binary Tree from Preorder and Postorder Traversal stack的区别. preorder 第一个是tree的root, inorder 中root->val左面root的left tree,右面root的right tree, |
| 106. Construct Binary Tree from Inorder and Postorder Traversal | O(n) | O(h) | Medium | 😍😍 🔍🔍 O(1) memory 和 stack |
| 108. Convert Sorted Array to Binary Search Tree | O(n) | O(logn) | Easy | ❌ 跟095. Unique Binary Search Trees II逻辑一样 binary tree height 需要balanced |
| 109. Convert Sorted List to Binary Search Tree | O(n) | O(logn) | Medium | 🔍注意O(N)的解，不是two pointer的 |
| 110. Balanced Binary Tree | O(n) | O(h) | Medium | 😚 跟095. Unique Binary Search Trees II类似 用bottom-up 比top-down 更efficient |
| 111. Minimum Depth of Binary Tree | O(n) | O(h) | Medium | ❌if not left: return h(r.right)+1; , if not right: return h(r.left)+1; else: return min(h(r.right), h(r.left))+1; |
| 114. Flatten Binary Tree to Linked List | O(n) | O(h) | Medium | 🎅 preorder 的reverse |
| 116. Populating Next Right Pointers in Each Node | O(n) | O(1) | Medium | 审题: perfect binary tree
|
| 124. Binary Tree Maximum Path Sum | O(n) | O(h) | Hard | 🔍not hard question |
| 129. Sum Root to Leaf Numbers | O(n) | O(h) | Medium | O(1) extra memory |
| 241. Different Ways to Add Parentheses | O(n* 4^n / n^(3/2)) | O(n * 4^n / n^(3/2)) | Medium | 😍 算sign前的，算sign后的,然后做前和后的permutation和 |
| 337. House Robber III | O(n) | O(h) | Medium | 🎅Greedy Algorithm. 返回vector, vector[0]存的是用上一个最大的获取值，vector[1]存的是不用上一个 最大的获取值 |
| 395. Longest Substring with At Least K Repeating Characters | O(n) | O(n) | Medium | 😍😍
|
| 404. Sum of Left Leaves | O(n) | O(h) | Easy | ❌ |
| 437. Path Sum III | O(n) | O(h) | Easy | 🔍一定用unorderedmap , 不能用unordered_set, 比如 -5,5,-6,6,4, 要sum = 4, 可以从-5到4 或者-6 到4 |
| 669. Trim a Binary Search Tree | O(n) | O(h) | Easy | 😚 |
| 671. Second Minimum Node In a Binary Tree | O(n) | O(h) | Easy | ❌ |
| 761. Special Binary String | O(n^2) | O(n) | Hard | ❌Bad problem description Divide-conquer, 把每个special string 再分成小的special string,然后sort |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 004. Median of Two Sorted Arrays | O(log(min(m, n))) | O(1) | Hard | ⭐⭐⭐ |
| 033. Search in Rotated Sorted Array | O(log(n)) | O(1) | Medium | 💜🎅Similar Question: |
| 034. Find First and Last Position of Element in Sorted Array | O(log(n)) | O(1) | Medium | lowerbound/upperbound/EqualRange, lowerbound 可以convert to int |
| 35. Search Insert Position | O(log(n)) | O(1) | Easy | |
| 069. Sqrt(x) | O(log(n)) | O(1) | Easy | 🎅 Bit Solution similar Question |
| 074. search a 2D Matrix | O(logm + logn) | O(1) | Medium | lower_bound, upper_bound lambda |
| 081. Search in Rotated Sorted Array II | O(logn) | O(1) | Medium | 💜🎅 Similar Question: |
| 153. Find Minimum in Rotated Sorted Array | O(logn) | O(1) | Medium | Similar Question: |
| 154. Find Minimum in Rotated Sorted Array II | O(logn) ~ O(n) | O(1) | Hard | Similar Question: |
| 162. Find Peak Element | O(logn) | O(1) | Medium | ❌ |
| 222. Count Complete Tree Nodes | O((logn)^2) | O(1) | Medium | 注意审题 complete tree |
| 275. H-Index II | O(logn) | O(1) | Medium | |
| 278. First Bad Version | O(logn) | O(1) | Easy | |
| 300. Longest Increasing Subsequence | O(nlogn) | O(n) | Medium | 💜🎅🎅🎅 similar question |
| 354. Russian Doll Envelopes | O(nlogn) | O(n) | Hard | 💜🎅similar question |
| 363. Max Sum of Rectangle No Larger Than K | O(min(m, n)^2 * max(m, n) * logn(max(m, n))) | O(max(m, n)) | Hard | 💜🎅🎅, 利用Set |
| 367. Valid Perfect Square | O(logn) | O(1) | Easy | Similar Question |
| 374. Guess Number Higher or Lower | O(logn) | O(1) | Easy | |
| 378. Kth Smallest Element in a Sorted Matrix | O(n * log(MAX - MIN) | O(1) | Medium | l=m[0][0], r=m[-1][-1], binary search 是否至少有k个数小于等于mid |
| 410. Split Array Largest Sum | O(nlogn) | O(1) | Hard | 💜 |
| 436. Find Right Interval | O(nlogn) | O(n) | Medium | map lower bound |
| 475. Heaters | O((m + n) * logn) | O(1) | Easy |
|
| 528. Random Pick with Weight | O((n*logn) | O(n) | Medium | |
| 540. Single Element in a Sorted Array | O(logn) | O(1) | Medium | |
| 658. Find K Closest Elements | O(logn+k) | O(1) | Medium | x-arr[left-1]<=arr[right]-x 保证left一定是起点，right是最后数后面一位 |
| 668. Kth Smallest Number in Multiplication Table | O(log(mn)*min(n,n)) | O(1) | Hard | binary search [1,m*n], isValid判断是否有至少有k个element在乘法表中 |
| 715. Range Module | O(n) | O(n) | Hard | ⭐⭐⭐ |
| 719. Find K-th Smallest Pair Distance | O(nlogn + nlogw) | O(1) | Hard | sort nums, l=0, r = nums[-1]-nums[0], binary search是否有k个数大于等于mid在num中 |
| 744. Find Smallest Letter Greater Than Target | O(logn) | O(1) | Easy | 判断最后一个字母是不是大于target, 大于的话用upperbound，否则返回第一个char |
| 786. K-th Smallest Prime Fraction | O(nlogr) | O(1) | Hard |
|
| 793.Preimage Size of Factorial Zeroes Function | O((logk)^2) | O(1) | Hard | l = 0, r=5*k, binary search mid是否有k个零的0，有的话r=mid, 否则l = mid+1, 最后再判断l是否有k个0, 有的话返回5,没有的话返回0 |
| 875. Koko Eating Bananas | O(NlogW) | O(1) | Medium | |
| 981. Time Based Key-Value Store | O(nlogn) | O(n) | Medium | |
| 1060. Missing Element in Sorted Array | O((logN) | O(1) | Medium | 🎅 |
| 1385. Find the Distance Value Between Two Arrays | O((n + m) * logm) | O(1) | Easy | 🎅Binary Search, Two pointer |
| 1818. Minimum Absolute Sum Difference | O((n * logn) | O(n) | Medium | |
| 2055. Plates Between Candles | O((max(q * logn, n)) | O(n) | Medium | |
| 2358. Maximum Number of Groups Entering a Competition | O(logN) | O(1) | Medium | Math / Brain Teaser |
| 3048. Earliest Second to Mark Indices I | O(mlogm) | O(m) | Medium | ⭐⭐⭐ key: 根据bound，每次last_index 是需要更新的 |
| 3049. Earliest Second to Mark Indices II | O(mlogm) | O(m) | Hard | ⭐⭐⭐
|
| 3116. Kth Smallest Amount With Single Denomination Combination | O(2^n * log(k)) | O(2^n) | Hard | itertools.combinations, math.lcm |
| 3134. Find the Median of the Uniqueness Array | O(nlogn) | O(n) | Hard |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 220. Contains Duplicate III | O(nlogn) | O(n) | Medium | set/multiset lower_bound 或者python OrderedDict, 每次popitem(false) pop 最先insert的 |
| 230 Kth Smallest Element in a BST | O(max(h, k)) | O(min(h, k)) | Medium | inorder traversals(从最小的travel到最大的) / stack |
| 235. Lowest Common Ancestor of a Binary Search Tree | O(h) | O(1) | Easy | 利用 binary search tree的性质 |
| 352. Data Stream as Disjoint Intervals | O(logn) | O(n) | Hard | |
| 449. Serialize and Deserialize BST | O(n) | O(h) | Medium | preorder traversals |
| 450. Delete Node in a BST | O(h) | O(h) | Medium |
|
| 530. Minimum Absolute Difference in BST | O(n) | O(h) | Easy | 利用binary search tree的性质 或者inorder traversal 带着前面prev的node val |
| 783. Minimum Distance Between BST Nodes | O(n) | O(h) | Easy | 利用binary search tree的性质 或者inorder traversal 带着前面prev的node val(与530题 解法一样) |
| 1382 Balance a Binary Search Tree | O(n) | O(h) | Medium |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 094. Binary Tree Inorder Traversal | O(n) | O(1) | Medium | Tree |
| 095. Unique Binary Search Trees II | O(4^n / n^(3/2)) | O(4^n / n^(3/2)) | Medium | 😍 🔍loop start -> end. Generate vector of left subtree 和right subtree, 然后排列组合把他们弄在一起 |
| 098. Validate Binary Search Tree | O(n) | O(1) | Medium | 用prev 点, iterative + recurssion |
| 099 Recover Binary Search Tree | O(n) | O(1) | Hard | Tree |
| 100. Same Tree | O(n) | O(h) | Easy | ❌ |
| 104. Maximum Depth of Binary Tree | O(n) | O(h) | Easy | ❌ |
| 101. Symmetric Tree | O(n) | O(h) | Easy | ❌ 注: iterative stack push 顺序 |
| 108. Convert Sorted Array to Binary Search Tree | O(n) | O(logn) | Easy | ❌ 跟095. Unique Binary Search Trees II逻辑一样 binary tree height 需要balanced |
| 109. Convert Sorted List to Binary Search Tree | O(n) | O(logn) | Medium | 🔍注意O(N)的解，不是two pointer的 |
| 110. Balanced Binary Tree | O(n) | O(h) | Medium | 😚 跟095. Unique Binary Search Trees II类似 用bottom-up 比top-down 更efficient |
| 111. Minimum Depth of Binary Tree | O(n) | O(h) | Medium | ❌if not left: return h(r.right)+1; , if not right: return h(r.left)+1; else: return min(h(r.right), h(r.left))+1; |
| 112. Path Sum | O(n) | O(h) | Easy | 🔍(iterative Solution: 如果有right会经过root 两次)[https://github.com/beckswu/Leetcode/blob/master/DFS/112.%20Path%20Sum.cpp#L74] |
| 124. Binary Tree Maximum Path Sum | O(n) | O(h) | Hard | 🔍not hard question |
| 129. Sum Root to Leaf Numbers | O(n) | O(h) | Medium | O(1) extra memory |
| 144. Binary Tree Preorder Traversal | O(n) | O(1) | Medium | Tree |
| 145. Binary Tree Postorder Traversal | O(n) | O(1) | Hard | Tree |
| 199 Binary Tree Right Side View | O(n) | O(h) | Medium | ❌ Easy |
| 222. Count Complete Tree Nodes | O((logn)^2) | O(1) | Medium | |
| 257 Binary Tree Paths | O(n * h) | O(h) | Easy | ❌ Easy |
| 404. Sum of Left Leaves | O(n) | O(h) | Easy | ❌ |
| 437. Path Sum III | O(n) | O(h) | Easy | unorderedmap 存的在现在点之前的 <prefix sum, frequency> pairs. 从中间某点到现在sum = 从root到现在点sum - root到中间某点的sum |
| 515. Find Largest Value in Each Tree Row | O(n) | O(h) | Medium | ❌ DFS / BFS |
| 538. Convert BST to Greater Tree | O(n) | O(h) | Easy | Tree |
| 543. Diameter of Binary Tree | O(n) | O(h) | Easy | Tree |
| 572. Subtree of Another Tree | O(m * n) | O(h) | Easy | |
| 617. Merge Two Binary Trees | O(n) | O(h) | Easy | |
| 623. Add One Row to Tree | O(n) | O(h) | Medium | |
| 637. Average of Levels in Binary Tree | O(n) | O(h) | Easy | |
| 653. Two Sum IV - Input is a BST | O(n) | O(h) | Easy | |
| 671. Second Minimum Node In a Binary Tree | O(n) | O(h) | Easy | ❌ |
| 687. Longest Univalue Path | O(n) | O(h) | Easy | |
| 669. Trim a Binary Search Tree | O(n) | O(h) | Easy | 😚 |
| 814. Binary Tree Pruning | O(n) | O(h) | Medium | |
| 863. All Nodes Distance K in Binary Tree | O(n) | O(h) | Medium | 😍😍Really good question! 不必纠结于one pass, 需要child -> parent map |
| 865. Smallest Subtree with all the Deepest Nodes | O(n) | O(h) | Medium | 🔍DFS, left level == right level 返回root, if left level > right level, 返回left dfs的node else返回right dfs的 |
| 889. Construct Binary Tree from Preorder and Postorder Traversal | O(n) | O(h) | Medium | 😍😍
|
| 1008. Construct Binary Search Tree from Preorder Traversal | O(n) | O(h) | Medium | 🔍Stack / Morris Traversal |
| [1028. Recover a Tree From Preorder Traversal](https://leetcode.com/problems/recover-a-tree-from-preord er-traversal/) | O(n) | O(h) | Hard | 😚 stack / DFS, stack逻辑类似889. Construct Binary Tree from Preorder and Postorder Traversal |
| 1367 Linked List in Binary Tree | O(n+l) | O(h+l) | Medium | |
| 2265. Count Nodes Equal to Average of Subtree | O(n) | O(n) | Medium | |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 112. Path Sum | O(n) | O(h) | Easy | 🔍iterative Solution: 如果有right会经过root 两次 |
| 113 Path Sum II | O(n) | O(h) | Medium | 🔍iterative Solution: 如果有right会经过root 两次 |
| 199 Binary Tree Right Side View | O(n) | O(h) | Medium | ❌ Easy |
| 200 Number of Islands | O(m * n) | O(m * n) | Medium | ✏️ Union Find with Rank Heuristics, ✏️Python Complex number 表示四个DFS 方向 |
| 236 Lowest Common Ancestor of a Binary Tree | O(n) | O(h) | Medium | 🔍 Iterative Solution |
| 257 Binary Tree Paths | O(n * h) | O(h) | Easy | ❌ Easy |
| 282 Expression Add Operators | O(4^n) | O(n) | Hard | 🎅难点: 弄清 cv (cumulative sum), pv(previous sum) 关系, pos 到现在process的index，注意:
|
| 301. Remove Invalid Parentheses | O(C(n, c)) | O(c) | Hard | 😍😍Complexity Analysis
|
| 329. Longest Increasing Path in a Matrix | O(m * n) | O(m * n) | Hard | 😍
|
| 339. Nested List Weight Sum | O(n) | O(n) | Medium | |
| 399. Evaluate Division | O(q*|V|!) | O(e) | Medium | DFS with memiozation 用unordered_map, vector, unordered_set记录是否经过， 跟329. Longest Increasing Path in a Matrix类似 |
| 417. Pacific Atlantic Water Flow | O(m * n) | O(m * n) | Medium | 😍🎅 bit mask, 难点: 起点必须是四个边 |
| 440. K-th Smallest in Lexicographical Order | O(logn) | O(logn) | Hard | 找规律, 不能一个一个算, 要跳缩减区间 |
| 464. Can I Win | O(n!) | O(n) | Medium | 😚DFS+Memoization 难点: Memoization记录的不能是还剩多少到target, 记录是现在可选择的set能不能赢 |
| 489. Robot Room Cleaner | O(n*m) | O(n*m) | Hard | ⭐⭐⭐ |
| 515. Find Largest Value in Each Tree Row | O(n) | O(h) | Medium | ❌ DFS / BFS |
| 638. Shopping Offers | O(n * 2^n) | O(n) | Medium | 🎅✏️ [设计一个好的DFS structure](https://github.com/beckswu/Leetcode/blob/master/DFS/638.%20Shopping%20Offers.cpp#L42] |
| 690. Employee Importance | O(n) | O(h) | Easy | 需要用unordered_map, 因为vector index 不等同于 id |
| 694. Number of Distinct Islands | O(m*n) | O(m*n) | Medium | |
| 733. Flood Fill | O(m*n) | O(m*n) | Easy | ❌ |
| 749. Contain Virus | O((m * n)^(4/3)) | O(m * n) | Hard | 😚 DFS/BFS, every step try each possibility see where is max new Infection area, then build wall and update grid |
| 753. Cracking the Safe | O(k^n) | O(k^n) | Hard | 🎅 Greedy + BrainStorming, 难点:如果设置起始数字，如何Loop 不会有deadlock |
| 756. Pyramid Transition Matrix | O(a^b) | O(a^b) | Medium | bottom-up, bit mask |
| 785. Is Graph Bipartite? | O(|V+E|) | O(|V|) | Medium | DFS/BFS + Bit Mask, 用红蓝两色表vertex，如果相邻的node 一样颜色 return false |
| 797. All Paths From Source to Target | O(p + r * n) | O(n) | Medium | ❌ |
| 802. Find Eventual Safe States | O(|V+E|) | O(|V|) | Medium | 😚 DFS + bit mask 需要定义state 0：unvisited, 1 visited not safe, 2 visited not safe, 3 visited and safe 注意不能用visited 的value 代替boolean 的value |
| 886. Possible Bipartition | O(|V+E|) | O(|V+E|) | Medium | DFS, BFS |
| 980. Unique Paths III | O((m * n) * 2^(m * n)) | O((m * n) * 2^(m * n)) | Medium | DFS, BFS |
| 1367 Linked List in Binary Tree | O(n+l) | O(h+l) | Medium | KMP 🔍C++ 用const auto [] get function return pair |
| 1136. Parallel Courses | O(V+E) | O(V+E) | Medium | topological sort |
| 1368 Minimum Cost to Make at Least One Valid Path in a Grid | O(m*n) | O(m*n) | Medium | BFS + DFS |
| 1377. Frog Position After T Seconds | O(n) | O(n) | Hard | ✏️Python Set |
| 1391. Check if There is a Valid Path in a Grid | O(m*n) | O(1) | Medium | |
| 1806. Minimum Number of Operations to Reinitialize a Permutation | O(n) | O(1) | Medium | Reverse |
| 2359. Find Closest Node to Given Two Nodes | O(n) | O(n) | Medium | |
| 2360. Longest Cycle in a Graph | O(n) | O(n) | Hard | ⭐ |
| 2368. Reachable Nodes With Restrictions | O(V+E) | O(V+E) | Medium | BFS / DFS |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 017. Letter Combinations of a Phone Number | O(n * 4^n) | O(n) | Medium | ✏️Python Lambda Function |
| 022. Generate Parentheses | O(4^n / n^(3/2)) | O(n) | Medium | ✏️Python Trick |
| 037. Sudoku Solver | O((9!)^9) | O(1) | Hard | 可以用bit mask |
| 039. Combination Sum | O(k * n^k) | O(k) | Medium | ✏️Python Trick, Difference between yield and return Similar Question |
| 040. Combination Sum II | O(n * n!) | O(n) | Medium |
Similar Question |
| 046. Permutations | O(\n * n!) | O(n) | Medium | Similar Question |
| 047. Permutations II | O(\n * n!) | O(n) | Medium | ⭐⭐⭐
Similar Question |
| 051. N-Queens | O(n!) | O(n) | Hard | 🔍Python Solution |
| 052. N-Queens-II | O(n!) | O(n) | Hard | ❌ 与051. N-Queens 逻辑一样 |
| 077. Combinations | O(k * C(n, k)) | O(k) | Medium | 😍 Python Multiple Solution |
| 079. Word Search | O(m * n * l) | O(l) | Medium | Simple DFS. smart way: 把visited的字母改了 省掉了hashset, visited |
| 093. Restore IP Addresses | O(1) | O(1) | Medium | recursive & iterative |
| 078. Subsets | O(n * 2^n) | O(1) | Medium | ⭐⭐⭐ Similar Question |
| 090. Subsets II | O(n * 2^n) | O(1) | Medium | ⭐⭐⭐ recursive(逻辑类似040. Combination Sum II) & 😍😍 iterative（插数） Similar Question |
| 126. Word Ladder II | O(n * d) | O(d) | Hard |
|
| 131. Palindrome Partitioning | O(n^2) ~ O(2^n) | O(n^2) | Medium | ⭐⭐⭐ Python Solution Similar Question |
| 140. Word Break II | O(n * l^2 + n * r) | O(n^2) | Hard | 🎅DFS with Memoization, 没有memoization TLE, ✏️C++ Std:function |
| 212. Word Search II | O(m * n * l) | O(l) | Hard | Suffix Trie (backtracking 是把board 暂时改了, 省去了hashset visited), 难度medium左右, ✏️Python Complex number 表示四个DFS 方向, Dictionary setdefault |
| 216. Combination Sum III | O(k * C(n, k)) | O(k) | Medium | 🔍Python itertools.combination |
| 526. Beautiful Arrangement | O(n!) | O(n) | Medium | swap, 注意if 条件, 🔍Python Solution |
| 676. Implement Magic Dictionary | O(n) | O(d) | Medium |
|
| 679. 24 Game | O(1) | O(1) | Hard | Complexity: upper bound of 12* 6 * 2 * 4 * 4 * 4 = 9216 possibilities🔍🔍 Python Solution |
| 698. Partition to K Equal Sum Subsets | O(n* 2^n) | O(2^n) | Medium | 😍😍 非常经典题目,
|
| 784. Letter Case Permutation | _O(n * 2^n) _ | O(1) | Easy | ✏️Python itertools.product |
| 1087. Brace Expansion | O(n * l *log(n *l)) | O(n * l) | Medium | |
| 2352. Equal Row and Column Pairs | O(n^2) | O(n^2) | Medium | suffix Trie / Python Zip |
(注directed vs undirected 区别) undirected graph 设置global visited, directed graph 设置local visited
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 133. Clone Graph | O(N+M) | O(N) | Medium | |
| 261. Graph Valid Tree | O(V+E) | O(V+E) | Medium | Similar Question |
| 277. Find the Celebrity | O(n) | O(1) | Medium | |
| 323. Number of Connected Components in an Undirected Graph | O(V+E) | O(V+E) | Medium | undirected graph connected component, union find |
| 332. Reconstruct Itinerary | O(t! / (n1! * n2! * ... nk!)) | O(t) | Medium | 😍⭐⭐⭐
Similar Question |
| 499. The Maze III | O(nlogn) | O(n) | Hard | |
| 505. The Maze II | O(mnlog(nn)) | O(mn) | Medium | |
| 529. Minesweeper | O(m * n) | O(m + n) | Medium | ⭐⭐简单DFS, Similar Question |
| 547. Number of Provinces | O(n^2) | O(n) | Medium | ⭐⭐⭐ Union Find with Rank Heuristic / DFS, undirected graph 设置global visited, b/c A不能到B 不代表 B 不能到A Similar Question |
| 695. Max Area of Island | O(m*n) | O(m*n) | Medium | ✏️Python Complex number 表示四个DFS 方向 Similar Question |
| 834. Sum of Distances in Tree | O(n) | O(n) | Hard | |
| 841. Keys and Rooms | O(V+E) | O(V+E) | Medium | |
| 947. Most Stones Removed with Same Row or Column | O(k) | O(k) | Medium | ⭐⭐ Similar Question Union find
|
| 994. Rotting Oranges | O(m*n) | O(m*n) | Medium | ⭐⭐ BFS乘以列的个数, 而不是行数 Similar Question |
| 1245. Tree Diameter | O(n) | O(n) | Medium | |
| 1361. Validate Binary Tree Nodes | O(n) | O(n) | Medium | |
| 1466. Reorder Routes to Make All Paths Lead to the City Zero | O(n) | O(n) | Medium | ⭐⭐⭐ no cycle Similar Question |
| 1494. Parallel Courses II | O(2^n) | O(2^n) | Hard | |
| 1786. Number of Restricted Paths From First to Last Node | O(M*(V + ElogV)) | O(n) | Hard | ⭐⭐⭐ Dijkstra's Algorithm, Floyd–Warshall algorithm Similar Question |
| 1971. Find if Path Exists in Graph | O(V + E) | O(V +E) | Easy | ⭐Union Find |
| 2101. Detonate the Maximum Bombs | O(V*(V+E)) | O(V+E) | Medium | ⭐⭐⭐ directed graph, 每个dfs 前设置visited, b/c A不能到B 不代表 B 不能到A , count the max number of child from a node Similar Question |
| 2050. Parallel Courses III | O(n + e) | O(n + e) | Hard | ⭐⭐⭐ |
| 2065. Maximum Path Quality of a Graph | O(V+E + 4^10) | O(V + E) | Medium | |
| 2092. Find All People With Secret | O(M*log M + N) | O(M + N) | Hard | ⭐⭐⭐ undirected graph Union Find |
| 2097. Valid Arrangement of Pairs | O(M+N) | O(M + N) | Hard | ⭐⭐⭐ directed graph Eulerian Path Similar Question |
| 2115. Find All Possible Recipes from Given Supplies | O(V+E) | O(V + E) | Medium | ⭐⭐⭐ directed graph Union Find，topoloigical sort |
| 2316. Count Unreachable Pairs of Nodes in an Undirected Graph | O(V+E) | O(V + E) | Medium | ⭐⭐⭐ undirected graph Union Find |
| 2204. Distance to a Cycle in Undirected Graph | O(E + n) | O(n) | Hard | ⭐⭐⭐ undirected graph 用indegree 来 detect cycle Similar Question |
| 2421. Number of Good Paths | O(E + nlogn) | O(n) | Hard | ⭐⭐⭐ undirected graph union find Similar Question Union find
|
| 2642. Design Graph With Shortest Path Calculator | O(M*(V + ElogV)) | O(n) | Hard | ⭐⭐⭐ Dijkstra's Algorithm, Floyd–Warshall algorithm Similar Question |
| 2685. Count the Number of Complete Components | O(V+E) | O(V+E) | Medium | ⭐⭐⭐ c++ all_of, 如果每个都在cycle中， 每个node的outgoing size = 总共的node - 1 |
| 2858. Minimum Edge Reversals So Every Node Is Reachable | O(n) | O(n) | Hard | ⭐⭐⭐ no cycle Similar Question |
| 2976. Minimum Cost to Convert String I | O(26^3) | O(26^2) | Medium | ⭐⭐⭐Floyd-Warshall |
| 2977. Minimum Cost to Convert String II | O(n^3) | O(n^2) | Hard | ⭐⭐⭐Floyd-Warshall |
| 3108. Minimum Cost Walk in Weighted Graph | O(V*(V+E)) | O(V+E) | Medium | ⭐⭐⭐ undirected graph union find |
| 3123. Find Edges in Shortest Paths | O(V + ElogV) | O(V+E) | Hard | ⭐⭐⭐ undirected graph union find |
undirected graph
//undirected graph
//detect cycle
bool dfs(unordered_map<int, unordered_set<int>>&graph, vector<int>&visited, int cur, int parent){
//cout<<" in "<<cur<<endl;
visited[cur] = 1;
for(auto nxt: graph[cur]){
if(nxt == parent) continue;
if (visited[nxt]) return false;
if (!dfs(graph, visited, nxt, cur)){
return false;
}
}
return true;
}
//detect cycle node
int find_cycle(unordered_map<int,unordered_set<int>>&graph, int cur, int parent, vector<int>&visited, unordered_set<int>&cycle){
if(visited[cur]){
return cur;
}
visited[cur] = 1;
for(auto &nxt: graph[cur]){
if(nxt == parent) continue;
int cycle_node = find_cycle(graph, nxt, cur, visited, cycle);
if(cycle_node >= 0){
cout<<" find cycle node " << cur<<endl;
cycle.insert(cur);
}
if(cycle_node >= 0){
//比如 1-> 2 -> 3 -> 4 -> 1, 当4 ->1 返回1, 当 cur = 1 时候, cycle_node = 1是cycle 的起点
return cur == cycle_node? -1: cycle_node;
}
}
return -1;
}
//BFS find cycle node
void find_cycle(int n, vector<vector<int>>& edges) {
unordered_map<int, unordered_set<int>>graph;
vector<int>degree(n,0);
for(auto & edge: edges){
graph[edge[0]].insert(edge[1]);
graph[edge[1]].insert(edge[0]);
++degree[edge[0]];
++degree[edge[1]];
}
queue<int>q;
for(int i = 0; i<n; ++i){
if(degree[i] == 1) {
q.push(i);
}
}
while(!q.empty()){
int top = q.front(); q.pop();
for(auto nxt: graph[top]){
if(--degree[nxt] == 1){
q.push(nxt);
}
}
}
vector<int>res(n, 2*n);
for(int i = 0; i < n; ++i){
if(degree[i]>1){
cout<<" find cycle node " << i<<endl;
}
}
}
DFS 是看有没有path，DP是看有几个path, 如果不要连续的dp[i][j] = max(dp[i-1][j], dp[i][j-1])
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 146. LRU Cache | O(1) | O(k) | Medium |
|
| 359. Logger Rate Limiter | O(1) | O(n) | Easy | |
| 380. Insert Delete GetRandom O(1) | O(1) | O(1) | Medium | 🎅🎅 |
| 460. LFU Cache | O(1) | O(1) | Hard | ⭐⭐⭐ remove element from list 不会invalidate iterator |
| 1381. Design a Stack With Increment Operation | ctor: O(1) |
|||
| push: O(1) |
||||
| pop: O(1) |
||||
| increment: O(1) | O(n) | Medium | Lazy increment | |
| [1396. Design Underground System](1396 Design Underground System) | ctor: O(1) |
|||
| checkin: O(1) |
||||
| checkout: O(1) |
||||
| getaverage: O(1) | O(n) | Medium | ||
| 2349. Design a Number Container System | ctor: O(1) |
|||
| change: O(logn) |
||||
| find: O(1) |
O(n) | Medium | Python SortedList | |
| 2353. Design a Food Rating System | ctor: O(nlogn) |
|||
| changeRating: O(logn) |
||||
| highestRated: O(1) |
O(n) | Medium | Python SortedList |
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 192 Word Frequency | O(n) | O(k) | Medium | switch column awk, remove whitespace sed |
| 193. Valid Phone Numbers | O(n) | O(1) | Easy | grep |
| 194 Transpose File Shell | O(n^2) | O(n^2) | Medium | paste & cut |
| 195. Tenth Line | O(n) | O(1) | Easy | awk, sed |
- c++ parameter to thread always pass by value. need
std::ref(x)to pass by reference. Thread cannot be copied cannot only be moved - Future .get() 只能被call 一次，call多次会crash、
- c++ wait lambda是release的条件，python 的wait_for也是release的条件
Python
- 第一个
Lock.acquire()不会block thread, 第二个Lock.acquire()会block - 第一个
Event.wait()会block thread, thread process 当Event.set()(Set the internal flag to true), 用完一次后需要Event.clear()(Reset the internal flag to false). 需要先clear 才能再次set Semphore初始值默认1,Semphore.acquire()decrement value, thread block 当 value == 0,Semphore.release()increent value- Python Barrier release 当初始的counter == barrier.wait()的call时候
| Title | Time | Space | Difficulty | Algorithm Note |
|---|---|---|---|---|
| 1114. Print in Order | O(1) | O(1) | Easy | Python的多种写法 |
| 1115. Print FooBar Alternately | O(n) | O(1) | Medium | Python的多种写法 |
| 1116. Print Zero Even Odd | O(n) | O(1) | Medium | |
| 1117. Building H2O | O(n) | O(1) | Medium | ⭐⭐
|
| 1188. Design Bounded Blocking Queue | O(n) | O(n) | Medium | ⭐⭐⭐ 解释python 为什么notify 需要before lock.release |
| 1195. Fizz Buzz Multithreaded | O(n) | O(1) | Medium | ⭐ ✏️ c++ python thread lambda function |
| 1226. The Dining Philosophers | O(n) | O(1) | Medium | ⭐⭐ ✏️ C++ semaphore 写法 |
| 1242. Web Crawler Multithreaded | O(V+E) | O(V) | Medium | ⭐⭐⭐ vector<thread> 在emplace_back 后就开始工作了 |
| 1279. Traffic Light Controlled Intersection | O(n) | O(n) | Easy | ❌ bad question description |
#下面code thread 1 先run, thread 2后run
# Condition, 必须 notifyAll() under with self.cv:
cv = threading.Condition()
isFoo = True
def thread1():
with cv:
cv.wait_for(lambda: isFoo) #when isFoo = True, acquire lock and continue work
"""
do some thing
"""
print("先print")
global isFoo
isFoo = not isFoo
cv.notify()
def thread2():
with cv:
cv.wait_for(lambda: not isFoo) #when isFoo = False, acquire lock and continue work
"""
do some thing
"""
print("后print")
global isFoo
isFoo = not isFoo
cv.notify()
t = threading.Thread(target = thread1).start()
t2 = threading.Thread(target = thread2).start()
# Event
# Event.set()
# Event.clear()
# An event manages a flag that can be set to true with the set() method and
# reset to false with the clear() method.
# The wait() method blocks until the flag is true. The flag is initially false.
e = (threading.Event(), threading.Event())
e[0].set()
def thread1():
e[0].wait() # wait until e[0] flag is true by set, pass because e[0] has been set
"""
do some thing
"""
print("先print")
e[1].set()
e[0].clear() #set e[0] flag false
def thread2():
e[1].wait() # wait until e[1] flag is true by set
"""
do some thing
"""
print("后print")
e[0].set()
e[1].clear() #set e[1] flag false
t = threading.Thread(target = thread1).start()
t2 = threading.Thread(target = thread2).start()
"""
Barrier:
used as to wait for a fixed number of thread before any particular thread can proceed
keep track of wait() call. If wait () call大于 number of thread initialized.
wait(): Wait until notified or a timeout occurs. 当代n 个 thread 到wait 后一起释放 工作， simultaneously released.
比如 n = 5, 现在有3个到了wait， 等待另外两个到wait 才工作
"""
barrier = threading.Barrier(2)
i = 0
def run(id):
print("enter ",id)
barrier.wait()
print("process ",id)
thread1 = threading.Thread(target=run, args=(1,)).start()
time.sleep(5)
thread2 = threading.Thread(target=run, args=(2,)).start()
"""
先打印 enter id = 1, 然后wait
5 秒后，
打印 enter id = 2, release all simultaneously
print : process 2
process 1
"""
"""
Lock, default is release
lock.acquire()
lock.release()
"""
e = (threading.Lock(), threading.Lock())
e[1].acquire()
def thread1():
e[0].acquire()
"""
do some thing
"""
print("先print")
e[1].release()
def thread2():
e[1].acquire()
"""
do some thing
"""
print("后print")
e[0].release
t = threading.Thread(target = thread1).start()
t2 = threading.Thread(target = thread2).start()
# Semaphore
"""
Semaphore(value=1)
acquire()
release(n=1)
A semaphore manages an internal counter which is decremented by each acquire() call
and incremented by each release() call.
The counter can never go below zero;
when acquire() finds that it is zero, it blocks, waiting until some task calls release().
"""
e = (threading.Semaphore(1), threading.Semaphore(1))
e[1].acquire()
def thread1():
e[0].acquire()
"""
do some thing
"""
print("先print")
e[1].release()
def thread2():
e[1].acquire()
"""
do some thing
"""
print("后print")
e[0].release
t = threading.Thread(target = thread1).start()
t2 = threading.Thread(target = thread2).start()
"""
Lock vs Semaphore
1. Locks cannot be shared between more than one thread processes but semaphores
can have multiple processes of the same thread.
2. Only one thread works with the entire buffer at a given instance of time
but semaphores can work on different buffers at a given time.
3. Lock takes care of the locking system however semaphore takes care of the signal system.
4. we consider lock as an object whereas we consider semaphore as an integer with values.
5, The lock has 2 principles that are acquire and release however semaphore has two principles
which are wait() and signal().
6. The lock does not have any subtypes of its own however semaphore has 2 subtypes.
They are binary semaphores and counting semaphores.
7. Locks can have multiple programs at a time but it cannot perform them all at the same time.
Whereas semaphores can have multiple programs and can perform them all at the same time.
"""