---
# System prepended metadata

title: Data Structures and Algorithms - 資料結構與演算法

---

# 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!)