# Data Structures and Algorithms - 資料結構與演算法
## TL;DR
學習資料結構與演算法的筆記整理
# 深度優先搜索與廣度優先搜索 DFS and BFS on Tree and Graph
## 重點整理
* 以 `while` loop 與 Queue 實現 BFS
* 以 Recursion 實現 DFS
* 在 Graph 上多考慮 Redundancy 問題
* Tree 的解題重點通常在於在每一個 node 上要做什麼事情，還有要使用 Bottom-up 還是 Top-down
## Implementing BFS on Binary Tree
### 邏輯
1. Add the starting node (`root` node) to the queue
2. while queue is not empty
1. 利用變數 `currentNode` 指向正在操作的 node (to mark which node you are operating on) - `dequeue()`
2. Visit the `currentNode`
3. Check `currentNode` 是否有左子節點與右子節點，有的話 Add them to the queue
```
if (currentNode.left) {queue.push(currentNode.left)}
if (currentNode.right) {queue.push(currentNode.right)}
```
```
const queue = []
queue.push(root)
while (queue.length > 0) {
const current = queue.shift()
// Visit the current node
if (current.left) {queue.push(current.left)}
if (current.right) {queue.push(current.right)}
}
```
## Implementing DFS on Binary Tree
使用 Recursion 比較適合，利用 Iteration 來建立 DFS 時，Preorder, Inorder, Postorder 三種方法會很不一樣，並不只是換指令的順序而已。
### 邏輯
1. 定義一個 helper function `traverse()`，接受一個參數 `currentNode`
1. Base case: `currentNode === null`
2. Recursive case:
* Visit the `currentNode`
* 以左子節點與右子節點作為參數調用 recursive function
> 在 Recursive Calls 之前、之中、之後 visit `currentNode` 決定是 Preorder, Inorder, 還是 Postorder
2. Invoke the helper function with the starting node (root node) as the input parameter
```
const traverse = (current) => {
if (current === null) {return}
// Proorder
traverse(current.left)
// Inorder
traverse(current.right)
// Postorder
}
```
## Implementing BFS on Graph
概念基本上與 BFS on Tree 類似，但是 Graph 需要多考慮 Redundancy 的問題，也就是同一個 Vertex 可能被重複走訪，需要透過一個 set to keep track of the vertex that has been visited
#### 邏輯
1. Add the starting node to the queue
2. Add the starting node to the set
3. While queue is not empty
1. 利用變數 `currentNode` 指向正在操作的 node (to mark which node you are operating on) - `dequeue()`
2. Visit the `currentNode`
3. Loop through all `neighbors`
4. Check `neighbors` 是否有被走訪過
5. 沒有的話 add them to the queue, add them to the set
```
const queue = []
const visited = new Set()
queue.push(start)
visited.add(start)
while (queue.length > 0) {
const current = queue.shift()
// Visit the current node
const neighbors = graph[current]
for (let i = 0; i < neighbors.length; i++) {
if (!visited.has(nieghbors[i])) {
queue.push(neighbors[i])
visited.add(neighbors[i])
}
}
}
```
## Implementing DFS on Graph
概念基本上與 DFS on Tree 類似，但是 Graph 需要多考慮 Redundancy 的問題，也就是同一個 Vertex 可能被重複走訪，需要透過一個 set to keep track of the vertex that has been visited。
### 邏輯
1. 定義一個 helper function `traverse()`，接受一個參數 `currentNode`
1. Base case: `currentNode` has been visited
2. Recursive case:
* Visit the `currentNode`
* **Add the `currentNode` to the set**
* 以 `neighbors` 作為參數調用 Recursive Function
2. Invoke the helper function with the starting node as the input parameter
```
const visited = new Set()
const traverse = (current) => {
if (visited.has(current)) {return}
// Visit the current node
visited.add(current)
const neighbors = graph[current]
for (let i = 0; i < neighbors.length; i++) {
traverse(neighbors[i])
}
}
```
DFS on Graphs 也可以利用 `while` loop 與 Stack 來實現，將 BFS on Graph 的步驟中的 Queue 改成 Stack 即可。
# 回溯法 Backtracking
## 回溯法的邏輯
簡單來說，**Backtracking 就是回到上一個選擇的狀態**。逐一嘗試各種可能 (Enumeration of Candidates 列舉各種可能性, enumeration 列舉)，在嘗試過程中若發現路徑不為解或已窮盡所有可能，退回前一步驟，重新嘗試其他可能。
## 解題重點
以我目前的解題經驗來看，**Backtracking 通常搭配遞迴函數實現窮舉。窮舉的邏輯是一個樹狀結構，窮舉的過程是 DFS on Tree**。
### 如何分析一個窮舉過程
建立窮舉邏輯的樹狀結構時，思考窮舉過程的三個元素：
* 路徑 (path) - 已經做的選擇
* 選擇 (options) - 目前可以做的選擇
* 終止條件 (base cases) - 遞迴終止的條件
**窮舉的邏輯主要分為兩個層面**
* 第一個層面 (做選擇) - 調用 Recursion，選擇後的狀態調用 Recursion 代表做了一個選擇，往下一個選擇移動。
* 第二個層面 (窮舉各種選擇) - 利用 Iteration 窮舉當下的所有選擇。Backtracking 會與 Iteration 在同一個 level 發生，在每一個 Iteration 裡
1. 做選擇
2. 調用遞迴
3. 取消選擇
簡而言之，做選擇就是在樹狀結構上執行 DFS，做完選擇，狀態改變，掉用遞迴，前往下一個狀態。
```
let result = []
const backtrack = (path, options) => {
if (base case) {
result.push(path)
return
}
for (option in options) {
path.push(option) // 做選擇
backtracking(path, options) // 調用遞迴
path.pop() // 取消選擇
}
}
```
# 排列組合 Permutation and Combination
**排列組合的解題邏輯基本上靠窮舉，窮舉的邏輯是一個樹狀結構而窮舉的過程就是 DFS on Tree，所以可以透過 DFS 搭配 Backtracking 的概念走訪窮舉邏輯的樹狀結構得到所有的可能。DFS 靠 Recursion 實現**。
用 Recursion 來實現窮舉的時候，需要解決的問題是如何建立 Recursion。有三個元素可以幫助思考如何建立 Recursion 來窮舉。
* 路徑 (path) - 已經做的選擇
* 選擇 (options) - 目前可以做的選擇
* 終止條件 (base cases) - 遞迴終止的條件
## 解題步驟
1. 以上述三點建立窮舉的樹狀邏輯 - 每個步驟 (節點) 的狀態要標示清楚是關鍵
2. **透過樹狀邏輯得到 Recursion 函數需要的參數與 Base Case**
3. 再利用模板確認細部邏輯
## 排列 Permutation
### 定義
從給定個數的元素中取出指定個數的元素進行排列。元素相同但順序不同為不同的排列。(順序不同算不同)
### 邏輯
因為是排列，先取 1 再取 2 與先取 2 再取 1 是不一樣的，所以除了路徑中已經被選過的元素不能再選以外 (通常排列不考慮同一元素可以重複使用)，所有選擇都在被考慮範圍。若選項中有重複的元素，在同一個 Level 相同元素的選項是被視為相同的，不需重複選取。
### 模板
使用模板前先考慮三個問題：
* 是不是排列？
如果是，要考慮順序。先取 1 再取 2 與先取 2 再取 1 是不一樣的。每次都從頭 loop through 所有選擇。
```
for (let i = 0; i < options.length; i++) {
// 做選擇
}
```
* 同一元素可不可以重複使用？
若是不能重複同一元素，用一個 `used` array 紀錄這個 index 有沒有用過。做決定時 `used[i] = true`，在 backtrack 時 `used[i] = false`。`if (used[i]) {continue}` 跳過這個選擇。
* options 裡面有沒有重複的元素？
若有重複元素，在同一個 level 遇到重複的元素應視為相同的選擇，要忽略。**先將 options 排序後**，當 `i > 0 && !used[i - 1] && nums[i] === nums[i - 1]` 時 `continue`(**`used[i - 1] === false` 因為有 Backtracking**，`used[i - 1] === true` 會發生在下一個 Level 的選擇但元素與上一個 Level 被選擇的元素一樣，此時 `options[i]` 是可以選擇的)
* 檢查 Backtracking
[LeetCode 47 花花答案參考](https://zxi.mytechroad.com/blog/searching/leetcode-47-permutations-ii/)
```
options = options.sort((a, b) => a - b)
dfs(state, path, used) {
if (state === 終止條件) {遞迴終止}
for (let i = 0; i < options.length; i++) {
if (used[i]) {continue}
used[i] = true
path.push(options[i])
dfs(state + options[i], path, used)
path.pop()
used[i] = false
}
}
```
## 組合 Combination
### 定義
從給定個數的元素中取出指定個數的元素，不考慮排序。元素相同但順序不同依然為相同的組合。(順序不同算相同)
### 邏輯
因為是組合，先取 1 再取 2 與先取 2 再取 1 是一樣的，所以前面選過的元素後面不要再考慮。同一個元素是否可以重複選取會影響接下來可做的選擇。若選項中有重複的元素，在同一個 Level 相同元素的選項是被視為相同的，不需重複選取。
### 模板
* 是不是組合？
如果是，不考慮順序。先取 1 再取 2 與先取 2 再取 1 是一樣的。定義一個 `start` 參數，loop through 選擇的時候從 `start` 開始，避免重複的組合。
```
for (let i = start; i < options.length; i++) {
// 做選擇
}
```
* 同一元素可不可以重複使用？
如果可以重複使用同一元素，要做下一個選擇的 `start` 不變。若是不能重複同一元素，要做下一個選擇時 `start + 1`。
* options 裡面有沒有重複的元素？
若有重複元素，在同一個 level 遇到重複的元素應視為相同的選擇，要忽略。**先將 options 排序後**，當 `i > start && options[i] === options[i - 1]` 時 `continue`
* 檢查 Backtracking
```
options = options.sort((a, b) => a - b)
dfs(state, path, start) {
if (state === 終止條件) {遞迴終止}
for (let i = start; i < options.length; i++) {
path.push(options[i])
dfs(state + options[i], path, i)
path.pop()
}
}
```
## 範例
### 39. Combination Sum
Time Complexity:
為 n 叉樹的節點數，n 為 the size of candidates array
樹高為 target / min value in candidates，考慮每次都加最小值
節點數 = 1 + n + n ^ 2 + .... + n ^ (target / min)
等比級數和公式 = a0(1 - r ^ (n)) / 1 - r
所以節點數為 (1 - n ^ ((target / min) + 1)) / 1 - n
Space Complexity:
O(target / min)
### 46. Permutations
Time Complexity:
1 + n + n(n - 1) + ... + n! (應該是這樣)
Space Complexity:
O(n!)
Sign in with Wallet
Connect another wallet