# Leetcode
[TOC]
## 16. 3Sum Closest
- 在list中找 3 個數使得總合越接近 $target$
- **Attempt 1:**
- 暴力法：三層 $for$ 迴圈
- $for\ i\in (1,n)$
$for\ j\in (i+1,n)$
$for\ k\in (j+1,n)$
- $O(n^3)$
- **Attempt 2:**
- 先 $sort$
- $k$ 用 $\text{binary search}$
- $for\ i\in (1,n)$
$for\ j\in (i+1,n)$
$\text{binary search}$ 後面陣列
- $\text{binary search}$ 要找最接近的
若 $num[mid] \neq target$
先 search 後比較 $num[mid]$ 和 $num[searched]$ 哪個跟 $target$ 差較小
- $O(n^2logn)$
- **Solution 1:**
- $j$ 也用 $\text{binary search}$
- 找到 $k$ 後
- 下個 $j$ 也用 $\text{binary search}$
- $O(nlog^2n)$
> Runtime: 60 ms, faster than **98.70%** of Python online submissions for 3Sum Closest.
Memory Usage: 11.9 MB, less than **12.90%** of Python online submissions for 3Sum Closest.
- **Solution 2:**
- 若目前 $sum$ 小於 $target$，$j$ 才往右找
目前 $sum$ 大於 $target$，$k$ 才往左找
## 22. Generate Parentheses
- $Catalan\ Number$
1. Stack permutation
2. valid binary search tree
3. valid parentheses
- Binary Search Tree
$T(n) = T(i) + T(1) + T(n-i-1),i \in [0,n]$
第n顆數= 左子樹 + root + 右子樹
- Parentheses
$T(n) = (T(i))T(n-i-1), i \in [0,n]$
第n個排列 = $($ 左子樹 $)$ 右子樹
- **Time complexity:** $O(\frac{4^n}{\sqrt{n}})$
## 32. Longest Valid Parentheses
- 找出最長的合法的括號子字串(substring)
- **Solution 1:**
- 若 $stack$ 為空但要$pop$，紀錄不合法位置
- 若有元素沒有被 $pop$ 掉，也是不合法位置
> Runtime: 36 ms, faster than **76.30%** of Python online submissions for Longest Valid Parentheses.
Memory Usage: 12.8 MB, less than **14.29%** of Python online submissions for Longest Valid Parentheses.
## 42. Trapping Rain Water
- 給一List，判斷可以儲存多少單位的水(凹陷下去的面積)
- **Attempt 1:**
- 若 $num[i-1],num[i+1]< num[i]$ (突起處)
- 則計算前一個突起處到這裡的總和
- 突起處更新
> **WA** 若左右兩邊有更高的突起處，此突起處會被淹沒
- **Solution 1:**
- $maxFront[i] = max(nums[0:i])$
- $maxEnd[i] = max(nums[i:n])$
- 得知目前最左邊的最大值和最右邊的最大值
取兩個中較小的為可能的積水高度
- $flow = min(maxFront[i], maxEnd[i])-nums[i]$
> Runtime: 40 ms, faster than **54.80%** of Python online submissions for Trapping Rain Water.
Memory Usage: 12.6 MB, less than **8.22%** of Python online submissions for Trapping Rain Water.
## 55. Jump Game
- 是否可以從起點跳到終點，$list[i]$ 儲存此格可跳的最大步數
- **Solution 1:**
- 計算 $target = max(target, i+list[i])$
- $target$ 為目前要去的最遠的目的點
- 如果最後 $target>=len(list)$ 則為 True
> Runtime: 72 ms, faster than **76.72%** of Python online submissions for Jump Game.
Memory Usage: 13.2 MB, less than **77.14%** of Python online submissions for Jump Game.
## 75. Sort Colors
in-place: 不需要data structure儲存
- 2-pass sorting: 用一個for迴圈紀錄0,1,2出現幾次，再用一個for迴圈輸出對應的0,1,2
- 1-pass sorting: 紀錄第一個1的位置及第一個2的位置，若$nums[i]==1$則跟第一個2的位置交換；若$nums[i]==0$則跟第一個1的位置交換，再把1和第一個2的位置交換
(注意第一個1及第一個2是否有出現)
## 84. Largest Rectangle in Histogram
- 找出最大面積
- **First Attemp**
- 紀錄陣列 $i$ 到 $j$ 之間的最小值
- 用 $n\times n$ 矩陣儲存
- 計算 $n\times n$ 的面積最大值
- 重複性高、占空間
| | 2 | 1 | 5 | 6 | 2 | 3 |
| --- | --- | --- | --- | --- | --- | --- |
| 2 | 2 | 1 | 1 | 1 | 1 | 1 |
| 1 | | 1 | 1 | 1 | 1 | 1 |
| 5 | | | 5 | 5 | 2 | 2 |
| 6 | | | | 6 | 2 | 2 |
| 2 | | | | | 2 | 2 |
| 3 | | | | | | 3 |
> Memory Limit Exceeded
- **Second Attemp**
- 用 `min` 直接找 $i$ 到 $j$ 之間的最小值
- 不用矩陣空間儲存
- 仍是 $O(n^2)$ 執行時間
> Time Limit Exceeded
> `[0,1,2,3,.....]`
- **Third Attemp**
- $Divide\ and\ conquer$
- 找出目前陣列中最小的值的index ($minIndex$)
- $maxArea(startIndex,endIndex)=\begin{cases} len(\text{heights})\times min(\text{heights}) \\ maxArea(startIndex, minIndex-1) \\ maxArea(minIndex+1, endIndex) \end{cases}$
- worse case: 全部陣列數都一樣 $O(n^2)$
> Time Limit Exceeded
> `[1,1,1,1,1,1,....,1]`
- **Solution 1**
- [ref](https://www.cnblogs.com/grandyang/p/4322653.html)
- 只處理 $heights[i+1] < heights[i]$ 的情形
- 若 $heights[i+1] < heights[i]$
令 $j$ 為從 $i$ 開始往回推到 $0$
如果 $heights[j] < heights[i]$
則算出此面積值
- $Time\ complexity:$
- $heights[i+1] > heights[i]$: $m$ 次
$heights[i+1] < heights[i]$: $n$ 次
$heights[i+1] == heights[i]$: $o$ 次
- $O(n+m)$
- $O(n)$
- **Solution 2**
- [ref](https://leetcode.com/problems/largest-rectangle-in-histogram/discuss/510500/python-using-stack)
- 與 **solution 1** 類似
只處理 $heights[i+1] < heights[i]$ 的情形
- 用 $stack$ 存遞增數列
- 若stack頂端的數`stack[-1]` 大於 $heights[i]$
則 pop stack 頂端的index (index: $k$)
計算現在 stack 頂端的 index 跟 $k$ 之間的面積
- 優點：不用往回搜尋 $heights[j] < heights[i]$
直接從 stack 中 pop 取得
## 94. Binary Tree Inorder Traversal
- recursive解: 左子樹+root.val+右子樹
- iterative解: 一直往左子樹走(while迴圈)(儲存root位址)，輸出root.val，往右子樹走一次
$Algorithm:Morris\ Traversal$
```python=
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
res.append(root.val)
root = root.right
```
- **Attempt:**
- while
- ~~node為stack最上面元素~~
- 遞迴走左子樹
- pop出stack元素
- 走右子樹
- **會造成每次pop後再往左子樹走**
- **解法:**
- 同時用 `cur` 跟 `stack`
## 97. Interleaving String
- $s3$ 是否可以由 $s1,s2$ 的子序列組合成
- **Attempt 1:**
- recursive:
- 若遇到相同字母則嘗試選擇 $s1$ 或 $s2$
> **TLE**
- **Attempt 2:**
- 看 $s1,s2$ 是否為 $s3$ 的子序列
> **WA**
> `s1="ab"`
> `s2="ab"`
> `s3="abac"`
> 兩者都是 `s3` 子序列可是不能組成 `s3`
- **Attempt 3:**
- 用 $\text{dictionary}$
- 如果此字母的 count 小於零則 False
> **WA**
> 無法保證`s1`中順序
> `s1="aabd"`
> `s2="abdc"`
> `s3="aabdbadc"`
- **Solution 1:**
- $DP$
- `s1` 為 $x$ 軸，`s2` 為 $y$ 軸
- 從 $[0,0]$ 到 $[m,n]$ 的任何路徑即為 `s1`, `s2` 的 interleaving
- `s3="aadbbcbcac"`
-
| | 0 | d | b | b | c | a |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | | | | | |
| a | 1 | | | | | |
| a | 1 | 1 | 1 | 1 | 1 | |
| b | | | | | 1 | |
| c | | | | | 1 | 1 |
| c | | | | | | 1 |
- return $dp[m][n]$
> Runtime: 32 ms, faster than **39.78%** of Python online submissions for Interleaving String.
Memory Usage: 11.9 MB, less than **12.50%** of Python online submissions for Interleaving String.
## 120. Triangle
-
```python
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
```
- 找到 top 到 bottom 的最短路徑
- **Attemp 1:**
- 遞迴解法
- 比較左下三角形和右下三角形的最短路徑
加上頂端的值
回傳
> **TLE**
- **Solution 1:**
- $DP$
- 用 $minSum$ 陣列
```python
[
[0],
[0,0],
[0,0,0],
[0,0,0,0]
]
```
存取目前路徑最小值
$minSum[i,j]=triangle[i,j]+min(minSum[i+1,j],minSum[i+1,j+1])$
- 記憶體用量大
- **Solution 2:**
- 直接複寫input $triangle$ 矩陣
- 記憶體用量差不多
- **Solution 3:**
- 用一維陣列 $minSum=triangle[-1]$ 存取目前最小值
- $minSum[j]=triangle[i,j]+min(minSum[j],minSum[j+1])$
- 記憶體用量較少
- $j$ 須從小到大更新，不然新的會覆寫原本的資料
> Runtime: 36 ms, faster than **98.92%** of Python online submissions for Triangle.
> Memory Usage: 12.3 MB, less than **50.00%** of Python online submissions for Triangle.
## 124. Binary Tree Maximum Path Sum
- 找總和最大的連續子路徑，不得為空，可以跨左右子樹
- **Solution 1:**
- `max(None, -3) = -3`
- 若沒有 node 可以 return `None`
- 用 `self.res` 儲存現在最大的路徑總和
- $search(node)$ 函數：回傳含有 $node$ 的最大路徑總和
- 函數內比較 $max(node.val+left, node.val+right, node.val+left+right)$
- 如果比 `self.res` 大則更新
- return $max(node.val+left, node.val+right)$
> Runtime: 76 ms, faster than **90.66%** of Python online submissions for Binary Tree Maximum Path Sum.
Memory Usage: 25.9 MB, less than **32.50** of Python online submissions for Binary Tree Maximum Path Sum.
## 141. Linked List Cycle
- 找 linked list 有沒有 cycle
- **Solution 1:**
- 用 $dictionary$ 存 node 跟對應的 index
- `nodeDict[node] = index`
- 檢查若 `node` 在 `nodeDict` 中，回傳 `True` (有cycle)
- 直到`node.next == null`
> 挑戰用 $O(1)$ 的記憶體
- **Solution 2:**
- 用兩個 $pointer$
- 一個一次走兩個一個一次走一格
- 若兩個走到一樣的 node，則 `True`
## 144. Binary Tree Preorder Traversal
- 類似**94**
- 往左找時，每次append(root.val)
```python=
while stack or root:
while root:
res.append(root.val)
stack.append(root)
root = root.left
root = stack.pop()
root = root.right
```
## 145. Binary Tree Postorder Traversal
- 類似 **94**及**145**
- $Algorithm:Morris\ Traversal$ 每次都先走左子樹，此題stack中存右子樹的root，但是走右子樹。每走到一個點時存入值到 $res$ ，但 $res$ 最後要反向輸出
(因為此時存入數字是中右左)
## 200. Number of Islands
- 找出二維矩陣中有幾個Islands (相鄰的 $1$ 為一個島)
- **Attempt 1:**
- 用兩個 $queue$
- 一個紀錄矩陣中 $1$ 的點
一個紀錄 $0$ 的點
- 如果 $queue_1$ 不為空則 $pop$
否則 $pop\ queue_0$
- 若 $queue_1$ 為空則紀錄島的數量加一
> 例外:
> 0 1 0
> 1 0 1
> 0 1 0
> 跑過點 $(0,0)$ 時同時紀錄 $(0,1), (1,0)$
> 雖然 $(0,1)$ 被 $pop$ 了且為一個 island
> 但 $queue_1$ 仍不為空 (還有 $(1,0)$)
- **Attempt 2:**
- 用三個 $queue(queue_1, queue_0, queue)$
- 當 $pop\ queue_1$ 時 $BFS$ 用 $queue$ 搜尋地圖
- 搜尋到 $queue$ 中沒有值為止
- 輸出 $count$ 加一 (表示此區域搜尋完畢)
且搜尋過的區域標示為 $visited$
> 例外：
> 0 1
> 1 1
> 若有點在 $queue_1$ 中 (已被標為 $visited$ )
> 在 $queue$ 的搜尋時就無法找到此點
> 此例中在 $(0,0)$ 點時，同時加入 $(1,0),(0,1)$ 點
> 在 $(0,1)$ 點搜尋時無法找到 $(1,0)$ 點
- **Solution 1:**
- 對 <font color=red>$queue_0$</font> $pop$ 時做修改
- **Attempt 2** 時如果上下左右有點則都加入 $queue$
- **Solution 1** 修改為，一次只加入一個點
(原先全部 $if$ 改為 $elif$)
> Runtime: **70.69%**
> Memory: **18.92%**
- **Solution 2:**
- 用兩層 $for$ 迴圈
- 如果遇到 $1$ 則 $DFS$，找過的點標記為 $visited$
> Runtime 較佳
## 201. Bitwise AND of Numbers Range
- 從 $m$ 到 $n$ 每個數字的每個 bit 做 $AND$
- 5=101
6=110
7=100
return 100 = 4
- **Solution 1:**
- 如果有零則全部為零
- 若 $m=n$ 則 return $m$
- 若第 $k$ bit要為 $1$，則 $2^{k-1}\leq m,n\leq 2^k-1$
- 檢查 $m,n$ 是否在範圍內
- 如果是則減掉 $2^{k-1}$ 再繼續檢查
> Runtime: 48 ms, faster than **58.02%** of Python online submissions for Bitwise AND of Numbers Range.
Memory Usage: 11.8 MB, less than **50.00%** of Python online submissions for Bitwise AND of Numbers Range.
## 211. Add and Search Word - Data structure design
- 找單字在不在字典裡，若字為`.` 則可用任何字替代
- **Attempt 1:**
- 用`a-z`替換`.`，再搜尋是否在$\text{dictionary}$ 中
- 遞迴
- input 為 `(pre, post)`
- 找 `pre+post` 是否在字典中
- $pre'=pre+post[:i]+alpha(a-z)$
$post'=post[i+1:]$
> **TLE**
> 每個字都替換的時間複雜度是 $O(26^m)$，$m$ 是 `.` 個數
- **Attempt 2:**
- 建立字典時用`.` 替換所有字母
- 類似前面遞迴法
- input 為 `(pre, post)`
- $pre'_1=pre+"."$
$post'_1=post[1:]$
$pre'_2=pre+post[0]$
$post'_2=post[1:]$
> **MLE**
> 字母長度 $m$ 就有 $2^m$ 個單字
(每個字母替換成`.`與否)
- **Solution 1:**
- 用 $len(\text{word})$ 當作字典 $\text{key}$
- 從長度一樣的字找匹配的單字
- 若有字母不同且 $\text{word}$ 不為`.`則檢查下個長度相同的字
> Runtime: 144 ms, faster than **95.63%** of Python online submissions for Add and Search Word - Data structure design.
Memory Usage: 22.3 MB, less than **92.86%** of Python online submissions for Add and Search Word - Data structure design.
## 279. Perfect Squares
- 找到整數 $n$ 最少可以用多少平方數相加而成
- **Attempt 1:**
- $DP$
- $dp[n] = \sum_{k=0}^{\frac{n-1}{2}} dp[k]+dp[n-1-k]$
> **TLE**
> $O(n^2)$
- **Solution 1:**
- $DP$
- $dp[n]=min(dp[n], dp[n-k^2]+1)$
$k$ 是比 $n$ 小的平方數的根
- **Solution 2:**
- $Lagrange's\ four-square\ theorem$
- 任何數都可由四個數的平方和組成
- $n=a^2+b^2+c^2+d^2$
- **Solution 3:**
- $BFS$
- 起始 $queue=[(n,1)]$
(目前要平方的數字,目前的平方數)
- 每次 $(num, k)=queue.pop(0)$
- 若 $num$ 為平方數，則 return $k$
- 測試為平方數
- `if (num ** 0.5) == int(num ** 0.5)`
- 否則 $for\ i\in[1,\sqrt{num}]$
$queue$ 加入 $(num-i^2,k+1)$
## 300. Longest Increasing Subsequence
- 用1維list儲存每個元素目前為止最長的subsequence長度
- 若第i個元素$nums[i] > nums[j]$，則記錄下來，且紀錄為 $list[j]+1$，檢查所有 $j<i$ 的元素中 $list[j]+1$ 的最大值
- return $list$ 中的最大值
- $O(n^2)$
- $Robinson-Schensted-Knuth\ Algorithm$
- 用一個遞增$S$儲存
- 如果$S$中有元素比目前的$nums[i]$還大，則更新index最小的$k$，其中$S[k]> nums[i]$
1. 初始化: $s=[nums[0]]$
2. $for\ i \in [1,n]$
$k = binarySearch(s)\ \ //\ k\ is\ the\ smallest\ index\ such\ that\ s[k] > nums[i]$
$if\ k\ doesn't\ exist:$
$\ \ \ \ length=length+ 1$
$\ \ \ \ s.push(nums[i])$
$else:$
$\ \ \ \ s[k]=nums[i]$
$return\ length$
- $O(nlogn)$
- example: [0, 8, 4, 12, 2]
- i = 1: [0,8]
- i = 2: [0,<font color=red>4</font>]
- i = 3: [0,4,<font color=red>12</font>]
- i = 4: [0,<font color=red>2</font>,12]
## 304. Range Sum Query 2D - Immutable
- 求矩陣 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的和
- **Solution 1:**
- 用矩陣紀錄 $x_1,...,x_n$ 累積的和
- 如果要求 $x_i$ 到 $x_j$ 的和，則計算 $m[j]-m[i]$
- 二維： $m[i,j]=m[i-1,j]+m[i,j-1]-m[i-1,j-1]$
- 集合相加減掉交集
> $O(nm)$
> Time: 79.77%
> Memory: 14.29%
## 337. House Robber III
- 找出不相鄰的node和最大
- **Solution 1:**
- 遞迴
- $f$ return [不含node最大值, 含node最大值]
- 不含node最大值：左子樹最大+右子樹最大
- 含node最大值：`node.val`+左子樹不含`node.left`最大+右子樹不含`node.right`最大
- $max(f(root))$
> Runtime: 32 ms, faster than **94.93%** of Python online submissions for House Robber III.
Memory Usage: 16 MB, less than **42.86%** of Python online submissions for House Robber III.
## 382. Linked List Random Node
- [Reservoir sampling](https://zh.wikipedia.org/wiki/%E6%B0%B4%E5%A1%98%E6%8A%BD%E6%A8%A3)
- $\frac{1}{i}\frac{i}{i+1}\frac{i+1}{i+2}...\frac{n-1}{n} = \frac{1}{n}$
random
```python=
# random: return random number in [0,1]
random.random()
```
## 395. Longest Substring with At Least K Repeating Characters
- 子字串中每個字母都出現至少 $k$ 次
- **Attemp 1:**
- $i\in [1,n]$
- $j\in[i,1]$
- 檢查第 $[j:i]$ 個子字串
- $O(n^2)$
> TLE
>
- **Solution 1:**
- 若某個字出現 $k$ 次才檢查 $j\in[i,1]$
> runtime: **5.31%**
- **Solution 2:**
- 若某個字出現次數小於 $k$
- 則用此字母 $split$
- 遞迴直到不能 $split$
## 416. Partition Equal Subset Sum
- $target = \frac{sum(nums)}{2}$
- 令 $S[1,target]$ 為 $nums[1:i]$ 所有可能組合出的$sum$
若$S_j$ 為 $True$ 則表示可以組合出， $False$ 表不能，$\forall j \in[1:target]$
- $for\ i\ \in\ [1,len(nums)]$
$\ \ for\ element \in\ S$
$\ \ \ \ S_{element+nums[i]} = True$
- Example:
| i | nums | S |
| -------- | -------- | -------- |
| 1 | 1 | {0,<font color=red>1(0+1)</font>} |
| 2 | 5 | {0,1,<font color=red>5(0+5)</font>, <font color=red>6(1+5)</font>} |
| 3 | 11 | {0,1,5,6,<font color=red>**11**~~, 12, 16, 17~~</font>} |
| 4 | 5 | {0,1,5,6,**11**~~,12,16,17,~~<font color=red>~~10,21,22~~</font>} |
> ~~deleted numbers~~: more than $target$
- **Time Complexity:**$O(n\times target)$
## 450. Delete Node in a BST
- 搜尋BST是否有 $key$
- 若有則刪除
- **Solution 1:**
```graphviz
graph graphname {
3 -- 1;
3 -- 5;
1 -- null1;
1 -- 2;
5 -- 4;
5 -- null2;
}
```
- 若 $key$ 為 3 (`node = 3`)
- 則讓右子樹變成 `newRoot`
- `newRoot.left = node.left` ($3$ 的左子樹直接當 $5$ 的左子樹)
- $4$ 為孤兒
- <font color=red>孤兒必比 $3$ 的左子樹都大且比 $5$ 小</font>
- 孤兒接在 $3$ 的左子樹最右邊
> 因為是 BST 所以只要 $O(\text{log }n)$ 的搜尋時間 (找比 $key$ 大或小的子樹)
> 取代左子樹也是最多為 tree 的高度的搜尋時間
> 時間 (80.23%)
> 用遞迴：記憶體空間耗費大 (6.67%)
- **Solution 2:**
- 找到右子樹的最小值替換成刪掉的節點
## 454. 4Sum II
naive: $O(n^4)$
D as dict: $O(n^3)$
AB as dict: $O(n^2)$
- binary search不只要找到，要計算次數，所以用dict較佳
binarySearch:
```python=
s = [1,2,3,4,5,6]
current = 2
l = 0
r = len(s) - 1
found = False
while l <= r and not found:
mid = (l+r) // 2
if s[mid] == current:
found = True
elif s[mid] < current:
l = mid + 1
else:
r = mid - 1
print(found)
```
## 486. Predict the Winner
- 2 個 player，每 round 每個 player 可以從陣列頭或尾選擇數
- 選到數的總額最多的勝
- naive: $O(2^n)$ ($n$ 為陣列長度)
DP: $O(n^2)$
- DP做法
1. 建立 $n\times n$ 矩陣
其中 $[i][j]$ 為計算陣列 $i$ 到 $j$ 的兩個 player 的 payoff
2. $\text{first player payoff [i][j]=}\begin{cases} \text{nums}[i] + \text{second player payoff [i+1][j]}\\
\text{nums}[j] + \text{second player payoff [i][j-1]}
\end{cases}$
3. 決定 $\text{first player}$ 的策略後
算出 $\text{second player}$ 的 $\text{payoff}$
$\text{second player payoff [i][j]=}\begin{cases} \text{first player payoff [i+1][j]}\\
\text{first player payoff [i][j-1]}
\end{cases}$
> $i,j$ 是矩陣 index
- 因為 iterater 是 $(0,1), (1,2),(2,3),...,(0,3)$計算
將 $i,j$ 轉為
$i =start \\
j = start+offset$
iterate $start, offset$
## 520. Detect Capital
- 偵測合法大小寫
- **Solution 1:**
- $if$ 判斷
- **Solution 2:**
- 列出合法大小寫
- 全大寫
- 全小寫
- 首大寫
- 看 `word` 是否在其中
## 664. Strange Printer
- 一次只能印一個字母 (起始和結束位置可變)，最少需要印幾次
- **Attempt 1:**
- 印出橫跨最大範圍的字母
- 例外：`babcabac`
- 印出 `b`:
- `bbbbbb..`
- `baaaab..`
- `babbab..`
- `babcab..`
- `babcaba.`
- `babcabac`
- 正解：
- `bbb.....`
- `bab.....`
- `babccccc`
- `babcaaac`
- `babcabac`
- **Attempt 2:**
- $DP$
- $matrix(i,j)$ 為 $s$ 從 $i$ 到 $j$ 的最小列印次數
- 如果 $s(i) == s(j)$ 則
$matrix(i,j)=matrix(i,j-1)$
eg. `aba`
- 如果 $s(i) != s(j)$
$min_k(matrix(i,k)+matrix(k+1,j))$
> **WA**
> `"dddccbdbababaddcbcaabdbdddcccddbbaabddb"`
- **Solution 1:**
- $DP$
- 如果 $s(i) == s(j)$
$matrix(i,j)=min_k(matrix(i,k-1)+matrix(k+1,j))$
> Runtime: 376 ms, faster than **87.50%** of Python online submissions for Strange Printer.
Memory Usage: 16 MB, less than **12.50%** of Python online submissions for Strange Printer.
> $O(n^3)$
## 670. Maximum Swap
- $num[i]$ 只跟 $num[i+1:len(num)-1]$ 中最大的數交換
確保較大的數在越高位
1. 計算 $maxIndex[i]$ 定義為在 $i$ 到 $len(num)-1$ 中最大值的index，從 $len(num)-1$ 到 $0$，時間複雜度為 $O(n)$
(若最大值有多個，選最後出現那個)
3. 從 $i=0$ 開始，與其 $maxIndex[i]$ 交換，比較何者較大。 時間複雜度為 $O(n)$
## 698. Partition to K Equal Sum Subsets
- 每個subset的總和是 `sum(nums)/k`
-
## 729. My Calendar I
- 給定多個 $[start, end]$，判斷此區間是否已被佔用
- **Solution 1:**
- 用list儲存所有 $start, end$
- 如果有重複的就刪掉
- 初始：$[0,10^9]$
- 判斷：$[0,d_1, d_2, ...,d_{n-1}, d_n,10^9]$
- 判斷兩條線是否重合：一條end是否比另一條start小
- 重複比較是否重合
- $(d_1,d_n)$
- $(d_2,d_{n-1})$
- 但會輪流是合法/非法範圍
- 更新：
- 如果有一樣的數字則更新為新的範圍
- 否則新增到list中
- $set$ 概念
> Runtime: 1628 ms, faster than **7.22%** of Python online submissions for My Calendar I.
Memory Usage: 12.2 MB, less than **100.00%** of Python online submissions for My Calendar I.
- **Solution 2:**
- $\text{binary search}$
## 752. Open the Lock
- 四位數密碼一次只能上下調整一位數
- 給定不能調到的密碼 $deadends$
(若遇到則不能繼續調整)
- 最少要多少步才能調到 $target$
- **Solution 1:**
- 用 $BFS$
- 兩個 $queue$
- 一個儲存密碼
- 一個儲存用了幾步
- 每次調整一位數的可能存進 $queue$
- 且額外用一個 $\text{dictionary}$ 儲存已經調整過的可能的密碼
- 每次 $pop\ queue$
- 若遇到 $deadends$ 則 $continue$
> Runtime: **50%**
> 不用 $DFS$ 的原因: 數字越小越好，但 $DFS$ 會讓調整步數越來越大
## 804. Unique Morse Code Words
1. 用 **dictionary** 檢查 code pattern 是否出現過
2. 將 list 轉為 **set**
## 826. Most Profit Assigning Work
- 用zip將difficulty及profit綁在一起，根據difficulty排序(sorted)
- 將worker也排序，從最小能力值的worker開始找
- 紀錄目前difficulty中最大的profit值，即是該worker的profit
sorted: 根據a排序pairs`[a,b]`
```python=
jobs = sorted([a, b] for a, b in zip(difficulty, profit))
```
## 828. Count Unique Characters of All Substrings of a Given String
- 每個子字串其中字母只出現一次的和
- $\text{ABA}=1, \text{only B}$
- $\text{ABBB}=1, \text{only A}$
- **Attempt 1:**
- $\text{DP and dictionary}$
- 算出 $s[i:j]$ 中的 $\text{dictionary}$
- 若某個字母出現兩次以上，則減掉此字母的長度
> **MLE**
- **Attempt 2:**
- $\text{DP}$ 的矩陣不用 $n\times n$，改用 $n$ 即可
- 因為每多一個字母只取 $matrix[i,j-1]$ 的資料
> **TLE**
- **Attempt 3:**
- 每檢查到一個字母，減掉因為此字母而產生兩個以上的字母的長度
- eg.
- `index[B]=[0,2,3]`
| 0 | 1 | 2 | 3 |minus|
| --- | --- | --- | --- | --- |
| | | | B |0|
| | | B | B |2|
| | A | B | B |2|
| B | A | B | B |3|
- 長度要乘上兩個 `index` 之間的差
> **TLE**
- **Solution 1:**
- | 0 | 1 | 2 | minus|
| --- | --- | --- | --- |
| | | | 0|
| | | B | 0|
| | A | B | 0|
| B | A | B | 2|
- 比較此矩陣與上個矩陣
- 減掉的數可以累加
- 檢查字母長度是否大於 $2$
- 且每次只要檢查 $s[i]$，不用每個字母都檢查
> Runtime: 184 ms, faster than **6.67%** of Python online submissions for Count Unique Characters of All Substrings of a Given String.
Memory Usage: 12.1 MB, less than **100.00%** of Python online submissions for Count Unique Characters of All Substrings of a Given String.
## 919. Complete Binary Tree Inserter
- insert 數字到 complete binary tree 中
-
```python
class CBTInserter(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.queue = [] # 定義
...
def insert(self, v):
"""
:type v: int
:rtype: int
"""
self.queue # 可直接用
...
```
- **Attemp 1:**
- $heap + queue$
- 只取 parent 的 index 值 (沒有插入node)
> **WA** (但console test可以(!?))
- **Solution 1:**
- $queue$
- 紀錄最後一個 parent
- 判斷插入parent的左/右邊
- 回傳parent在 $queue$ 中的index
> Runtime: 48 ms, faster than **94.94%** of Python online submissions for Complete Binary Tree Inserter.
> Memory Usage: 13.2 MB, less than **100.00%** of Python online submissions for Complete Binary Tree Inserter.
## 923. 3Sum With Multiplicity
- 2Sum with $O(n)$ solution:
兩個pointer $i$, $j$, $i<j$
$if A[i]+A[j] > target: j = j-1$
$if A[i]+A[j] < target: i = i+1$
$if A[i]+A[j] == target: j = j-1, i=i+1, count= count+1$
- 3Sum:
$for\ i\ in\ length(A):$
$target = A[i]$
$find\ target\ at\ A[i+1,len(A)-1]$
- 但在$A[j]+A[k] == target-A[i]$時有兩種情況：
1. $A[j] != A[k]:$
若陣列為$A=[2,2,3,4,5,5]$，$j=0,\ k=5$
:::warning
若立刻執行$j=j+1$及$k=k-1$會少算
$j=0,\ k=4$及$j=1,\ k=5$的組合
:::
class:
```python=
class indexAndSum():
def __init__(self, sum, index):
self.sum = sum
self.index = index
```
enumerate:
```python=
for i, x in enumerate(A):
# i: index
# x: A[i]
```
## 973. K Closest Points to Origin
- 找 K 與原點最接近的數字
- **Solution 1:**
- $\text{sort}$
- 根據 $key=x^2+y^2$
- 取前 $k$ 個數字
> Runtime: 592 ms, faster than **83.24%** of Python online submissions for K Closest Points to Origin.
Memory Usage: 17.5 MB, less than **73.58%** of Python online submissions for K Closest Points to Origin.
## 1019. Next Greater Node In Linked List
- 用一個stack儲存沒有找到next greater node的index
- $nodeList_i,i\ \in [1,\ n]$ ，若找到更大的值則更新answer，若無則push $i$
- for-loop $nodeList:\ O(n)$
stack push/pop 攤銷 $O(n)$ (因為每個元素最多push一次pop一次)
total time complexity $O(n)$
List最末元素:
```python=
> stack = [1,2,3,4]
> stack[-1]
4
```
## 1054. Distant Barcodes
- 找出鄰近不相同的字串排列(必存在)
- **Attemp 1:**
- 用 count 排序
- 每次間隔輸出
$[0,2,4,...,1,3,5,...]$
> TLET
- **Solution 1:**
- 用 `from collections import Counter`
- ```python
from collections import Counter
for k,v in Counter(barcodes).most_common():
# k: 數字
# v: 幾次
```
> Time: 70%
> Memory: 100%
## 1123. Lowest Common Ancestor of Deepest Leaves
- 找最深的葉子們的共同祖先，return該點
- 比較左右兩子樹，深度較深的那邊則$LCA(Lowest\ \ Common\ \ Ancestor)$為該子樹，若相等則return該root
- 用一helper函數遞迴求左右兩子樹的子問題
- time complexity $O(N)$
- space complexity $O(H)$
```python=
def lcaDeepestLeaves(self, root):
def helper(root):
if not root: return 0, None
h1, lca1 = helper(root.left)
h2, lca2 = helper(root.right)
if h1 > h2: return h1 + 1, lca1
if h1 < h2: return h2 + 1, lca2
return h1 + 1, root
return helper(root)[1]
```
## 1129. Shortest Path with Alternating Colors
- 給定$[0,n-1]$共$n$個點，並給定紅藍線段，找出0到所有點的最短路徑長，且需紅藍相間
- 從0開始做BFS，若0到[1,2]有紅色線段，則設[1,2]長度為1，且顏色為藍(下一個需接藍色)
- 最大值為$n\times2-3$ (unknown)
```python=
def shortestAlternatingPaths(self, n, red_edges, blue_edges):
G = [[[], []] for i in xrange(n)]
for i, j in red_edges: G[i][0].append(j)
for i, j in blue_edges: G[i][1].append(j)
res = [[0, 0]] + [[n * 2, n * 2] for i in xrange(n - 1)]
bfs = [[0, 0], [0, 1]]
for i, c in bfs:
for j in G[i][c]:
if res[j][c] == n * 2:
res[j][c] = res[i][1 - c] + 1
bfs.append([j, 1 - c])
return [x if x < n * 2 else -1 for x in map(min, res)]
```
- $map(function,\ list):$ return [function(element) for element in list]
## 1137. N-th Tribonacci Number
- $T_0=0,T_1=1,T_2=1,求T_n$
- 用 $a,b,c$ 存目前的三個值，用 $d$ 存三數總和
- 下一輪：$a = b, b=c,c=d$
- return最後一輪的 $d$
## 1138. Alphabet Board Path
- 一board存 $a$~$z$ 字母，給定 $target$ 陣列。
- 從 $a$ 出發，往上則輸出 $U$ ，往右 $R$，往左 $L$，往下 $D$，印出字 $!$
- 輸出路徑並印出字
- <font color=red>注意不能超過board的長寬</font>
- 解法：找出目標字母的 $(ascii\ code-97)$ ，求出**商**和**餘數**，若商大於目前位置，則 $D$，反之 $U$；若餘數大於目前位置，則 $R$，反之 $L$
- 超過board長寬則先往 $L$ 或 $U$
- 字母ascii code: ```ord("a")```，return ```97```
## 1139. Largest 1-Bordered Square
- 有多大的正方形邊長都是 1
- eg.
1 1 1
1 0 1
1 1 1
- **Solution 1:**
- 參考 [304. Range Sum Query 2D](https://hackmd.io/OzKKg2EWRemnUzOum6rRwQ?both#304-Range-Sum-Query-2D---Immutable)
- 正方形減掉中間小正方形的和
- 要等於 $n^2-(n-2)^2=4n-4, \forall n > 2$
- 檢查所有長度 $k$ 的正方形
> Runtime: 2060 ms, faster than **5.71%** of Python online submissions for Largest 1-Bordered Square.
Memory Usage: 12 MB, less than **100.00%** of Python online submissions for Largest 1-Bordered Square.
> $O(n^3)$
- **Solution 2:**
- DP 矩陣儲存 $\text{row, col}$ 的連續 $1$ 長度
(需要2個矩陣)
- 在點 $(i,j)$ 時，檢查
- $\text{col}(i-len,j) \geq len$
- $\text{row}(i,j-len) \geq len$
- [圖解](https://leetcode.com/problems/largest-1-bordered-square/discuss/345265/c%2B%2B-beats-100-(both-time-and-memory)-concise-with-algorithm-and-image)
> Time: $O(n^2)$
> Space: $O(n^2)$
## 1144. Decrease Elements To Make Array Zigzag
- 給定一陣列，找到最小的 $move數$，使得數列呈偶數(或基數)元素較左右兩邊元素小
- **Greedy**的方法，掃過陣列，若要偶數元素較小則減去能使得較左右元素小的值
- 因為若要使偶數元素較小，再減去基數元素的值，會使得偶數元素需要減的值更多
- eg. $[3,5,4]$，要使得 $5$ 較左右小，再減掉 $3$ 會使得 $5$ 需要減去的值更多， $move數$ 增加，減掉 $4$ 也會使 $move數$ 增加，且無助於讓 $5$ 小於 $3$
- 注意邊界值， $index$ 為零時不能檢查左邊， $index$ 大於 `len(nums)` 時不能檢查右邊。
- 不用設`if index == 0: 檢查右邊`
- 而是設`if index != 0: 檢查左邊`
- 否則當`if index < len(nums)/2`時仍要再做`檢查右邊`，程式碼重複
- Time complexity $O(N)$
## Google Former Coding Interview Question: Compression and Decompression
- [Former Coding Interview Question: Compression and Decompression](https://techdevguide.withgoogle.com/resources/compress-decompression/?types=coding-interview-question#!)
isalpha
```python=
> "3".isalpha()
False
> "a".isalpha()
True
```
## 1209. Remove All Adjacent Duplicates in String II
- 移除最多 $k$ 個相連的字母，直到沒有 $k$ 個相連的字母為止
- **Attempt 1:**
- 每次檢查前 $k$ 個字母，如果都相同則移除
- $O(nk)$
- worse case: $k=2$ "aaaaaaaaaa"
- 如果只能移除 $k$ 個則會重複移除很多次
> TLE
- **Attempt 2:**
- 若字不同時，才移除前面 $q$ 個，$q$ 必為 $k$ 的倍數
> TLE
- **Solution 1:**
- 遞迴
- 用 **Attempt 2** 的方式每次移除 $>k$ 的字母
- 直到字串沒有再發生變化為止
> Runtime: 52 ms, faster than **87.18%** of Python online submissions for Remove All Adjacent Duplicates in String II.
Memory Usage: **17.1 MB**, less than 100.00% of Python online submissions for Remove All Adjacent Duplicates in String II.
- **Solution 2:**
- 一直replace字串直到沒有發生變化為止
- `s.replace(pattern,"")`
## 1218. Longest Arithmetic Subsequence of Given Difference
- 找出最長的遞增/遞減子序列
- **Attempt 1:**
- 用 $\text{dictionary}$ 紀錄出現過的數字的出現位置
- 找 `arr[i]+difference` 是否在 $\text{dictionary}$ 中
- 若有則繼續搜尋下一個 `arr[i]+difference+difference`
> TLE
- **Attempt 2:**
- 從數列最後端開始用 $\text{dictionary}$ 紀錄
- 若 `arr[i]+difference` 在 $\text{dictionary}$ 中
- $\text{dictionary}[arr[i]]=1+\text{dictionary}[arr[i]+\text{difference}]$
- 因為選到越右邊的數，越有可能在左邊找到此等差
- eg. `[7,5,...,5,3,1]`
- 最好是選到最右邊的 `5`
> WA
- **Solution 1:**
- case: `[1,2,3,4,1,2,3]`
- **Attempt 2** 因為越右邊的數字越好，所以左邊的就不理會
- 可是左邊的數字也有機會使得長度越長
- 出現相同數字時，仍檢查 `arr[i]+difference` 是否在 $\text{dictionary}$ 中
> Runtime: 532 ms, faster than **57.66%** of Python online submissions for Longest Arithmetic Subsequence of Given Difference.
Memory Usage: 23 MB, less than **100.00%** of Python online submissions for Longest Arithmetic Subsequence of Given Difference.
## 1325. Delete Leaves With a Given Value
- 若 leaf 是 target value 則刪除，刪到最少為止
- **Attempt 1:**
- $heap$ 解
- 每次檢查 $\frac{index-1}{2}$ 的值 (parent) 是否為target，是則往上刪除
- 由 $TreeNode$ 轉成 $heap$ 需要用 <font color=red>$queue$</font> 而不是 $stack$
才會是 level order 的輸出 node
$dequeue:$ `queue.pop(0)`
- $heap$ 最好只存 $value$ 不存 $TreeNode$ 不然會耗費空間
> 空間耗費大
> 因為需要存取 $complete\ tree$
> 會 **TLE**
- **Solution 1:**
- $TreeNode$ 遞迴解
- 定義 `searchTree(node)` 為：
若 `searchTree(node.left)` 為空
且 `searchTree(node.right)` 為空
且 `node.val == target`
則 `return None`
否則 `return node`
> $DFS$ 時間複雜度
> Runtime: 40 ms, faster than **86.46%** of Python online submissions for Delete Leaves With a Given Value.
> Memory Usage: 12.7 MB, less than **100.00%** of Python online submissions for Delete Leaves With a Given Value.
## 1357. Apply Discount Every n Orders
- 每 $n$ 個客人有 $discount$ 的折扣
> 83.76%
## 1358. Number of Substrings Containing All Three Characters
- 含有 $\text{abc}$ 字串的子字串個數
- **Solution 1:**
- 用 $Flag$ 紀錄 $\text{a, b, c}$ 出現的位址
- 紀錄最後一次更新的位址
- 若無更新過則為 $-1$
- 若更新過則為 $min(Flag_a,Flag_b,Flag_c)$
- 紀錄 $min(Flag_a,Flag_b,Flag_c)$
- 若 $\text{a, b, c}$ 都有出現過且 $min$ 有變動，則計算
- $(min(Flag_a,Flag_b,Flag_c)-lastUpdate)\times (len(s)-max(Flag_a,Flag_b,Flag_c))$
- | lastUpdate | ... | i | ... | j | ... | len(s) |
| ---------- | --- | --- | --- | --- | --- | ------ |
| c | ... | a | b | c | ... | a |
- 算出含有 $i$ 到 $j$ 的所有子字串可能
- 從左到右計算 $O(n)$
- $lastUpdate$ 用來排除已經計算過的字串可能
- 如
- | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --- | --- | --- | --- | --- |
| b | b | c | c | a | b |
- 在 $i=4$ 時，$Flag_a,Flag_b,Flag_c=(4,1,3)$， $lastUpdate=-1$
- 含有 $\text{bcca}$ 的字串有 $\text{bbcca, bbccab, bcca, bccab}$
- $lastUpdate$ 紀錄為 $1$
- 在 $i=5$ 時，$Flag_a,Flag_b,Flag_c=(4,5,3)$， $lastUpdate=1$
- 含有 $\text{cab}$ 的字串有 $\text{ccab, cab}$ (不包含到 index 為 1 的 $\text{b}$)
> 71.63%
## 1359. Count All Valid Pickup and Delivery Options
- 給定 $n$ 個包裹，計算所有可能的 $\text{Pickup/Dilivery}$ 個數
- 如 $n=2$
- 可能的組合有
- $(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1), (P2,D2,P1,D1)$
- **Solution 1:**
- 因必須 $P$ 再 $D$
- 等同於 **$PD$ 無順序**
- $n=2$ 的例子可視為
- $(ABAB, ABBA, AABB, BAAB, BABA, BBAA)$
- $n=3$
- $(AABBCC)$ 的排列組合
- 公式： $$\frac{(2n)!}{(2!)^n}$$
> 83.89%
## 1361. Validate Binary Tree Nodes
- 給定 $n, lchild, rchild$，判斷是否為 binary tree
- **Solution 1:**
- 用 tree definition
- $edges = n-1$
- $inward = 1, outward = [0-2]$
> 47.24%
## 1362. Closest Divisors
- 給定 $num$ 找到 $num+1$ 或 $num+2$ 中兩個乘積最接近者
- $\text{return [a,b], where }a\cdot b=num+1\text{ or }a\cdot b=num+2$
- `sqrt(num)` 也可用 $i^2==num$ 判斷
- **Solution 1:**
- $\text{for }i\in[1,\sqrt{num}]$
> 11.54%
- **Solution 2:**
- $\text{for }i\in[\sqrt{num},1]$
## 1363. Largest Multiple of Three
- 給定 $digits$ 選出能組成最大的 $3$ 的倍數的數字
- **Solution 1:**
- $Greedy:$ 越多位數越好
- 每次減少一個非三的倍數 (從最小的開始)
- 從 $9 ～ 0$ 輸出結果
## 1366. Rank Teams by Votes
- 找出哪個team得到最多votes
- 若前面位置的票的權重 **無限大於** 後面位置的票的權重
- 若票相同則按字母序輸出 team
- **Solution 1:**
- 建立26個字母的表
- 計算每個vote
- ex. ["WXYZ","XYZW"]
- list[W] = [1001]
- list[X] = [1100]
- list[Y] = [0110]
- list[Z] = [0011]
- 比較兩個list:
- 若第 $0-i$ 位數大於另一個list，則較大
- 若第 $0-i$ 有較小的數，則較小
- 若 $0-n$ 都相同，則相同
> Time 7.56%
## 1367. Linked List in Binary Tree
- 找出tree中有沒有linked list的字串
- **Attemp 1:**
- $DFS$
- 若`node.val == target.val`
- 則遞迴搜尋 `node.right` `node.left` `target.next`
- 如果 `target == None return True`
> 如果 `target.val` 非 `head`，直接找`node.left(right)` 會忽略 `node.val == head.val` 的可能
- **Solution 1:**
- $DFS$ 如上
- 最後 `return search(node, head) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)`
> Time 23.11%
## 1371. Find the Longest Substring Containing Vowels in Even Counts
- 找到最長 substring 裡面有偶數個母音(aeiou)
- **Attemp 1:**
- 找 $i$ 到 $j$ 中母音數量是不是為零
- $aCount[j] - aCount[i]\ \%2==0$
- $O(n^2)$
> **TLE**
- **Solution 1:**
- 用 $hash\ table$ 紀錄出現過的母音pattern
- $aeiou=01010$
$1$ 表示母音出現過奇數次
$0$ 表示母音出現過偶數次
- 若 pattern 沒有出現過，則紀錄 index
- 若 pattern 出現過，則搜尋第一次出現的 index
- 兩個 index 相減則是可以造出的合法字串長度
- $\text{Time: }O(n)$
$\text{Space: }O(2^5)=O(1)$
## 1372. Longest ZigZag Path in a Binary Tree
- 找到最長 ZigZag 路徑 (左子樹，右子樹，左子樹...)
- 用遞迴時要注意子樹中最長 ZigZag 路徑不一定能和 root 相加
- 可能沒有連續
- `return [left, right, max]`
## 1375. Bulb Switcher III
- 每次開一盞燈，算出幾個 phase 前面的燈會都開過
- **Solution 1:**
- 儲存目前開到的最大的燈泡值
- 如果 $max==(i+1)$ 則 $count+1$
> Time: 98.52%
> $O(n)$
## 1376. Time Needed to Inform All Employees
- 算出通知樹狀結構的每個下屬的時間
- **Attemp 1:**
- 每次往上尋找 manager 直到 root
- 更新每個 manager 最大的通知下屬的時間
`max(informTime[all child node])`
- $timeSum$ 儲存每個**下到上**的 `informTime`
(會因 children 而有不同)
> **TLE**
- **Solution 1:**
- $timeSum$ 儲存**上到下**的 `informTime`
(上到下的時間不會變)
- $timeSum$ 儲存後可供之後要用的 child 的點檢索
- 只找 `informTime[i] == 0` 的點(下屬)
- 用 $stack$ 儲存往 header 搜尋時經過的 node
之後 $pop$ 出這些 node 更新 $timeSum$
- `return max(timeSum)`
> 攤銷 $O(n)$
> 跑過的 manager 的點不用再跑一次
> Time : 99.13%
## 1382. Balance a Binary Search Tree
- 平衡二元搜尋樹
- **Attemp 1:**
- AVL tree
> WA
- **Solution 1:**
- 先建立 Tree 中有哪些數字
- 用這些數字建立 Tree
> good in time and space
## 1383. Maximum Performance of a Team
- 從 $n$ 個工程師裡面挑最多 $k$ 個使得 performance 越好
- $max\{(\sum\text{speed}_i)\times min(\text{efficiency}_i)\}, i<k$
- **Attemp 1:**
- $i\in[1,n]$
- 檢查 $\text{perfomance}[1:i-1],\text{perfomance}[i], \text{perfomance}[1:i]$ 哪個較好
- (假設可以求出在 $i$ 前的最好結果)
> WA
> 若相同 performance，但再加入工程師時結果會不同
- **Solution 1:**
- `bisect.insort(array, element)`
- 在 `array` 中插入 `element` 使得 `array` 仍排序過
- 按照 $\text{efficiency}$ 排序，但仍存 $\text{speed}$ 的排序結果
- 若結果數大於 $k$ 則減掉此 $\text{efficiency}$ 前最小的 $\text{speed}$
> $O(n^2)$
> 用 $\text{priority queue}$ 為 $O(nlogk+nlogn)$
>
## 1392. Longest Happy Prefix
- 找最長的 $\text{prefix = suffix}$
- **Solution 1:**
- $\text{KMP}$ 的 $\text{prefix table}$
-
| A | B | A | B | C | A | B | A | A |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| A | | | | | | | | |
| A | B | | | | | | | |
|**A** | B | **A** | | | | | | |
|**A** | **B** | **A** | **B** | | | | | |
| A | B | A | B | C | | | | |
| **A** | B | A | B | C | **A** | | | |
| **A** | **B** | A | B | C | **A** | **B** | | |
| **A** | **B** | **A** | B | C | **A** | **B** | **A** | |
| **A** | B | A | B | C | A | B | A | **A** |
| 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 1 |
- [KMP演算法](https://youtu.be/3IFxpozBs2I)
## 1395. Count Number of Teams
- 給定一個數列(unique)，計算有幾種可能的隊伍組合
$\text{rating}[i]<\text{rating}[j]<\text{rating}[k]$
$\text{rating}[i]>\text{rating}[j]>\text{rating}[k]$
- **Solution 1:**
- 暴力法
- 三個 $for$ 迴圈找到合適的 $i,j,k$
> $O(n^3)$
> Runtime: **50.33%**
- **Solution 2:**
- 以 <font color=red>$j$</font> 為 $iterator$
- 找 $j$ 前有幾個比 $j$ 大 <font color=#ff9e12>(小)</font> 的數字
- 找 $j$ 後有幾個比 $j$ 小 <font color=#ff9e12>(大)</font> 的數字
- $out := \sum_{j=1}^{n-2}less_{left}\times greater_{right}+less_{right}\times greater_{left}$
- example:
- `[13, 3, 4, 10, 7, 8]`
- $j=2, \text{ rating[2]}=4$
- 在 $4$ 左邊比 $4$ 小：$3$
在 $4$ 右邊比 $4$ 大： $10,7,8$
- 可能的組合: $(3,4,10),(3,4,7),(3,4,8)$
- $less_{left}\times greater_{right}=3$
> $O(n^2)$
## Line筆試
- 輸出`abc`的排列組合(可重複字母)
- 共有 $n^n$ 種組合
```python
def permute(pre,s,n):
if n == 0:
print(pre)
return
for i in range(len(s)):
permute(pre+s[i], s, n-1)
permute("","abc",3)
```
## Google New Grads phone interview
-
```python
def path(matrix, effort):
passed = [[0 for i in range(len(matrix))]for i in range(len(matrix))]
i = 0
j = 0
stack = [(i,j)]
while stack:
(x,y) = stack.pop()
if x == len(matrix)-1 and y == len(matrix)-1:
return True
if y < len(matrix)-1: # right
if abs(matrix[x,y]-matrix[x,y+1]) <= effort and not passed[x][y+1]:
stack.append((x,y+1))
if x < len(matrix)-1: # down
if abs(matrix[x,y]-matrix[x+1,y]) <= effort and not passed[x+1][y]:
stack.append((x+1,y))
if y > 0: # left
if abs(matrix[x,y]-matrix[x, y-1]) <= effort and not passed[x][y-1]:
stack.append(x, y-1)
if x > 0: # up
if abs(matrix[x,y]-matrix[x-1,y]) <= effort and not passed[x-1][y]:
stack.append(x-1,y)
passed[x][y] = True
return False
```
Sign in with Wallet
Connect another wallet