# Leetcode category
###### tags: `interview`
# General SOP
- 簡單的 20 min 內，難的 30-40 min
- 討論出解法及確認 TC / SC 沒問題再實作
#### Asking Clarifying Questions (2 mins)
- 問問題 (see [here](#Clarifying-questions))，dry run 一次範例
#### Proposing valid solution (8-10 mins)
- 解釋做法，分析複雜度，可以的話提出多種做法並討論 trade-off。
#### Code & Implement (5 mins)
#### Dry run (5 mins)
#### When stuck
- ask for hint
- 解釋可能的解法
- 解釋可能的解法困難點在哪裡
- observation
- 用 interviewer 給的範例人工解題
- 試著發現可以寫成 algorithm 的 pattern
- 如果是那種找出最小/大的 XXX 的問題，然後要做很多 decision (可以畫出 decision tree 的形式):
- 嘗試去感覺有沒有 greedy solution
- 很難做決定的話可能是 backtrack 或 dp
# Reactions to scenario
## input 的數量或是值有限:
- counting sort
- binary search
- segment tree
## 找出答案的決策流程很複雜:
- backtracking
- DP
- 知道 subproblem 的答案的話可以幫助算出原問題嗎?
- backtracking 的 solution 可以 memoize 嗎?
- greedy
- monostack
## input 之間有 connection 的概念:
- union find
- https://leetcode.com/problems/last-day-where-you-can-still-cross/
- https://leetcode.com/problems/bricks-falling-when-hit/
- graph alg
## input 是 sorted 或是可以 sort:
- sort + greedy
- binary search
- two pointers (find sum)
## 需要 partially sorted:
- priority queue with size limited to k
- O(nlogk)/O(k)
- quick select
- O(n) in avg/O(1) iterative
## 最短路徑 / 最少開銷從 A 到 B:
- BFS (equally weighted edge)
- O(V+E)/O(V+E)
- Dijkstra
- O(ElogV) using indexed priority queue
- total update E time, priority queue stays at most size V
- O(ElogE) = O(ElogV) using lazy update
- total update E time, priority queue may have duplicate val, size E
- but since O(logE) = O(2logV) = O(logV), the order is the same.
- O(V+E) space
## tree:
- path w/o cycle
- single root
## constant space (不能用額外 data structure):
- majority voting
- linked list cycle
- bitwise
## get max/min:
- prefix sum/min/max
- priority queue (hard to update, only lazy rm, or use indexed pq)
- binary search tree (easy to update)
- segment tree (range query/update)
## subset:
- backtracking
- 0/1 knapsack
## palindrome:
- 可先用 lookup table 把 `str[i:j]` 是否為 palindrom 記錄在 `memo[i, j]`
- O(n^2) for create table
- O(1) for furthur application
## 有大小、先後關係，要求排列或是否矛盾:
- topological sort
## Dynamic Programming:
- 問自己假設知道 subproblem 的答案，能夠解出現在問題的答案嗎？
- Reverse thinking，從 N -> 0
- 如果為了節省空間，只存前一個 subproblem，而宣告一堆變數來暫存 state 時，想想能不能倒著做(從 n 到 0)，讓 state 在更新前就使用完就不用暫存了
- https://leetcode.com/problems/pascals-triangle-ii/
- prefix DP dp[i] = arr[0...i] 的答案
- range DP dp[i][j] = arr[i...j] 的答案
- https://leetcode.com/problems/strange-printer/
- Floyd-Warshall https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/
- https://leetcode.com/problems/remove-boxes/
- https://leetcode.com/problems/burst-balloons
- https://leetcode.com/problems/minimum-cost-to-merge-stones/
- knapsack
- 給定一些 item 選與不選，item 有 value/cost，題目有 cost 上限，求：
- cost 上限內，最大/小 value or 選擇的 set
- TSP (travling salesman problem)
- https://leetcode.com/problems/find-the-shortest-superstring/
- augmented DP
- 如果原本的 dp table 不能完整敘述 subproblem，需要再加一維 dp[i] --> dp[i][j]，用這一維存下多的資訊
# Clarifying questions
1. size of input, can be empty?
2. what's the range of value, positive? negative? including 0?
3. is there duplicated value? or all unique?
4. is it sorted?
5. is it guarantee to have a valid ans?
6. what to return if no valid ans?
# Common mistake
### 1. 迴圈
迴圈最後要加的東西 沒有加進
```python=
ans = []
acc = 0
for i in range(n):
if arr[i] match condition:
ans.append(acc)
acc = 0
else:
acc += 1
# make sure the last part is added.
if acc > 0:
ans.append(acc)
```
記得迴圈用的區域變數不要跟其他變數衝突
```python=
def func(k):
for k, v in mp.items():
# k is overrided!
```
### 2. Boolean
#### 檢查 AND/OR 不要搞反
#### 小心 short circuit
如果 `dfs(left)==False`，`dfs(right)` 就不會執行：
```python=
return dfs(left) and dfs(right)
```
如果有些邏輯是不管怎樣都要對每個 node 執行，務必寫成這樣：
```python=
l = dfs(left)
r = dfs(right)
return l and r
```
### 3. Complexity
#### permutation: $n!$
#### combination: $2^n$
#### dfs for "path": $2^n$
```python=
def dfs(i):
vis[i] = 1
dfs(next)
vis[i] = 0
```
4. String
invalid number string:
leading zero: `000012`
negative zero: `-0`
---
## Time Complexity
n! --> 2^n --> polynomial
- n! permutation
T(n) = nT(n-1)
- 2^n combination
T(n) = 2T(n-1)
- polynomial combination (reuse subset of combination)
- O(n)
- T(n) = T(n-1) + O(1)
- O(nlogn)
- T(n) = 2T(n/2) + O(n)
- O(logn)
- T(n) = T(n/2) + O(1)
- O(n2)
- T(n) = T(n/2) + O(n2)
---
## Data structures
- priority queue
- stack
- hash map
- hash set
- segment tree
- trie
---
# Category
## Knapsack
### 0/1 knapsack
- find number of valid subset
https://leetcode.com/problems/profitable-schemes/
- find least item used
### unbounded knapsack
- find least item used
https://leetcode.com/problems/coin-change/
- find number of valid subset
https://leetcode.com/problems/coin-change-2/
## Array
#### Quickselect
O(n) / O(1)
得到 k-th 大/小的元素
https://leetcode.com/problems/kth-largest-element-in-an-array/
#### Dutch National Flag
L 指向 0 後的第一個 idx
M 指向第一個 ?
R 指向最後一個 ?
```
0000111????????2222
^ ^ ^
L M R
```
```python
def dutchsort(arr):
def swap(i, j):
arr[i], arr[j] = arr[j], arr[i]
l = m = 0
r = len(arr)-1
while m <= r:
if arr[m] == 0:
swap(m, l)
l += 1
m += 1
elif arr[m] == 1:
m += 1
else:
swap(m, r)
r -= 1
```
#### majority voting
https://leetcode.com/problems/majority-element-ii/
#### linked list cycle
https://leetcode.com/problems/linked-list-cycle-ii/
#### prefix sum :fire:
#### sliding window / 2-3 pointers :fire:
- 快慢 pointer
- 滿足條件的最小 subarray
- 左右 pointer 往中間夾
- sorted 找 target
#### hash map (2Sum) :fire:
在 loop 的過程中將 arr[i] 加進 map，在 map 尋找 target - arr[i] 的 idx/count。
可搭配 prefix，將 prefix 存進 map，便能在 map 尋找某區間的和是否等於 target。
https://leetcode.com/problems/longest-well-performing-interval/
https://leetcode.com/problems/subarray-sum-equals-k/
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
https://leetcode.com/problems/contiguous-array/
https://leetcode.com/problems/binary-subarrays-with-sum/
#### left/right extend arr
用 left[i] 紀錄往左邊看第一個比 arr[i] 還大/小的 idx
用 right[i] 紀錄往右邊看第一個比 arr[i] 還大/小的 idx
便能計算以 arr[i] 為最大/小值的最大 subarray，搭配 prefix sum 能進一步算該 subarray 的和。
e.g.
```python=
left = [-1] * n
for i in range(1, n):
p = i - 1
while p >= 0 and nums[p] >= nums[i]:
p = left[p]
left[i] = p
```
- https://leetcode.com/problems/maximum-of-minimum-values-in-all-subarrays/discuss/1310252/Java-O(n)-using-Stacks
- https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/28902/5ms-O(n)-Java-solution-explained-(beats-96)
#### reverse all + reverse partial 技巧
https://leetcode.com/problems/rotate-array/
https://leetcode.com/problems/reverse-words-in-a-string-iii/
#### square root decomposition
https://leetcode.com/problems/design-most-recently-used-queue/
## Priority Queue :fire:
Use extra field to mark element as "removed".
https://leetcode.com/problems/exam-room/discuss/139941/Python-O(log-n)-time-for-both-seat()-and-leave()-with-heapq-and-dicts-Detailed-explanation
improvement (using bucket):
https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14
-> bucket O(1) popmax / insert
if the value range is limited, use each value as key, store the elements with that value in array or hashset.
## Game / MinMax
https://leetcode.com/problems/cat-and-mouse/submissions/
## Rectangles
[84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)
[221. Maximal Square](https://leetcode.com/problems/maximal-square/)
[85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)
[1727. Largest Submatrix With Rearrangements](https://leetcode.com/problems/largest-submatrix-with-rearrangements/)
## Stack
[1673. Find the Most Competitive Subsequence](https://leetcode.com/problems/find-the-most-competitive-subsequence/)
[1425. Constrained Subsequence Sum](https://leetcode.com/problems/constrained-subsequence-sum/)
[239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)
## Monotonic Queue
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
https://leetcode.com/problems/next-greater-element-i/
https://leetcode.com/problems/largest-rectangle-in-histogram/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
TODO:
[907. Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/)
[901. Online Stock Span]()
[856. Score of Parentheses]()
[503. Next Greater Element II]()
[496. Next Greater Element I]()
## Floyd-Warshall
[1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/)
## Counting sort
[49. Group Anagrams](https://leetcode.com/problems/group-anagrams/)
## Sliding Window
pattern: `subarray` that match some `condition`
template:
```cpp=
int n = input.size();
int l = 0;
int r = 0;
for (int r = 0; r < n; r++) {
while (l <= r && match(input, l, r)) {
// do something.
l++;
}
}
```
- [1248. Count Number of Nice Subarrays](https://leetcode.com/problems/count-number-of-nice-subarrays/)
- [1234. Replace the Substring for Balanced String]()
- [1004. Max Consecutive Ones III]()
- [930. Binary Subarrays With Sum]()
- [992. Subarrays with K Different Integers]()
- [904. Fruit Into Baskets]()
- [862. Shortest Subarray with Sum at Least K]()
- [209. Minimum Size Subarray Sum]()
## `map::lower_bound`, `map::upper_bound`
`map::lower_bound(k)`
gives the iterator that its key that >= k
`map::upper_bound(k)`
gives the iterator that its key > k
## Unicode character
- unicode contains 1 **OR** 2 character.
## Longest Increasing Subsequence
- [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)
- [354. Russian Doll Envelopes](https://leetcode.com/problems/russian-doll-envelopes/)
## Topological
- dfs:
```cpp=
vector<int> sorted;
bool dfs(int n, vector<vector<int>>& g, vector<int>& vis) {
// Check visited.
if (vis[c]==1) return true;
if (vis[c]==2) return false;
vis[n] = 1;
for (int c: g[n])
if (dfs(c, g, vis)) return true;
vis[n] = 2;
sorted.push_back(n);
return false;
}
void main() {
for (int i = 0; i < n; i++)
if (dfs(i, g, vis)) {
cout << "has cycle" << endl;
return;
}
reverse(sorted.begin(), sorted.end());
}
```
- bfs:
```cpp=
vector<int> sorted;
vector<int> degree(n);
vector<vector<int>> g(n);
for (auto e: edges) {
degree[e[1]]++;
g[e[0]].push_back(e[1]);
}
queue<int> q;
for (int i = 0; i < n; i++)
if (degree[i]==0) q.push(i);
int seen = 0;
while (!q.empty()) {
seen++;
int f = q.front();
sorted.push_back(f);
q.pop();
for (int neighbor: g[f]) {
degree[neighbor]--;
if (degree[neighbor]==0) q.push(neighbor);
}
}
if (seen!=n) {
cout << "has cycle!" << endl;
return;
}
```
- [1591. Strange Printer II](https://leetcode.com/problems/strange-printer-ii/)
- [discussion](https://leetcode.com/problems/strange-printer-ii/discuss/854151/C%2B%2B-O(n3)-solution-checking-cycle-in-dependency-graph)
- [329. Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/)
- single source shortest path
- [1857. Largest Color Value in a Directed Graph](https://leetcode.com/problems/largest-color-value-in-a-directed-graph/)
## Trie
root is dmy
check if next node exist
if not exist: return
else: check if "next" node is endNode and add to ans
[421. Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)
[1707. Maximum XOR With an Element From Array](https://leetcode.com/problems/maximum-xor-with-an-element-from-array/)
Trie search with limitation
## Prefix Sum
- [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
- [152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)
- [1590. Make Sum Divisible by P](https://leetcode.com/problems/make-sum-divisible-by-p/)
### Kadane's algorithm
[Bitset](https://www.geeksforgeeks.org/c-bitset-and-its-application/)
## Two pointer
[11. Container With Most Water](https://leetcode.com/problems/container-with-most-water/)
[42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)
算裝水的問題可以用stack或two pointer來做
用stack的缺點是你不知道從左到右的路上
```
_
\_????_...
\xx/
--
01234567
```
遇到小水坑你只能蒐集這個水坑裡的水(x的部分)
但水坑上方的的空間你不確定有沒有水(?的部分)
儘管左邊有更高的山(1)
但你不知道右邊有沒有高山可以困住(?)的水
要直到遇到了才能蒐集(?)
two pointer則很巧妙的用這個問題greedy的性質
從兩側往中間逼近
總是移動矮的那一邊，所以你可以保證另一邊一定有比這邊更高的山
所以每次蒐集雨水時可以直接算出每個位置會淹到哪裡
[713. Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/)
[1574. Shortest Subarray to be Removed to Make Array Sorted](https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/)
## Linked List
Reverse
Slow-Fast pointers
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise.
## Bucket
[220. Contains Duplicate III](https://leetcode.com/problems/contains-duplicate-iii/)
[a solution for 36. Valid Sudoku
](https://leetcode.com/problems/valid-sudoku/discuss/15464/My-short-solution-by-C%2B%2B.-O(n2))
## Permutation
[46. Permutations](https://leetcode.com/problems/permutations/)
#### Pascal Traingle
```cpp
vector<vector<int>> table(n);
for (int i = 0; i < n; i++) {
table[i] = vector<int> (i+1, 1);
for (int j = 1; j < i; j++) {
table[i][j] = table[i-1][j-1] + table[i-1][j]];
}
}
```
table[n-1][m] == Cn取m
[1569. Number of Ways to Reorder Array to Get Same BST](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/)
#### Backtracking
[gfg](https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/)
[1239. Maximum Length of a Concatenated String with Unique Characters](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/)
```cpp
void permute(vector<int>& a, int l, int r) {
if (l==r) {
// one permutation.
return;
}
for (int i = l; i <= r; i++) {
swap(a[l], a[i]);
permute(a, l+1, r);
swap(a[i], a[l]);
}
}
```
```cpp
void btrack(vector<int>& arr, int index = 0) {
for (int i = index + 1; i < arr.size(); i++) {
btrack(arr, i)
}
}
```
## Segment Tree
https://leetcode.com/tag/segment-tree/
- [307. Range Sum Query - Mutable
](https://leetcode.com/problems/range-sum-query-mutable/)
## Fenwick Tree
Need to be 1-based
range query + node 會swap位置
[1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits](https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/)
只加**下一個** parent
```python=
# 假設tree已經有原始資料
def build(arr):
tree = [0] + arr
for i in range(tree[1:]):
j += lsb(i)
if j < len(tree):
tree[j] += tree[i]
return tree
def query(tree, l, r):
def prefix(i):
res = 0
while i:
res += tree[i]
i -= lsb(i)
return res
return prefix(r) - prefix(l-1)
def update(tree, i, val):
while i < len(tree):
tree[i] += val
i += lsb(i)
def lsb(x):
return x & -x
```
### Segment Tree
#### Array based
假設要建segment tree的資料有n筆
如果n是2的power，tree size = 2n-1
如果不是，tree size是2x-1，x是比n大的最小的2的power
所以一定可以涵蓋的array大小會是n<<2 (4n)
```cpp
vector<int> tree(N<<2);
void build_tree(vector<int>& tree, int idx, int l, int r) {
if (l==r) {
tree[idx] = nums[l];
return;
}
int m = l + (r-l)/2;
tree[idx] = merge(
build_tree(tree, idx<<1, l, m),
build_tree(tree, idx<<1|1, m+1, r)
);
}
int query(vector<int>& tree, int idx, int l, int r, int i, int j) {
if (i==l && j==r) {
return tree[idx];
}
int m = l + (r-l)/2;
if (j <= m) {
// case 1. covered by left.
return query(tree, idx<<1, l, m, i, j);
} else if (m < i) {
// case 2. covered by right.
return query(tree, idx<<1|1, m+1 ,r, i, j);
} else {
// case 3. a mix.
int lft = query(tree, idx<<1, l, m, i, m);
int rgh = query(tree, idx<<1|1, m+1, r, m+1, j);
return merge(lft, rgh);
}
}
void update(vector<int>& tree, int idx, int l, int r, int i, int val) {
if (l==r) {
tree[idx] += val;
return;
}
int m = l + (r-l)/2;
if (idx <= m) {
update(tree, idx<<1, l, m);
} else {
update(tree, idx<<1|1, m+1, r);
}
tree[idx] = merge(tree[idx<<1], tree[idx<<1|1]);
}
int sg(vector<int>& nums) {
int n = nums.size();
tree = vector<int>(n<<2);
// 要1-index!
build_tree(tree, nums, 1, 0, n-1);
}
```
### lazy propagation
當要做range update時，可用lazy update
要另外管理一個跟`tree`一樣大的array: `lazy`
- lazy只會紀錄到樹的某一層，在lazy紀錄到之下的都還沒被更新
- 如果query到lazy紀錄的node，就更新那一層，再把lazy傳到下一層
```cpp
void update_lazy(vector<int>& tree, vector<int>& lazy, int idx, int l, int r, int i, int j, int val) {
// if the node is not lazy.
if (lazy[idx]!=0) {
tree[idx] += (r-l+1) * val;
if (l!=r) {
lazy[idx<<1] += lazy[idx];
lazy[idx<<1|1] += lazy[idx];
}
lazy[idx] = 0;
}
if (l>r || l>j || r<i) return;
// fully covered by query range.
if (l>=i && r<=j) {
// suppose the merge is addition.
tree[idx] += (r-l+1) * val;
lazy[idx<<1] += val;
lazy[idx<<1|1] += val;
return;
}
// mix
int m = l + (r-l)/2;
update_lazy(tree, lazy, idx<<1, l, m, i, m, val);
update_lazy(tree, lazy, idx<<1|1, m+1, r, m+1, j, val);
tree[idx] = merge(tree[idx<<1], tree[idx<<1|1]);
}
int query_lazy(vector<int>& tree, vector<int>& lazy, int idx, int l, int r, int i, int j) {
if (l>r || l>j || r<i) return 0;
if (lazy[idx]!=0) {
tree[idx] += (r-l+1) * lazy[idx];
if (l!=r) {
lazy[idx<<1] += lazy[idx];
lazy[idx<<1|1] += lazy[idx];
}
lazy[idx] = 0;
}
if (i==l && j==r) return tree[idx];
int m = l + (r-l)/2;
if (j<=m) {
return query_lazy(tree, lazy, idx<<1, l, m, i, j);
} else if (i > m) {
return query_lazy(tree, lazy, idx<<1|1, m+1, r, i, j);
}
// mix.
int lft = query_lazy(tree, lazy, idx<<1, l, m, i, m);
int rgh = query_lazy(tree, lazy, idx<<1|1, m+1, r, m+1, r);
return tree[idx] = merge(lft, rgh);
}
```
## Bit manipulation
- [1558. Minimum Numbers of Function Calls to Make Target Array](https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/)
- [1595. Minimum Cost to Connect Two Groups of Points](https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/)
### Merge Sort
- [327. Count of Range Sum](https://leetcode.com/problems/count-of-range-sum/)
- inplace_merge(begin, middle, end)
### Quick sort
- [148. Sort List](https://leetcode.com/problems/sort-list/)
### Random
[470. Implement Rand10() Using Rand7()](https://leetcode.com/problems/implement-rand10-using-rand7/)
## String
[316. Remove Duplicate Letters](https://leetcode.com/problems/remove-duplicate-letters/)
Greedy + string
### KMP
[youtube](https://www.youtube.com/watch?v=BXCEFAzhxGY&t=913s)
template:
```cpp
int kmp(string s, string p) {
// build KMP table (longest proper prefix).
int lps[p.size()];
lps[0] = 0;
int i = 0, j = 1;
while (j < p.size()) {
if (p[i] != p[j]) {
if (i!=0) {
i = lps[i-1];
continue;
}
lps[j] = 0;
i = 0;
} else {
lps[j] = i + 1;
i++;
}
j++;
}
// start matching.
int pi = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == p[pi]) {
if (++pi == p.size()) return i - p.size();
} else {
if (pi==0) continue;
pi = lps[pi-1];
i--;
}
}
return -1;
}
```
[28. Implement strStr()](https://leetcode.com/problems/implement-strstr/)
[796. Rotate String](https://leetcode.com/problems/rotate-string/)
#### palindrome
[214. Shortest Palindrome](https://leetcode.com/problems/shortest-palindrome/)
看回文 abc#bca
[5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)
[336. Palindrome Pairs](https://leetcode.com/problems/palindrome-pairs/)
### Rabin Karp
power 的部分可以用%prime來防止overflow
```cpp
for (i = 1 ; i < S.length(); i++)
power[i] = (power[i - 1] * 26) % prime;
```
[1044. Longest Duplicate Substring](https://leetcode.com/problems/longest-duplicate-substring/)
- map放global比較慢，會TLE
- 存string的index就好，不要存string，會爆memory
- 在Rabin Karp減去hash的時候:
`hash = (hash - ((S[i-m] - 'a') * (long long)power[m-1]) % prime) % prime;`
有時因為目前的hash已經超過prime，導致hash回到一個很小的數，讓`hash - ((S[i-m] - 'a') * (long long)power[m-1]) % prime`變成負數，所以要再加一個prime讓他變回正數
`hash = (hash - ((S[i-m] - 'a') * (long long)power[m-1]) % prime + prime) % prime;`
## Union Find
template:
```cpp
class UF {
public:
vector<int> uf;
UF(int n) {
uf = vector<int>(n);
for (int i = 0; i < n; i++)
uf[i] = i;
}
void uni(int x, int y) {
uf[find(y)] = uf[find(x)];
}
int find(int x) {
// path compression
if (uf[uf[x]] != uf[x]) {
uf[x] = find(uf[x]);
}
return uf[x];
}
}
```
- [924. Minimize Malware Spread](https://leetcode.com/problems/minimize-malware-spread/)
- union 完之後還是要再每一個node都find一次才會達到path compression
- [947. Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/submissions/)
- 決定union的方式比較複雜
- [1579. Remove Max Number of Edges to Keep Graph Fully Traversable
](https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/)
- 多個union find
- [1584. Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/)
- mst
## Greedy
#### Interval scheduling
[wiki](https://en.wikipedia.org/wiki/Interval_scheduling#Interval_Scheduling_Maximization)
> - Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.
> - Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.
>
[435. Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals)
...
[56. Merge Intervals](https://leetcode.com/problems/merge-intervals/)
[252. Meeting Rooms]()
[253. Meeting Rooms II]()
[452. Minimum Number of Arrows to Burst Balloons]()
[1605. Find Valid Matrix Given Row and Column Sums](https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/submissions/)
## Dynamic Programming
切割子問題
dp[i] = 範圍從0到i的子問題 且選擇i
- [221. Maximal Square](https://leetcode.com/problems/maximal-square/)
- [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)
- [85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)
- [887. Super Egg Drop](https://leetcode.com/problems/super-egg-drop/)
- [1594. Maximum Non Negative Product in a Matrix](https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/)
- 乘法找最大
- 處理負數的case，不能像加法單純存subproblem的最大值
- [1626. Best Team With No Conflicts](https://leetcode.com/problems/best-team-with-no-conflicts/)
- `dp[i]`存1~i並且選擇i最大的解
- 最佳解不是`dp[n]`而是`max(dp[0...n])`
- [1130. Minimum Cost Tree From Leaf Values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/)
- tree
- divide&conquer
- 兩種運算: 加和乘
- ＊任意相鄰的leaf都能配對在同一個parent下
- 例如[1,2,3,4]，2,3是可以配對在一起的
```
x
| \
x 4
| \
1 x
|\
2 3
```
- 仔細觀察可以發現能用stack做(GREEDY思維)
template:
##### Bottom-up (tabulation)
```cpp
int main() {
for (i)
for (j)
for (k in i+1 to j) {
dp[i][j] = f(dp[i][k], dp[k][y]);
}
return dp[i][j];
}
```
##### Top Down (memoization)
```cpp
int topdown(i, j) {
for (k in i+1 to j) {
// memoization
int dpik, dpkj;
if (dp[i][k] != -1) dpik = dp[i][k];
else dpik = topdown(i, k);
if (dp[k][k] != -1) dpkj = dp[k][j];
else dpkj = topdown(k, j);
dp[i][j] = f(dpik, dpkk);
}
return dp[i][j];
}
int main() {
return topdown(0, size-1);
}
```
[1](https://leetcode.com/problems/minimum-cost-to-cut-a-stick/discuss/780880/C%2B%2B-Top-Down-DP)
[638. Shopping Offers](https://leetcode.com/problems/shopping-offers/)
[1553. Minimum Number of Days to Eat N Oranges](https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges)
[1575. Count All Possible Routes](https://leetcode.com/problems/count-all-possible-routes/)
Top down
Bottom up
- hashmap
- Large scale --> use hashmap rather than array to skip unnecessary computing
- bucket
```cpp
int d2, d3;
if (mp.find(n/2) != mp.end()) {
d2 = mp[n/2];
} else {
d2 = minDays(n/2);
}
if (mp.find(n/3) != mp.end()) {
d3 = mp[n/3];
} else {
d3 = minDays(n/3);
}
mp[n] = 1 + min(n%2 + d2, n%3 + d3);
```
[983. Minimum Cost For Tickets](https://leetcode.com/problems/minimum-cost-for-tickets/)
##### N variable
如果遞迴關係只固定用到前N個，例如
```cpp
dp[i] = someFunc(dp[i-1], dp[i-2], ..., dp[i-N]);
```
可以不用存整個input size的memo
只需要存N個，退化成像是prefix sum的結構。
## Binary Search
template:
```cpp
// Initially
L R
v v
[ valid ] [ invalid ]
// Finally
R L
v v
[ valid ] [ invalid ]
bool valid(int m) {
}
// find the largest valid
int binarySearch(int l, int r) {
while (l <= r) {
int mid = l + (r-l)/2;
if (valid(mid)) l = mid + 1;
else r = mid - 1;
}
return r;
}
```
[1552. Magnetic Force Between Two Balls](https://leetcode.com/problems/magnetic-force-between-two-balls/)
[1482. Minimum Number of Days to Make m Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)
[1300. Sum of Mutated Array Closest to Target](https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/) valid() 難寫
...
[410. Split Array Largest Sum (Hard)]()
[1044. Longest Duplicate Substring (Hard)]()
[668. Kth Smallest Number in Multiplication Table (Hard)]()
[719. Find K-th Smallest Pair Distance (Hard)]()
[33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)
## MISC
[gcd](https://leetcode.com/problems/check-if-it-is-a-good-array/)
```cpp=
int gcd(int a, int b) {
while (b > 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
```
多個gcd:
```cpp=
arr=[12,45,26,90,68...]
g=arr[0]
for a in arr:
g = gcd(g, a)
return g
```
lcm:
```cpp=
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int lcm(vector<int> a) {
int l = a[0];
for (int i = 1; i < a.size(); i++)
l = lcm(l, a[i]);
return l;
}
```
- [858. Mirror Reflection](https://leetcode.com/problems/mirror-reflection/)
- [1589. Maximum Sum Obtained of Any Permutation](https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/)
range: 1-n, m個區間
- [1094. Car Pooling](https://leetcode.com/problems/car-pooling/)
求每個位置被多少個區間包住 O(n)：
```cpp
for (int[] r: interval) {
count[r[0]] += 1;
if (r[1] + 1 < n)
count[r[1] + 1] -= 1;
}
for (int i = 1; i < n; ++i)
count[i] += count[i - 1];
```
Sign in with Wallet
Connect another wallet