This is ongoing project which records my leetcode problem process. It also summarizes the common data structure, algorithm, and gives a template.
function autoLoadTrades() {
setInterval(() => {
window.scrollTo(0, document.body.scrollHeight);
}, 2); // Scroll every .002 seconds
}function gcd(int a,int b){
int r = 0;
while( b != 0){
r = a % b;
a = b;
b = r;
}
return a;
}unordered_map<int, int> m;
for(unordered_map<int, int>::iterator it=m.begin();it!=m.end();it++){
cout<<"("<<it->first<<","<<it->second<<")"<<",";
}| name | description |
|---|---|
| array | fixed size static array |
| vector | resizable dynamic array |
| deque | Dynamic array allows fast insertions and deletions at both ends. |
| list | Doubly Linked List |
| forward-list | Singly Linked List |
| name | description |
|---|---|
| set | Collection of unique elements sorted on values |
| map | Collection of key-value pairs sorted on keys where no two pairs have same keys |
| multiset | Collection of elements sorted on values but allows copies of values |
| multimap | Collection of key-value pairs sorted on keys where multiple pairs can have same keys |
| name | description |
|---|---|
| unordered set | Collection of unique elements hashed by values |
| unordered map | Collection of key-value pairs that are hashed by keys where no two pairs have same keys |
| unordered multiset | Collection of elements hashed by values and allows multiple copies of values |
| unordered multimap | Collection of key-value pairs that are hashed by keys where multiple pairs can have same keys |
| name | worst case | best case | additional space(in place) | stable(relative order) |
|---|---|---|---|---|
| 1. bubble sort | O(n2) | O(n) | O(1) | yes |
| 2. selection sort | O(n2) | O(n2) | O(1) | no |
| 3. insertion sort | O(n2) | O(n) | O(1) | yes |
| 4. merge sort | O(nlogn) | O(nlogn) | O(n) | yes |
| 5. quick sort | O(n2) | O(nlogn) | O(logn) | no |
| 6. heap sort | O(nlogn) | O(nlogn) | O(1) | no |
| 7. shell sort | O(nlogn2) | O(n) | O(1) | no |
| 8. bucket sort | O(n2) | O(n+k) (k:bucket size) | O(n+k) | yes |
| 9. radix sort | O(n*k/d) (d:number of largest digit) | O(n*k/d) | O(n+2d) | yes |
| 10. Tim sort | O(nlogn) | O(nlogn) | n | yes |
int left = 0, right = int(nums.size()) - 1;
while (left <= right) {
// Get the middle index and the middle value.
int mid = left + (right - left) / 2;
// Case 1, return the middle index.
if (nums[mid] == target) {
return mid;
}
// Case 2, discard the smaller half.
else if (nums[mid] < target) {
left = mid + 1;
}
// Case 3, discard the larger half.
else {
right = mid - 1;
}
}
// If we finish the search without finding target, return -1.
return -1;| >> signed right shift(divide the number by power of 2) e.g. (1000)_2>>2=(1110)_2 -2 | << signed left shift(preserve the sign) |
|---|---|
| >>> unsigned right shift | <<< unsigned left shift |
| bitwise and & | bitwise or | |
| bitwise XOR ^ (result is 0 if both bits are the same) | bitwise coomplement ~ |
| 1's complement: invert all bits, add up to 1 e.g. (1000)2=8 (0111)2=-7 | 2's complement: invert all bits and add one, msb is signed e.g. (0110)2=6 (1001)2+1=(1010)2=-1x23+1x2=-6 |
for each vertex u in G.V-{s}:#initialize
u.color = WHITE #not visited
u.d = inf #distance from s to u
u.pred = NIL #predecessor
s.color = GRAY # visiting
s.d = 0
s.pred = NIL
Q = Enqueue(Q,s);
while Q not empty:
u = Dequeue(Q)
for each v in G.Adj[u]:
v.color = Gray
v.d = u.d + 1
v.pred = u
Enqueue(Q,v)
u.color = Black # finish visiting uTime:O(V+E) Space:O(V)
for each vertex u in G.V: #initialize
u.color = White
u.pred = NIL
time = 0
for each vertex u in G.V:
if u.color = White:
DFS-VISIT(G,u)
DFS-VISIT(G,u):
time = time + 1
u.d = time #start time when discovering u
u.color = Gray
for each v in G.Adj[u]:
if v.color == White:
v.pred = u
DFS-VISIT(G,v)
u.color = Black
time = time + 1
u.f = time #time after finish visiting utime:O(V+E) space:O(V)