---
# System prepended metadata

title: DSA

---

---
title: DSA bestmark520
autoHeadingNumber: true
---
[TOC]
<!-- 按 Ctrl+Shift+P → Markdown: Create Table of Contents-->

# 容器：線性結構
## 線性容器語法總整理：Python, C, C++, string, list, dict
![001](https://hackmd.io/_uploads/H1dU8RM_le.png =75%x)

<div style="overflow-x: auto; white-space: nowrap;">

| 資料結構 | 操作 | Python | C | C++ |
| - | - | - | - | - |
| String<br>List / Array / Vector<br>Dict / Map | **宣告** | `data = ""`<br>`data = []`<br>`data = {}` | `char data[100] = "";`<br>`int data[10] = {0};`<br>無內建 dict | `std::string data = "";`<br>`std::vector＜int＞ data = {};`<br>`std::map＜string,int＞ data;` |
| String<br>List / Array / Vector<br>Dict / Map | **修改** | `data = data.replace("a","b")`<br>`data[0] = 10`<br>`data["a"] = 10` | `data[0] = 'A';`<br>`data[0] = 10;`<br>無內建 dict | `data[0] = 'A';`<br>`data[0] = 10;`<br>`data["a"] = 10;` |
| String<br>List / Array / Vector<br>Dict / Map | **新增** | `data += "abc"`<br>`data.append(3)`<br>`data["b"]=20` | `strcat(data, "abc");`<br>無法（固定長度）<br>無內建 dict | `data += "abc";`<br>`data.push_back(3);`<br>`data["b"] = 20;` |
| String<br>List / Array / Vector<br>Dict / Map | **刪除** | `data = data.replace("abc","")`<br>`del data[0]`<br>`del data["a"]` | `data[0] = '\0';`<br>無法真正刪除<br>無內建 dict | `data.erase(3,3);`<br>`data.erase(data.begin());`<br>`data.erase("a");` |
| String<br>List / Array / Vector<br>Dict / Map | **清空** | `data = ""`<br>`data.clear()`<br>`data.clear()` | `data[0] = '\0';`<br>`for(i) data[i]=0;`<br>無內建 dict | `data.clear();`<br>`data.clear();`<br>`data.clear();` |
| String<br>List / Array / Vector<br>Dict / Map | **複製** | `new = data[:]`<br>`new = data.copy()`<br>`new = data.copy()` | `strcpy(new, data);`<br>`memcpy(new, data, sizeof(data));`<br>無內建 dict | `std::string new = data;`<br>`std::vector＜int＞ new = data;`<br>`auto new = data;` |
| String<br>List / Array / Vector<br>Dict / Map | **取代** | `data = data.replace("a","b")`<br>`data = [x*2 for x in data]`<br>`data["a"]=999` | loop 手動替換<br>手動 for<br>無內建 dict | `std::replace(data.begin(),data.end(),'a','b');`<br>`for(auto ＆x:data)x*=2;`<br>`m["a"]=999;` |

</div>

## String 字串
python
```python
# 宣告
data = " " * n # 建立新字串 # data = '     '  (n 個空白)
data = "Hello" # 宣告 # Hello

# 新增
data += " World" # Hello World

# 刪除
data = data.replace("World", "") # Hello_

# 其他
data = data.strip() # 去除首尾空白 # Hello

# 字串分割
s = abcdefghijklmnopqrstuvwx
'''
s[0] 是 a
s[1] 是 b
s[2] 是 c
'''

# string -> list
c = [s[i:i + 6] for i in range(0, 24, 6)]
#將字串變成list，有24字元的s分隔成4段，每段有6個字元
'''
s[0:6] 是 abcdef  #最後一個s[6]不會顯示
s[6:12] 是 ghijkl
'''
print(c) # ['abcdef', 'ghijkl', 'mnopqr', 'stuvwx']
```
c++
```cpp
// 宣告
string data1;                // 空字串
string data2 = "";          // 空字串
string data3 = string();    // 空字串
string data = "Hello";     // 初始化字串

// 修改
data[4] = 'a';             // 修改單一字元 => "Hella"

// 新增
data += " World";          // 字串串接 => "Hella World"

// 刪除
data.erase(5, 6);          // 從索引5刪6個字元 => "Hella"
data.erase(5, 1);          // 刪除索引5的1個字元
data.erase(5);             // 從索引5刪到結尾
data.erase();              // 清空整個字串
data.erase(data.begin() + 5, data.end());  // 用迭代器刪除部分字串

// 其他常用操作
cout << data.size() << endl;     // 長度
cout << data.empty() << endl;    // 是否為空
data.clear();                    // 清空
data.insert(0, "Hi ");           // 插入字串 => "Hi Hella"
data.replace(3, 2, "ABC");       // 取代位置3起的2個字元為"ABC"

// 字串容器
vector<string> ans_(5, "");  // 建立一個有5個空字串的vector
```
c
```c
#include <stdio.h>
#include <string.h>

int main() {
    // 宣告
    char data1[100] = "";       // 空字串（預留空間100）
    char data[100] = "Hello"; // 初始化字串

    // 修改
    data[4] = 'a';            // 修改單一字元 => "Hella"

    // 新增（串接）
    strcat(data, " World");   // 串接 => "Hella World"

    // 刪除
    // 在 C 裡沒有 erase 函式，要用手動改字元或 strcpy
    data[3] = '\0';           // 從索引5開始刪到結尾 => "Hel"

    // 清空
    data[0] = '\0';           // 清空整個字串

    // 複製
    strcpy(data, "Hi there");  // data = "Hi there"

    // 取代
    // 沒有 replace，需用邏輯自行實作，例如：
    strcpy(data, "Hella World");
    strncpy(data + 3, "ABC", 3);   // 從位置3起覆蓋3個字元 => "HelABCWorld"

    // 長度
    printf("長度: %zu\n", strlen(data));

    // 比較
    if (strcmp(data, "Hello") == 0)
        printf("相等\n");

    // 判斷空字串
    if (strlen(data) == 0)
        printf("空字串\n");

    return 0;
}
```
### C: string reverse
```c
void reverse_string(char str[]) {
    int len = 0;
    while (str[r] != '\0') len++; // 找長度
    
    // 用for
    for (int i = 0; i<len/2; i++){
        char temp = str[i];
        str[i] = str[len -1 -i];
        str[len - 1 -i] = temp;
    }
    
    // 用while
    int i = 0;
    len--;
    while (start < len) {
        char tmp = str[i]; // func內部交換不用指標
        str[i] = str[len];  // 也可以改成str[i] = str[r -1 -i];
        str[r] = tmp;
        i++;  // 這是取代for的i++
        r--;
    }
}

int my_strlen(char *s) {
    char *p = s;
    while (*p != '\0') p++; // 當前字元不是字串結尾符 '\0'
    return p - s;
}

void swap(char *a, char *b) {
    char t = *a;
    *a = *b;
    *b = t;
}

void reverseString_callfunc(char *s) {  // 如果input有size就不用實作len
    if (s == NULL) return;
    int len = my_strlen(s);
    
    // 用for
    for (int i = 0; i < len / 2; i++) {
        swap(&s[i], &s[len - 1 - i]);
    }
    
    // 用while
    char *start = s;
    char *end = s + len - 1;
    while (start < end) {
        swap(start, end);     // 交換兩個字元
        start++;
        end--;
    }
}
```
## Python list、C++ vector、C array
- List 的實現比較複雜
- List 與 array 不同的是，它的大小可以動態調整，元素也可以是不同類型
- Python：list 幾乎就是日常用的主要容器，array 僅效能較佳
- C：array 最常用，linked list 偶爾用
- C++：vector 幾乎取代了大部分需要 list 的情況，真正的 linked list (std::list) 很少用
- 檢索、寫入、輸出、複製
- 插入：第 i 個位置插入新元素，原來第 i 之後的元素會往後移一個位置，最後一個元素可能丟失
- 刪除：去除第 i 個位置元素，原來 i + 1 之後的元素往前一個位置，最後一格元素變無意義（或0）

| ![010](https://hackmd.io/_uploads/r1HBdkmdxl.png) | ![010](https://hackmd.io/_uploads/BksBOJ7uge.png) |
| --- | --- |

| ![010](https://hackmd.io/_uploads/H118OyQ_lg.png) | ![010](https://hackmd.io/_uploads/HkfI_yQ_lg.png) |
| --- | --- |
```python
# 宣告
data = []                        # 空列表
data = [1, 2, 3]                 # 直接建立
data = (1, 2, 3)                 # 這是 Tuple，不可變，盡量不要用
data = [(1, 2, 3), (7, 8, 9)]    # List of Tuples，不是array
data = list([1, 2, 3])           # 轉換為 List（實際上多餘）
data = list((1, 2, 3))           # Tuple 轉 List
data = [x**2 for x in range(10)] # List Comprehension

s = "abcdefgh"
data = [""] * n # 字串的列表 # data = ['', '', '', '', ''] # ""連在一起中間沒空格所以是空的
data[x] += s[i] # 把string值存到list

# 修改
data[2] = 30 # 修改第3個元素
data[1:3] = [20, 40] # 修改第2、3個元素
data2[:] = data  # list整個替換另一個list

# 新增
data.append(5)       # 在列表末尾新增 5
data.append([nums[i], nums[left], nums[right]]) # List[List[int]]的方法
data.extend([6, 7])  # 在列表末尾新增list [6, 7]
data.insert(2, 99)   # 在索引 2 插入 99 # ['a', 'b' , 99, 'c']

# 移除
data.remove(40)      # 移除第一個出現的 40
popped_value = data.pop(3)  # 移除索引 3 的值，並返回該值
del data[1]          # 刪除索引 1 的元素
del data[1:3]        # 刪除索引 1 到 2 的元素
data.clear()         # 清空列表

# 其他
data.sort()
data.reverse()
new_data = data.copy()
if not data: print("空")
data = [1, 2, 3, 4, 5]
print(len(data), max(data), min(data), sum(data))  # 5, 5, 1, 15
print(data[0], data[-1])  # 1, 5
print(data[1:4], data[:3], data[2:], data[::-1])  # [2, 3, 4], [1, 2, 3], [3, 4, 5], [5, 4, 3, 2, 1]

# list → string # '跟"沒差異
my_list = ["Hello", "World", "!"] # my_list[0][1] equals e
data = " ".join(my_list) # data = Hello World ! 
data = ''.join(my_list) # data = HelloWorld!
data = ' && '.join(my_list) # data = Hello && World && !

# string → list
my_string = "hello world"
my_list = list(my_string) # ['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
my_list = [my_string] # ['hello world']
my_list = my_string.split() # ['hello', 'world']
```

```cpp
vector<int> data;               // 空 vector
vector<int> data(5);            // 長度 5，預設 0
vector<int> data(5, 10);        // 長度 5，預設值為 10
vector<int> data = {1, 2, 3};   // 直接初始化
vector<pair<int, char>> data(26);  // 類似 dict 結構

// 修改
data[1] = 20;

// 新增
data.push_back(5); // 在尾部加入 5
data.insert(data.begin() + 2, 99); // 在 position 位置插入 value

// 移除
data.erase(data.begin());         // 刪除開頭
data.erase(data.begin() + 3);     // 刪除索引 3
data.pop_back();               // 刪除尾部元素
data.clear();  // 清空所有元素

// 其他
cout << data.at(1) << endl; // 如果超範圍會提醒
int n = data.size();
int m = data.capacity();
vector<int> new_data = data; // 複製
sort(data.begin(), data.end());
reverse(data.begin(), data.end());

// 沒有內建切片，需手動處理
vector<int> sliced(data.begin()+1, data.begin()+4);

nums1.resize(m);  // 把nums1的長度直接變m
data.empty()  // 如果data是空的
if (!data.empty())  // 如果data不是空的
```
```c
#include <stdio.h>
#include <stdlib.h>

int main() {
    int capacity = 10;               // 最大容量
    int size = 5;                    // 目前長度
    int *data = malloc(capacity * sizeof(int));  // 在heap區宣告
    int ListArray[1000];  // 在stack區宣告

    // 初始化
    for (int i = 0; i < size; i++)
        data[i] = i + 1;             // data = [1,2,3,4,5]

    // 新增(push_back)
    data[size++] = 6;

    // 插入(insert at index 2)
    for (int i = size; i > 2; i--)
        data[i] = data[i - 1];
    data[2] = 99;
    size++;

    // 刪除(index 3)
    for (int i = 3; i < size - 1; i++)
        data[i] = data[i + 1];
    size--;

    // 反轉
    for (int i = 0; i < size / 2; i++) {
        int tmp = data[i];
        data[i] = data[size - 1 - i];
        data[size - 1 - i] = tmp;
    }

    // 輸出結果
    printf("Array: ");
    for (int i = 0; i < size; i++)
        printf("%d ", data[i]);
    printf("\n");

    free(data);
    return 0;
}
```

### C: array reverse
```c
void reverse(int arr[], int size) {
    int temp;
    for (int i = 0; i < size / 2; i++) {
        temp = arr[i];
        arr[i] = arr[size - 1 - i];
        arr[size - 1 - i] = temp;
    }
}

// 補充array計算長度僅能在main進行
int arr[5];
int len = sizeof(arr) / sizeof(arr[0]);  // = 5
```

### Python 2D array 二維陣列
- `list of list` & `np.array`
- 列row、行column，大陸日本美國英文中文相反，數學上的「矩陣」恰好可以用二維陣列來表示與儲存
- 矩陣輸出： 例如輸入矩陣大小 4 x 3，則依序填入 1 到 12，輸出在螢幕上
- 矩陣相加：矩陣相加的條件是兩矩陣行列數相同
- 矩陣相乘：兩矩陣中一方行必須等於另一方列。例如：A = m x n, B = n x t, 兩者相乘 C = m x t

![010](https://hackmd.io/_uploads/SyP38VQugg.png =35%x)

注意陷阱：錯誤初始化
```python
# 錯誤：所有列指向同一個 list
arr = [[0]*3]*4
arr[0][0] = 9
print(arr)  # [[9, 0, 0], [9, 0, 0], [9, 0, 0], [9, 0, 0]]

# 正確：每列都是獨立物件
arr = [[0]*3 for _ in range(4)]
```

建立 np.array
```python
import numpy as np

# 1D
a = np.array([1, 2, 3])

# 2D
b = np.array([[1, 2], [3, 4]])

# 宣告指定內容
c = np.array([[1, 3, 5], [2, 4, 6]])

# 指定大小的初始化
zeros = np.zeros((3, 4))   # 3x4 全為 0
ones = np.ones((2, 2))     # 2x2 全為 1
full = np.full((2, 3), 7)  # 2x3 全為 7
identity = np.eye(3)       # 3x3 單位矩陣
```

修改、插入、刪除
```python
c[0, 1] = 99                            # 修改
c = np.append(c, [[5, 6, 7]], axis=0)   # 插入新列
c = np.insert(c, 1, [7, 8, 9], axis=0)  # 在第 1 列插入
c = np.delete(c, 0, axis=0)            # 刪除第 0 列
```

其他常用操作
```python
print(c.shape)      # 尺寸
print(c.T)          # 轉置
print(c.sum(axis=0))  # 每欄加總
print(c.flatten())  # 轉為一維
```

## Dictionary 字典
- `Python`的`dict` `=` `C++`的`map` `!=` `Python`的`map` 
* `Python` 的 `dict`、`set` 都是用 `Hash Table`實作
*  `Hash Table`的輸入%某值直接找這個key是否存在，查找效率為O(1)
*  `set`是`dict`只有key沒有value
* `C++` 的 `dict` 語法是 `map` 用Red-Black Tree（紅黑樹）實作， 查找效率為 O(log n)，並且會自動依 key 排序
* `Python` 的 `map()` 函數 跟 `C++` 的 `map` 完全無關：
  * `Python` 的 `map(func, iterable)` 是一種 函式工具（Functional Programming）
  * 它的功能是：將某個函數應用到 iterable（如 list）中的每個元素
  * 例如讓list裡面的元素都平方
* `C`的`dict`要自己手刻

| ![025](https://hackmd.io/_uploads/Bk4diEmdxg.png)| ![025](https://hackmd.io/_uploads/BJ_djNmdlx.png) |
| --- | --- |

雜湊函式hash function，index = hash(key) % capacity，如下圖capacity = 100
雜湊衝突與擴容，用上述方法，%100可能會一樣的答案，解決方法為改成%200
|![025](https://hackmd.io/_uploads/H1Oho47ulg.png =55%x)|![026](https://hackmd.io/_uploads/H1Jps4muel.png =55%x)|
| --- | --- |

```python
# 宣告與初始化
hmap: dict = {} # 同 hmap = {} # hmap = []是list
dic = {} # 空字典
dic = {"a": 5, "b": 2} # 直接指定 # {key: value}
dic = {3: 1} # 把數字當key就不用 " "
dic = dict(a=5, b=2) # 用 dict() 函數
pairs = [("x", 1), ("y", 2)] # 從 list of tuple 建立
dic = dict(pairs)

# 存取元素
dic["a"]          # 取出 key = "a" 的值 → 5
dic.get("a", 0)   # 若 key 不存在，回傳預設值 0
dic[a] = dic.get(a, 0) + 1 # get()常用於統計計數
# 若 a 已存在 → 值 +1
# 若 a 不存在 → 初始化為 1

# 新增
dic["x"] = 10

# 更新
dic["a"] = 100
dic.update({"b": 20, "c": 30}) # 批次更新多個 key

# 刪除
dic.pop("a")      # 刪除 key="a"，並回傳對應的值
dic.popitem()     # 隨機刪除最後插入的項目 (Python 3.7+)
del dic["b"]      # 直接刪除 key="b"
dic.clear()       # 清空整個字典

# 走訪
for key, value in dic.items(): print(key, "→", value) # 同時取出 key 和 value
for key in dic.keys(): print(key) # 只取 key
for value in dic.values(): print(value) # 只取 value

# 判斷存在與長度
"a" in dic        # True / False
len(dic)          # 回傳鍵值對數量

# 排序
dic = {"b": 2, "a": 5, "c": 1}
sorted_key1 = sorted(dic.items()) # 照key排序 # 生成list of tuple # [('a', 5), ('b', 2), ('c', 1)]
sorted_key2 = dict(sorted(dic.items()))  # {'a': 5, 'b': 2, 'c': 1}
sorted_value1 = sorted(dic.items(), key=lambda x: x[1])  # 依value排序 # [('b', 2), ('a', 5), ('c', 1)]
sorted_value2 = dict(sorted(dic.items(), key=lambda x: x[1])) # {'b': 2, 'a': 5, 'c': 1}
sorted_value3 = dict(sorted(dic.items(), key=lambda x: x[1], reverse=True)) # 依value由大到小排序

# 只取最大或最小的 key/value
max_key = max(dic, key=dic.get)   # 回傳 value 最大的 key
min_key = min(dic, key=dic.get)   # 回傳 value 最小的 key

# dict → list
list_of_keys = list(dic.keys())
list_of_values = list(dic.values())
list_of_items = list(dic.items())

# list → dict
pairs = [("x", 1), ("y", 2)]
dic = dict(pairs)

# 字典合併
dic1 = {"a": 1, "b": 2}
dic2 = {"b": 3, "c": 4}

# Python 3.9+
dic3 = dic1 | dic2   # {'a': 1, 'b': 3, 'c': 4}

# 傳統寫法
dic1.update(dic2)

# 將列表轉換成字典
nums = [1, 2, 3]
dic = {x: x**2 for x in nums}  # {1: 1, 2: 4, 3: 9}

# 篩選字典中的條件項
dic = {"a": 5, "b": 2, "c": 9}
filtered = {k: v for k, v in dic.items() if v > 3}  # {'a':5, 'c':9}

# 應用例子：統計出現次數
s = "banana"
count = {}
for c in s:
    count[c] = count.get(c, 0) + 1
print(count)  # {'b': 1, 'a': 3, 'n': 2}
```
```python
from collections import defaultdict

# 建立一個字典，如果你使用不存在的 key，它會自動新增該 key，
# 並且把 value 初始化成「空的 list []」。
anagrams = defaultdict(list)

# 如果 sorted_str 這個 key 已存在 → 把 s 加進對應的 list。
# 如果 sorted_str 這個 key 不存在 → defaultdict 會自動生成：
#    anagrams[sorted_str] = []
# 然後再 append(s)。
anagrams[sorted_str].append(s)
```
```cpp
// C++ 語法
// 需要 #include <map> 或 #include <unordered_map>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 宣告
    map<string, int> dic1;                // 有序字典
    unordered_map<string, int> dic2;      // 無序 hash table
    dic1["a"] = 5;
    dic2["b"] = 2;

    // 存取元素
    int v = dic1["a"];                    // 若 key 不存在，map 會自動插入預設值 0
    if (dic2.find("c") != dic2.end())     // 判斷是否存在
        cout << dic2["c"];

    // 插入 / 更新
    dic1["x"] = 10;                       // 新增或更新
    dic1.insert({"y", 20});               // 僅插入不存在的 key
    dic1["a"] = 100;                      // 更新已有 key

    // 刪除元素
    dic1.erase("a");                       // 刪除 key="a"
    dic1.clear();                          // 清空整個 map

    // 走訪
    for (auto& [k,v] : dic1)              // C++17 structured binding
        cout << k << " -> " << v << endl;

    for (auto it = dic2.begin(); it != dic2.end(); ++it)
        cout << it->first << " -> " << it->second << endl;

    // 判斷長度
    cout << dic1.size() << endl;

    // 排序
    // map 本身是 key 自動排序的
    // unordered_map 若要排序可以轉成 vector<pair>
    vector<pair<string,int>> vec(dic2.begin(), dic2.end());
    sort(vec.begin(), vec.end(), [](auto &a, auto &b){ return a.second < b.second; }); // 依 value 排序

    // 最大最小 key/value
    auto max_it = max_element(dic2.begin(), dic2.end(),
                              [](auto &a, auto &b){ return a.second < b.second; });

    // 字典推導式類似用 loop 建立
    vector<int> nums = {1,2,3};
    map<int,int> squared;
    for (int x: nums) squared[x] = x*x;

    // 統計出現次數
    string s = "banana";
    map<char,int> count;
    for (char c : s) count[c]++;          // 若不存在自動初始化為 0

    return 0;
}
```

### Python：set
* `Python` 的 `dict`、`set` 都是用 `Hash Table`實作
*  `Hash Table`的輸入%某值直接找這個key是否存在，查找效率為O(1)
*  `set`是`dict`只有key沒有value
```python
# list
my_list = [1, 2, 3, 4]
my_list.append(5)  # 添加元素
print(my_list[2])  # 使用索引訪問，輸出 3

# array
import array
my_array = array.array('i', [1, 2, 3, 4])  # 整數類型的 array
my_array.append(5)
print(my_array[2])  # 使用索引訪問，輸出 3

# set
my_set = {1, 2, 3, 4}
my_set.add(5)  # 添加元素 # 只有 set 是用 add
print(3 in my_set)  # 判斷元素是否存在，輸出 True
```

![016](https://hackmd.io/_uploads/ry_P_Nmdxl.png =75%x)

# 容器：Linked List
## Linked List 鏈結串列
- 各個節點記錄當下的值跟下一個值(引用指標)，它們的記憶體位址無須連續，尾節點指向空
- 在 C、C++、Go 和 Rust 等支持指標的語言中，上述引用應被替換為指標
- 插入節點，改變兩個節點的引用(指標)
- 刪除節點，改變一個節點的引用(指標)

| ![016](https://hackmd.io/_uploads/r170I4X_ge.png)| ![016](https://hackmd.io/_uploads/rktFDVQulg.png) |
| --- | --- |
| ![016](https://hackmd.io/_uploads/HyyqDNX_el.png) | ![016](https://hackmd.io/_uploads/r1TswNQdex.png) |

用python的class定義Linked List的結構
```python
class ListNode:
    def __init__(self, val):
        self.data = val
        self.next = None   # 建立時，先預設沒有下一個節點

n3 = ListNode(3)
n2 = ListNode(2)
n1 = ListNode(1)
n1.next = n2   # 之後再手動指定
n2.next = n3
head = n1 # 也可以直接用n1但會有點亂

# 定義節點 (Node)
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # 節點存放的數值
        self.next = next    # 自定義.next跟自定義.age是一樣的意思

node3 = ListNode(3)              # 3 -> None
node2 = ListNode(2, node3)       # 2 -> 3 -> None
node1 = ListNode(1, node2)       # 1 -> 2 -> 3 -> None
head = node1   # head 指向整條 Linked List 的開頭

# 等同以下 # 每個ListNode都包含下一個ListNode函式
head = ListNode(1, ListNode(2, ListNode(3, None)))

# 直線形無法建立cycle
head = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)

head.next = node2
node2.next = node3
node3.next = node4
node4.next = node2   # 這裡建立 cycle，讓 -4 指回 2
```

![009](https://hackmd.io/_uploads/ryAuT9Iogg.png =60%x)

```python
# 遍歷 (Traversal)
current = head
while current:
    print(current.val)
    current = current.next

# 插入節點 2 -> 3, 2 -> 4 -> 3
node4 = ListNode(4)
node4.next = node3
node2.next = node4

# 刪除節點 1 -> 2 -> 3, 1 -> 3
node1.next = node2.next

# 快慢指標 (Floyd’s Tortoise & Hare)
slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
```
### Leetcode常見用法
- C 只要建立一個新的linklist的node就要用一次malloc
```c
struct ListNode {
    int val;
    struct ListNode *next;
};

// main
struct ListNode *aaa = malloc(sizeof(struct ListNode)); 
// 宣告指標一定要用malloc去heap建立空間
// 只要建立一個新的linklist的node就要用一次malloc
aaa->val = 5;
aaa->next = NULL;
head->next = aaa;
```
- linklist的輸出就是一個點，每個點都有`next`所以會無限延伸
- 設定變數就是一直在縮小範圍，變數很多，沒有好的命名方法
```c
struct ListNode* func(struct ListNode* head) {
    struct ListNode dummy; // 建立stack的假頭
    dummy.val = 0;
    dummy.next = head;

    struct ListNode* prev = &dummy; // 增加變數  // 接下來實際操作點 // 縮小範圍
    prev = prev->next; // 移動

    struct ListNode* cur = prev->next; // 增加變數  // 接下來實際操作點 // 縮小範圍
    struct ListNode* tail = cur; // 記錄點
    cur = cur->next; // 移動

    struct ListNode* newNode = cur; // 增加變數  // 接下來實際操作點 // 縮小範圍
    // 做很多指標修改（反轉 / 插入 / 重接）
    // ...

    return dummy.next;
}
```
|![image](https://hackmd.io/_uploads/HkbXi4fwWx.png)|![image](https://hackmd.io/_uploads/S1ZaiNMwWg.png)|
|-|-|

### C: linklist insert
```c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;  //  C++可以直接寫 Node *next;  // C此時typedef還沒生效
} Node;

// 指定位子插入  // 沒有講是stack的往前插入還是quene的往後插入
// 用Node **head 因為可能改到指標head的value且func是用void宣告
void insert(Node **head, int value, int pos) { // [0, 1, 2, 3], value = 7, pos = 3
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (pos == 0 || *head == NULL) {
        // 插入頭部
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node *current = *head;
    // 用迴圈定位，同array[pos], current = 2
    for (int i = 0; i < pos - 1 && current->next != NULL; i++) 
        current = current->next; // 遍歷常用 current = cuttern->next

    newNode->next = current->next; // 2 ->3, 7 ->3
    current->next = newNode; // 2 ->7 ->3
}
```
### C linklist add delete search
```c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* addNode(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 在heap建立新地址
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
    } else {
        Node* current = head;
        while (current->next != NULL) { // 用迴圈定位，同array[-1]
            current = current->next;
        }
        current->next = newNode;
    }

    return head;
}

Node* deleteNode(Node* head, int data) {
    if (head == NULL) return NULL;
    
    // 如果要刪掉的data是head
    if  (head->data == data){
        Node* temp = head;
        head = head ->next;
        free(temp);
        return head;
    }
    
    Node* current = head;
    // 如果下一個data不是我要刪的我就繼續往前走
    while (current->next != NULL && current->next->data!=data){
        current = current->next;
    }
    // 把current的下一個data刪掉
    if (current->next!=NULL){
        Node* temp = current->next;
        current->next=current->next->next;
        free(temp);
    }
    
    return head;
}

void searchNode(Node* head, int data) {
    Node *current = head;
    while(current != NULL){
        if(current->data == data) return;
        current = current->next;
    }
}

void displayList(Node* head) {
    Node* current = head;

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    Node* head = NULL; // 創建在stack上
    // heap建立在main的stack，後面的node都建立在heap

    head = addNode(head, 1); // addNode沒有修改head本身，藉由return回傳地址
    head = addNode(head, 2);
    head = addNode(head, 3);
    head = addNode(head, 4);

    printf("鏈結串列目前的資料：");
    displayList(head);

    head = deleteNode(head, 3);
    head = deleteNode(head, 1);
    head = deleteNode(head, 4);

    printf("刪除節點後的鏈結串列：");
    displayList(head);

    // 搜尋節點
    searchNode(head, 2);
    searchNode(head, 5);

    return 0;
}
```

### C++ 單向 Linked List 反轉，不能使用任何額外記憶體
```cpp
struct Node {
    int val;
    Node* next; 
};

Node* reverseList(Node* head) {
    Node* prev = nullptr; // 第一個點的next是nullptr
    Node* cur = head;    // n1 ->n2 ->n3 ->nullptr
    Node* next;
    while (cur != nullptr) {
        next = cur->next;  // 先存下一個要處理的點
        cur->next = prev;  // 反轉
        prev = cur;        // prev推進
        cur = next;        // cur推進
    }
    return prev;  // 新 head
}
```
![image](https://hackmd.io/_uploads/HyxKyHGDZe.png =70%x)
### C++ 雙向 Linked List 反轉，不能使用額外記憶體
```cpp
struct DNode {
    int val;
    DNode* next;
    DNode* prev;
};

DNode* reverseDList(DNode* head) {
    DNode* cur = head;
    DNode* tmp = nullptr;
    while (cur != nullptr) {
        // DNode.prev跟DNode.next交換
        tmp = cur->prev;
        cur->prev = cur->next;
        cur->next = tmp;
        
        cur = cur->prev;  // cur推進，prev 等效原本 next
    }
    if (tmp != nullptr)
        head = tmp->prev;  // 新 head
    return head;
}
```

## Stack 堆疊
資料進出規則，先入後出，LIFO(last in first out)
先入後出，如桌面上的一疊盤子，如果想取出底部的盤子，則需要先將上面的盤子依次移走
| ![016](https://hackmd.io/_uploads/HkSucNmdeg.png) | ![016](https://hackmd.io/_uploads/HJYO9NXOel.png) |
| --- | --- |

### C array Stack
```c
#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int top;
} Stack;

// 初始化
void init(Stack *s) {
    s->top = -1;
}

// push
int push(Stack *s, int value) {
    if (s->top >= MAX - 1) return 0;  // overflow
    s->data[++(s->top)] = value;
    return 1;
}

// pop
int pop(Stack *s, int *value) {
    if (s->top < 0) return 0;  // underflow
    *value = s->data[(s->top)--];
    return 1;
}

// peek
int peek(Stack *s, int *value) {
    if (s->top < 0) return 0;
    *value = s->data[s->top];
    return 1;
}
```
### C++ Linked List 實作 Stack 大量註解
```cpp
#include <iostream>
using namespace std;

struct Node // struct := class, struct public, class private
{
    int data;
    Node* next;
    // self.next = None
    // *是c++指標的寫法
    // Node*跟int一樣是一種宣告
    // 為什麼Node裡面可以用Node*宣告?
    // 因為Node*就是指Node的地址，宣告next是某個Node的地址
    // n1(房間A) ->n2(房間B) ->n3(房間C)，這個next紀錄下一個Node*的地址
    
    Node(int val) : data(val), next(nullptr) {} 
    // 建構子(constructor) = 宣告新的struct、class的行為
    // 同 Node(int val) { data = val; next = nullptr; }
};

class Stack 
{
private:  // 不讓使用者修改
    Node* top; 
    // 指標，指向目前的最上面節點
    // 有點像python宣告這個class有top這個類別
    // 如果不用指標的話，Stack內的函式只要return一次整個top變數就會消失，參考c++記憶體區域

public:
    Stack() : top(nullptr) {} 
    // 初始化時把 top 設成空指標
    // 宣告新的struct、class的行為

    void push(int val) // push 入Stack：新增一個節點放到Stack頂
    {
        Node* newNode = new Node(val);  
        // new是增加記憶體
        // Node*的功能同int，Node*作為宣告的意思是說，存的是這個房間的號碼
        // n1(房間A) ->n2(房間B) ->n3(房間C)
        // Node* newNode = new Node(n1);
        // newNode 是房間A、newNode->val 是n1、newNode->next 是房間B
        
        newNode->next = top; 
        // 新節點的 next 指向原本的 top  
        // newNode->next是newNode.next
        top = newNode; // 更新 top，讓新節點變成Stack頂
    }

    void pop() // pop 出Stack：移除Stack頂
    {
        if (top == nullptr) 
        {
            cout << "Stack is empty\n";
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp; // 釋放掉原本的記憶體
    }

    int peek() 
    {
        if (top == nullptr) 
        {
            cout << "Stack is empty\n";
            return -1;
        }
        return top->data;
    }

    bool isEmpty() 
    {
        return top == nullptr;          // 如果 top 是空指標，就代表棧是空的
    }
};

int main() 
{
    Stack st; // 建立一個 Stack 物件 st (此時 top=nullptr)
    // 本身不會佔空間，是裡面的Node佔空間，不用* new等

    st.push(10); // 把 10 放進棧 -> top 指向節點(10)
    st.push(20); // 把 20 放進棧 -> top 指向節點(20)，next 指向節點(10)

    cout << st.peek() << endl; // 輸出棧頂值：20
    st.pop(); // 移除棧頂 (刪除節點 20，top 變成指向節點 10)
    cout << st.peek() << endl; // 輸出棧頂值：10
}
```

### C++ Linked list 實作Stack、Queue
```cpp
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class Stack // class Queue
{
private:
    Node* top; 
    /*
    Node* front;
    Node* rear;
    */
    
public:
    Stack() : top(nullptr) {} 
  //Queue() : front(nullptr), rear(nullptr) {}
    
    void push(int val)
    {
        Node* newNode = new Node(val);  
        newNode->next = top; // stack，往前堆，原本的top放到新的後面
        top = newNode;
        
        /*
        Node* newNode = new Node(val);
        
        if (rear == nullptr) {  // 輸入比stack多一個檢查
            front = rear = newNode;
            return;
        }
        
        rear->next = newNode;  // queue往後堆，新的放到原本的後面
        rear = newNode;
         */
    }

    void pop()
    {
        if (top == nullptr) 
        {
            cout << "Stack is empty\n";
            return;
        }
        Node* temp = top;  // 拿出去stack跟queue一樣，都是從前面拿
        top = top->next;
        delete temp;
        
        /*
        if (front == nullptr) 
        {
            cout << "Queue is empty\n";
            return;
        }
        Node* temp = front;
        front = front->next;
        if (front == nullptr) // 多一個檢查，拿完可能剛好是空的
            rear = nullptr;
        delete temp;
        */
    }

    int peek() 
    {
        if (top == nullptr) 
        {
            cout << "Stack is empty\n";
            return -1;
        }
        return top->data;
        
        /*
        if (front == nullptr) 
    {
            return -1;
        return front->data;
    }
        */
    }

    bool isEmpty() 
    {
        return top == nullptr;
    }
};
```

## Queue 隊列
資料進出規則，先進先出，FIFO(first in first out)，資料只能朝同一個方向走
| ![016](https://hackmd.io/_uploads/ry53qNm_xe.png) | ![016](https://hackmd.io/_uploads/Sy0n54Qdxl.png) |
| --- | --- |

### C array Queue
```c
#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int front;
    int rear;
    int size;
} Queue;

// 初始化
void init(Queue *q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

// enqueue
int enqueue(Queue *q, int value) {
    if (q->size >= MAX) return 0; // full
    q->rear = (q->rear + 1) % MAX;
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

// dequeue
int dequeue(Queue *q, int *value) {
    if (q->size == 0) return 0; // empty
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX;
    q->size--;
    return 1;
}

// peek
int peek(Queue *q, int *value) {
    if (q->size == 0) return 0;
    *value = q->data[q->front];
    return 1;
}
```

### Double-ended queue 雙向佇列：List為主，資料進出規則，用在BFS
| ![016](https://hackmd.io/_uploads/S1rGoNQull.png) | ![016](https://hackmd.io/_uploads/ryKGoVmOge.png) |
| --- | --- |

```python
from collections import deque

queue = deque()    # 建立一個空的雙端佇列

# 放入元素
queue.append((0, 0))    # 往右端加入
queue.append((1, 2))

# 取出元素
r, c = queue.popleft()  # 從左端拿出
print(r, c)             # 0 0  # (r, c)是座標

# 還可以從左端加入
queue.appendleft((-1, -1))
r, c = queue.popleft()  # 取左端元素
print(r, c)             # -1 -1
```

```python
from collections import deque

# 範例矩陣 (Grid)
grid = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
    [1, 0, 1, 0]
]

rows, cols = len(grid), len(grid[0])
visited = set()  # 記錄已拜訪的座標
queue = deque()

# 假設 BFS 從 (0, 0) 起點開始
start = (0, 0)
queue.append(start)

while queue:
    r, c = queue.popleft()  # 從隊列左端取出
    if (r, c) not in visited:
        visited.add((r, c))
        print("拜訪座標:", (r, c), "值:", grid[r][c])
        
        # 上下左右四個鄰居
        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            nr, nc = r + dr, c + dc
            # 邊界檢查
            if 0 <= nr < rows and 0 <= nc < cols:
                queue.append((nr, nc))
```
# 容器：Tree & Graph
>樹是一種圖
## `from collections import defaultdict`用在dict、tree、grahp
```python
from collections import defaultdict
# dict（一般字典初始化）
# 情境：要統計每個元素出現次數 → 使用 defaultdict(int)
count = defaultdict(int) # 自動將不存在的 key 初始化為 0

nums = [1, 1, 2, 3, 3, 3]

for x in nums:
    count[x] += 1   # 不需要先檢查 key 是否存在

print("字典計數結果:", dict(count)) # 輸出: {1: 2, 2: 1, 3: 3}

# 樹（Tree）
# 情境：用 parent -> children 方式建樹時 → defaultdict(list)
tree = defaultdict(list) # 樹的 children list 自動初始化為 []

edges = [
    (1, 2),
    (1, 3),
    (2, 4),
    (2, 5),
]

# 建立一棵樹（1 為根）
for parent, child in edges:
    tree[parent].append(child)

print("樹的 children 表示法:", dict(tree)) # 輸出: {1: [2, 3], 2: [4, 5]}

# 圖（Graph）
# 情境：用 adjacency list 建無向圖 → defaultdict(list)
graph = defaultdict(list)

edges = [
    (1, 2),
    (2, 3),
    (1, 3),
    (3, 4),
]

# 無向圖：雙向 append
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

print("圖的 adjacency list:", dict(graph)) # 輸出: {1: [2, 3], 2: [1, 3], 3: [2, 1, 4], 4: [3]}

'''
小總結：
defaultdict(int)   → 為不存在的 key 自動建立 0（做計數）
defaultdict(list) → 為不存在的 key 自動建立 []（建樹、建圖）
'''
```
## Binary Tree 二元樹
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 建立範例二元樹
node4 = TreeNode(4)
node5 = TreeNode(5)
node2 = TreeNode(2, node4, node5)
node3 = TreeNode(3)
root = TreeNode(1, node2, node3)
```

```python
# 遍歷 (Traversal)
def preorder(node):
    if not node:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

# 搜尋 (Search)、插入 / 刪除
# DFS 或 BFS

# 樹的高度 / 最大深度
def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# 判斷是否對稱 / 完全二元樹

# 路徑相關操作
```

### Binary Tree 二元樹 說明
> 一種非線性資料結構，每個節點最多有兩個子節點（左子節點、右子節點），根節點在最上層，葉節點在最下層。
> 
> 平均情況下的查找、插入、刪除 **時間複雜度：O(log n)**；但如果退化成鏈結串列，會變成 **O(n)**。
> 
> Binary Tree 和 Binary Search Tree (BST) 最大的差異在於有沒有排序規則
> Binary Search Tree (BST) 必須：
> 左子樹所有值 <父節點
> 右子樹所有值 >父節點

名詞
| ![016](https://hackmd.io/_uploads/SypTK7wdxx.png) | ![016](https://hackmd.io/_uploads/H1m-cXD_eg.png) |
| --- | --- |

| 名詞                  | 說明                      |
| ------------------- | ----------------------- |
| 根節點 (root)          | 位於樹頂，沒有父節點              |
| 葉節點 (leaf)          | 沒有子節點，左右指標均為 `None`     |
| 邊 (edge)            | 節點與節點之間的連線              |
| 層 (level)           | 從上到下計數，根節點在第 1 層        |
| 節點的度 (degree)       | 子節點數量，二元樹中度 ∈ {0, 1, 2} |
| 樹的高度 (tree height)  | 根到最遠葉節點的邊數              |
| 節點的深度 (depth)       | 根到該節點的邊數                |
| 節點的高度 (node height) | 該節點到最遠葉節點的邊數            |

#### 插入與刪除
* 插入與鏈結串列類似，透過修改指標完成。
  * 1. 插入：根據數值大小，遞迴找到空位後插入。
  * 2. 刪除：
     * 無子節點 → 直接刪除。
     * 只有一個子節點 → 用子節點替代該節點。
     * 兩個子節點 → 找到右子樹的最小值（或左子樹的最大值）替換該節點，再刪除該替代節點。

![051](https://hackmd.io/_uploads/HJXlomDdlg.png =75%x)

#### 二元樹種類
| 種類               | 說明                               |
| ---------------- | -------------------------------- |
| 完美二元樹 (Perfect)  | 每層節點都填滿，高度 h → 節點數 = `2^(h+1)-1` |
| 完全二元樹 (Complete) | 除最後一層外，其餘層填滿；最後一層節點靠左            |
| 滿二元樹 (Full)      | 每個節點的度要麼是 0，要麼是 2                |
| 平衡二元樹 (Balanced) | 任意節點左右子樹高度差 ≤ 1                  |
| 退化樹 (Degenerate) | 每個節點只有一個子節點，退化成鏈結串列              |

| ![052](https://hackmd.io/_uploads/r1X7jXPdeg.png)    | ![053](https://hackmd.io/_uploads/rypXomD_gl.png =75%x) |
| -- | -- |
| ![054](https://hackmd.io/_uploads/H1Z827Puxl.png =85%x) | ![055](https://hackmd.io/_uploads/HkBUhXPOxx.png)       |

#### 陣列表示法
| 完美二元樹轉陣列   | 完全二元樹轉陣列 |
|----------------|--------------|
| ![061](https://hackmd.io/_uploads/SJXDEVwdge.png)| ![062](https://hackmd.io/_uploads/SyCwNVvOlg.png)|

| 任意二元樹轉陣列 |  |
|-------------------|-------------------|
| ![063](https://hackmd.io/_uploads/rJvYNEwulg.png =75%x)|  ![064](https://hackmd.io/_uploads/BJiFENDOlx.png)|

## Binary Search Tree (BST) 二元搜尋樹
在一個二元搜尋樹 (BST) 中，給定一個節點鍵值 `value`，請寫一個函數 `int findPosition(Node *root, int value)`，回傳該節點在 **中序遍歷** 中的位置（從 1 開始計數）。

條件：
1. `Node` 結構中包含 `parent` 指標，可以往回走到父節點。
2. 函數只能利用 `parent` 和 `left/right` 指標，不額外建立陣列或 list。
3. 若節點不存在，回傳 -1。

```cpp
#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* parent;  // 指向父節點
};

// 找 BST 中某個節點的中序追蹤位置
int findPosition(Node* root, int value) {
    Node* cur = root;
    Node* target = nullptr;

    // 1. 先找到 value 的節點
    while (cur != nullptr) {
        if (cur->val == value) {
            target = cur;
            break;
        } else if (value < cur->val) {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
    }

    if (!target) return -1;  // 沒找到

    // 2. 往左走到最左下，計算左子樹大小
    int count = 0;
    Node* node = target;

    // 往回走，使用 parent 計算中序位置
    while (node) {
        // 如果 node 是 parent 的右子節點，累加左子樹大小 + 1
        if (node->parent && node->parent->right == node) {
            Node* leftSub = node->parent->left;
            int leftCount = 0;
            if (leftSub) {
                // 計算 leftSub 節點的大小
                Node* tmp = leftSub;
                // 中序遍歷計數 leftSub 節點數量
                // 簡單遞迴計算節點數
                function<int(Node*)> size = [&](Node* n) {
                    if (!n) return 0;
                    return size(n->left) + 1 + size(n->right);
                };
                leftCount = size(leftSub);
            }
            count += leftCount + 1;
        }
        node = node->parent;
    }

    // 再加上左子樹大小 + 1 (target 本身)
    function<int(Node*)> leftSize = [&](Node* n) {
        if (!n) return 0;
        return leftSize(n->left) + 1 + leftSize(n->right);
    };
    count += leftSize(target->left) + 1;

    return count;  // 中序位置
}
```
### Binary Search Tree (BST) 二元搜尋樹 英文解說
#### 定義 (Definition)
Binary search tree follows all properties [ˋprɑpɚtɪs] of binary tree, and:
- Its left child contains values [ˋvæljʊz] less than the parent node.
- Its right child contains values greater than the parent node.

#### 性質 (Properties)
Binary Tree 和 Binary Search Tree (BST) 最大的差異在於有沒有排序規則
搜尋（search）、插入（insertion）、刪除（deletion）的時間複雜度在平均情況下為 **O(log n)**。
1. For the root node, all values in the left subtree < root node's value < all values in the right subtree
   對於根節點，左子樹中所有節點的值 < 根節點的值 < 右子樹中所有節點的值
2. The left and right subtrees of any node are also binary search trees
   任意節點的左、右子樹也是二元搜尋樹

#### Insert（插入）
- Compare X with the root node
- Compare X with the left or right child of the root node 
- Continue comparing X with left/right children
- Until reaching a leaf, then insert to the left or right accordingly

| ![066](https://hackmd.io/_uploads/By0YeXO_gx.png) | ![067](https://hackmd.io/_uploads/BJRtxQuuxg.png) |
| --- | --- |
| ![068](https://hackmd.io/_uploads/Hy0FlQuOge.png) | ![069](https://hackmd.io/_uploads/H1Atg7dOgl.png) |
| ![070](https://hackmd.io/_uploads/SyRYe7_ugx.png) |   |

#### Search（搜尋）
- Compare X with the root node
- Compare X with left/right child of the root node
- Continue comparing with left/right children
- If found X, return X; if reached leaf without finding, return NULL

Example:
Starting from root 8, ignore the black 6 in picture 2,
since 6 < 8, go to the left subtree of 8;
since 6 > 3, go to the right subtree of 3;
finally, find 6.

| ![071](https://hackmd.io/_uploads/BJ9x-QOOlx.png) | ![072](https://hackmd.io/_uploads/rJigbQuOge.png) |
| --- | --- |
| ![073](https://hackmd.io/_uploads/SJcgZ7u_gl.png) | ![074](https://hackmd.io/_uploads/Bkqlb7uOge.png) |

#### Delete（刪除）
- Case 1: Delete a leaf node directly
- Case 2: Delete a node with a single child
  - Exchange the node to be deleted with its child, then delete
- Case 3: Delete a node with two children
- Case 2 & Case 3:
  - 要刪的節點一直往右下、往左下、往右下、往左下…直到葉節點(最底)，交換後再刪除，
  - Case 3的50右下是70再左下是60，所以50跟60交換後刪除

| ![075](https://hackmd.io/_uploads/HJ44b7uuel.png) | ![076](https://hackmd.io/_uploads/H14EZXduxx.png) |
| --- | --- |
| ![077](https://hackmd.io/_uploads/Sk4EWmddee.png) |  |

### Binary Search 二元搜尋
```c
int binary_search(unsigned int *arr, int left, int right, int target)
{
    while (left <= right)
    {
        int mid = left + (right - l) / 2;
        if (arr[mid] == target)
            return 1;  // TRUE
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return 0;  // FALSE
}

int binary_search(unsigned int *arr, int left, int right, int target)
{
    if (left > right)
        return 0;  // FALSE

    int mid = left + (right - l) / 2;

    if (arr[mid] == target)
        return 1;  // TRUE
    else if (arr[mid] < target)
        return binary_search_recursive(arr, mid + 1, right, target);
    else
        return binary_search_recursive(arr, left, mid - 1, target);
}
```

### Red-Black Tree 紅黑樹 說明
如果一棵二元搜尋樹（BST）不平衡，像極端情況變成 鏈狀結構，
紅黑樹透過幾個顏色與結構規則，讓樹保持接近平衡（不是完全平衡，但足夠接近）。
它的平衡保證：
從根到任一葉節點的最長路徑 ≤ 最短路徑的 2 倍，
這意味著搜尋路徑的長度上限被控制住了 → 時間複雜度保證 O(log n)，
如果你插入節點順序是 1 → 2 → 3 → 4，普通二元搜尋樹會變成這樣（嚴重不平衡）：

```
  1
   \
    2
     \
      3
       \
        4
```

紅黑樹會在每次插入後**變色與旋轉**，避免變成鏈狀：
```
只有一個節點，直接設為黑色（根節點規則）
  1(B)

2 插到右邊，父節點黑色，無需調整
  1(B)
     \
      2(R)

3 是紅色，父節點 2 也是紅色 → 違反「紅節點不可相鄰」
叔叔節點不存在（視為黑色） → **左旋+變色**
    2(B)
   /   \
  1(R)  3(R)

插到 3 的右邊，父 3 是紅色 → 違反紅紅規則
叔叔節點 1 也是紅色 → 父叔變黑，祖父變紅
根節點變紅後，因為是根 → 再變回黑色
    2(B)
   /   \
  1(B)  3(B)
           \
            4(R)
```
結果：路徑長度差不超過 2 倍，樹高度保持在 **log n** 級別。
而原本 BST 的鏈狀高度是 n，搜尋效率差很多。

## Heap 堆積
- `Heap`是一種`Tree`
```python
import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heap)   # [1, 3, 5] # 預設小頂堆積
print(heapq.heappop(heap))  # 1 (最小的被拿出來)

heap = [1, 3, 5, 7, 9]
heap[3] = 7 # 因為(3-1)//2 = 1，heap[1] => 3，3的左子節點 
heap[4] = 9 # 因為(4-1)//2 = 1，heap[1] => 3，3的右子節點
```
| 節點 | 左子節點    | 右子節點    | 父節點      |
| -- | ------- | ------- | -------- |
| i  | 2*i + 1 | 2*i + 2 | (i-1)//2 |

![image](https://hackmd.io/_uploads/H1W6JpM0ll.png =60%x)

### Heap 堆積說明
是一種特定條件的完全二元樹，有分小頂堆積、大頂堆積。
對於大頂堆積（小頂堆積），堆積頂元素（根節點）的值是最大（最小）的

名詞：堆積頂、堆積底
- 大頂堆積 (max heap)：任意節點的值 ≥ 其子節點的值
- 小頂堆積 (min heap)：任意節點的值 ≤ 其子節點的值

![027](https://hackmd.io/_uploads/HksQNzDdxe.png =75%x)

完全二元樹非常適合用陣列來表示，任意節點與其左子節點、右子節點、父節點的關係皆相同。
![028](https://hackmd.io/_uploads/HJjE4MPdlx.png =75%x)

#### 元素入堆積
很像二元搜尋樹，但堆積的規則是節點一定要都大於或都小於子節點
以大頂堆積為例，因為是完全二元樹，從最後一個位子插入，一直跟自己的父節點比，若自己較大就交換。

#### 堆積頂元素出堆積
直接跟最後一個元素交換後刪除。
以大頂堆積為例，接著頂元素一直跟子節點比，與最大的子節點交換。

#### 串列建立成堆積的方法
##### 方法 1：用入堆積實現
建立一個空堆積，再對每個元素做入堆積操作。
- `n` 個元素，每個元素最多花 `log(n)` 時間
- 時間複雜度：`O(n log n)`
- ps. 分成兩個子節點，時間都會是 `log(n)`

##### 方法 2：用訪問實現
不整理串列，直接將所有元素依序放進完全二元樹中，依次對每個 **非葉節點** 執行 **從頂至底堆積化**。

需要堆積化的節點是 `(n-1)/2`，時間是 `log(n)`，看似時間複雜度是 `O(n log n)`，但這個算法計算錯了，因為較低層的節點數量遠大於較高層的節點數量，所以需要重新計算。
![029](https://hackmd.io/_uploads/B1DfHzPuxl.png =75%x)

複雜度分析（以完美二元樹為例）：
時間複雜度
T(h) = 每層節點數量 × 該層高度
T(h) = (2^0)(h-0) + (2^1)(h-1) + … + (2^(h-1))(1)

經過計算後：
T(h) = 2^(h+1) - h - 2 = O(2^h)
其中 `n = 2^(h+1) - 1` 所以 `T(h) = O(n)`

#### Top-K 問題
問題：給定一個長度為 `n` 的無序陣列 `nums`，請返回陣列中最大的 `k` 個元素。

##### Top-K 方法 1：走訪方法
- 複雜度：`O(nk)`
- 若 `k` 接近 `n`，則變成 `O(n^2)`
- 類似 Selection Sort

![030](https://hackmd.io/_uploads/BkZ98GDueg.png =55%x)

##### Top-K 方法 2：HeapSort
- 依序把最大的元素出堆積，依次記錄出堆積元素，即可得到從大到小排序的序列
- 複雜度：`O(n log n)`
- 缺點：會超額完成任務（因為會全部排序）

![031](https://hackmd.io/_uploads/rkAsUGvdlg.png =55%x)

##### Top-K 方法 3：堆積法
1. 先將陣列的前 `k` 個元素初始化成一個 **小頂堆積**（堆頂元素最小）。
2. 從第 `k+1` 個元素開始：
   - 若當前元素大於堆頂元素，則：
     - 將堆頂元素出堆積
     - 將當前元素入堆積
3. 走訪完成後，堆積中儲存的就是最大的 `k` 個元素。

參考檔案：`ch8/top-k.py`
| <img src="https://hackmd.io/_uploads/SkNCUfw_lx.png" height="200"> | <img src="https://hackmd.io/_uploads/H1OAIzvdgg.png" height="200"> |
| --- | --- |

## Graph 圖 實現方式：Grid、dict (adjacency list)
```python
# 用grid模擬畫圖
grid = [
  [1, 1, 0, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 1],
  [1, 0, 1, 0]
]

# 用dict模擬畫圖
graph = {
    (0,0): [(0,1),(1,0)],
    (0,1): [(0,0)],
    (1,0): [(0,0)],
    (1,3): [],
    (2,2): [(2,3),(3,2)],
    (2,3): [(2,2)],
    (3,2): [(2,2)]
}

'''
(0,0) ─ (0,1)
   │
 (1,0)

(1,3)

(2,2) ─ (2,3)
   │
 (3,2)
'''
```
```python
# 一般的dict
d = {}
d["a"] = 1
print(d["a"])   # 1
print(d["b"])   # ❌ KeyError，因為 "b" 不存在

# 用collections的dict建立Graph
from collections import defaultdict

graph = defaultdict(dict)

print(graph["a"])   # 自動生成一個空 dict {}
graph["a"]["b"] = 2.0
print(graph)        # {'a': {'b': 2.0}} # 有向圖

graph = {
    "a": {"b": 2.0, "c": 4.0},
    "b": {"a": 0.5}
}
print(graph["a"])          # {'b': 2.0, 'c': 4.0}
print(graph["a"].items())  # dict_items([('b', 2.0), ('c', 4.0)])
```

```python
# DFS 計算連通分量、走迷宮、拓撲排序
# BFS	最短路徑、層序遍歷
# Cycle detection	判斷是否有環	
# Topological sort	DAG、課程安排
# Shortest path	最短距離、最少步數
# MST	加權最小生成樹
```
### Graph 圖 說明
#### 圖的名詞
- 圖 (Graph)：由頂點 (Vertex) 與邊 (Edge) 所構成的資料結構
- 頂點 (Vertex)：圖中的節點
- 邊 (Edge)：連接兩個頂點的線
- 鄰接（adjacency）：與某個頂點相連的其他頂點。例如 A 的鄰接點可能是 B、C
- 路徑（path）：由邊連接起來的頂點序列，例如 A-B-C-D-E
- 度（degree）：
  - 無向圖：與該頂點相連的邊數
  - 有向圖：
    - in-degree：進入該頂點的邊數
    - out-degree：離開該頂點的邊數
- 無向圖（undirected graph）：邊沒有方向
- 有向圖（directed graph）：邊有方向
- 連通圖（connected graph）：圖中任意兩點皆可互相到達
- 非連通圖（disconnected graph）：存在無法到達的點
- 有權圖（weighted graph）：邊帶有權重，常用來表示距離、成本或親密度

#### 圖的表示
將圖 G 抽象表示為：
- 頂點集合 V
- 邊集合 E

例如：
V = {1, 2, 3, 4, 5}
E = {(1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5)}
G = {V, E}
|![034](https://hackmd.io/_uploads/BkvsnfDOel.png)|![035](https://hackmd.io/_uploads/B1Ja3fDuxg.png)|
| --- | --- |

#### 鄰接矩陣（adjacency matrix）
- 原理：以二維矩陣記錄頂點間是否有邊，用 **空間換時間**
- 定義：
  - `M[i, j] = 1` → 表示 `V[i]` 到 `V[j]` 有邊
  - `M[i, j] = 0` → 表示沒有邊
  - 主對角線通常為 0（因為頂點不會連到自己）
![036](https://hackmd.io/_uploads/ryMC2GDOex.png =75%x)

操作複雜度：
- 初始化：`O(n^2)`（建立全 0 矩陣）
- 新增 / 刪除邊：`O(1)`（直接修改對應位置）
- 新增頂點：`O(n)`（新增一列與一行）
- 刪除頂點：`O(n^2)`（移動矩陣資料）

參考程式：`ch9/graph_adjacency_matrix.py`
![037](https://hackmd.io/_uploads/Hysb6fwulg.png  =55%x)
![038](https://hackmd.io/_uploads/Sk1fazwuex.png  =55%x)
![039](https://hackmd.io/_uploads/HJBGaMPulx.png  =55%x)

#### 鄰接表（adjacency list）
- 原理：每個頂點維護一個「鄰接節點列表」，用 **時間換空間**
- 解釋：假設有頂點 A，它的鄰接表可能是 `[B, C, E]`，表示 A 與這三個點相連。
  - 這種方式不會為不存在的邊浪費空間，適合稀疏圖。
  - 初始化時，每個頂點都會有一個空列表，之後依邊資料把對應的節點加進去。

![040](https://hackmd.io/_uploads/r1aXafD_xl.png =55%x)

操作複雜度：
- 初始化：`O(n + m)`（n 為頂點數，m 為邊數）
- 新增邊：`O(1)`（直接在對應列表加節點）
- 刪除邊：`O(m)`（可能需要搜尋整個列表）
- 新增頂點：`O(1)`（新增一個空列表）
- 刪除頂點：`O(n + m)`（需刪除所有與它相關的邊）

參考程式：`ch9/graph_adjacency_list.py`
![041](https://hackmd.io/_uploads/B1KBpGPOll.png =55%x)

# 演算法
## Sort排序，一般排序，comparison-based 兩兩比較，O(n^2)
### Select Sort 
```python
def selection_sort(nums: list[int]):
    n = len(nums)
    # 外迴圈：未排序區間為 [i, n-1]
    for i in range(n - 1):
        # 內迴圈：找到未排序區間內的最小元素
        k = i
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j  # 記錄最小元素的索引
        # 將該最小元素與未排序區間的首個元素交換
        nums[i], nums[k] = nums[k], nums[i]

nums = [4, 1, 3, 1, 5, 2]
selection_sort(nums)
print("選擇排序完成後 nums =", nums)
```
```c
#include <stdio.h>

void selection_sort(int nums[], int n) {
    // 外迴圈：未排序區間為 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        int k = i;  // 假設最小元素的索引是 i

        // 內迴圈：找到未排序區間內的最小元素
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k]) {
                k = j;  // 更新最小元素索引
            }
        }

        // 將該最小元素與未排序區間的首個元素交換
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

int main() {
    int nums[] = {4, 1, 3, 1, 5, 2};
    int n = sizeof(nums) / sizeof(nums[0]); // 計算陣列長度
    selection_sort(nums, n);
    printf("選擇排序完成後 nums = ");
    for (int i = 0; i < n; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");
    return 0;
}
```
- 程式迴圈可視化：nums = [1~10]：`[1~10]`、`[2~10]`、`[3~10]`、…、`[10~10]`
- 程式說明：
  - 最左邊數來第一個數字跟右邊所有數字比大小，把最小的數字跟最左邊數來第一個數字交換，
  - 最左邊數來第二個數字跟右邊所有數字比大小，把最小的數字跟最左邊數來第二個數字交換，
  - 以此類推，依序把最小的數字放到最左邊
- 程式白話文說明：
  - 每一次迴圈中，先用k = j紀錄第幾個值最小，最後才把最小的數字交換到最左邊
![078](https://hackmd.io/_uploads/H15dLmOOlx.png =45%x)

### Bubble Sort 
```python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):#一共比7圈
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:#如果前一個比後一個大，兩個就交換
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
#第一圈兩個兩個比，最右邊為最大值
#第二圈兩個兩個比，右邊數來第二個數字為第二大值，以此類推

# 測試
nums = [4, 1, 3, 1, 5, 2]
sorted_arr = bubble_sort(arr)
print("排序後的陣列:", sorted_arr)
```
```c
void bubble_sort(int arr[], int n) {
    // 外迴圈：總共要比 n 次
    for (int i = 0; i < n; i++) {
        // 內迴圈：兩兩比較，把最大的數「冒泡」到右邊
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交換 arr[j] 與 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 每一圈結束後，右邊第 n-i-1 個位置就已經是當前最大值
    }
}
```
- 程式迴圈可視化：nums = [1~10]：`[1~10]`、`[1~9]`、`[1~8]`、…、`[1~1]`
- 程式說明：
  - 最左邊數來第一個數字依序跟右邊的數字比大小，大的數字放右邊，比到最右邊數來第一個數字，
  - 最左邊數來第一個數字依序跟右邊的數字比大小，大的數字放右邊，比到最右邊數來第二個數字，
  - 以此類推，排序
- 程式白話文說明：依序把大的數字放到最右邊
- 補充：Bubble sort也可以改成小的數字都放左邊，
- select sort每次換數字都是直接到最左邊，bubble是兩兩交換，慢慢換到最右邊

### Insertion Sort 
```python
def insertion_sort(nums: list[int]):
    """插入排序"""
    # 外迴圈：已排序區間為 [0, i-1]
    for i in range(1, len(nums)):
        base = nums[i]
        j = i - 1
        # 內迴圈：將 base 插入到已排序區間 [0, i-1] 中的正確位置
        while j >= 0 and nums[j] > base:
            nums[j + 1] = nums[j]  # 將 nums[j] 向右移動一位
            j -= 1
        nums[j + 1] = base  # 將 base 賦值到正確位置

nums = [4, 1, 3, 1, 5, 2]
insertion_sort(nums)
print("插入排序完成後 nums =", nums)
```
```c
void insertion_sort(int nums[], int n) {
    // 外迴圈：已排序區間為 [0, i-1]
    for (int i = 1; i < n; i++) {
        int base = nums[i];   // 待插入的元素
        int j = i - 1;

        // 內迴圈：將 base 插入到已排序區間 [0, i-1] 中的正確位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j];  // 將 nums[j] 向右移動一位
            j--;
        }

        nums[j + 1] = base;  // 將 base 賦值到正確位置
    }
}
```
- 程式迴圈可視化：nums = [1~10]：`[1~2]`、`[1~3]`、`[1~4]`、…、`[1~10]`
- 程式白話文說明：從第二個數字開始，依序把右邊的數字放到左邊
- 程式說明：
  - 最左邊數來第2個數字存到base，base = nums[1]
  - 如果base < nums[0]
    - nums[1] = nums[0]
    - nums[0] = base
  - 最左邊數來第3個數字存到base，base = nums[2]
  - 如果base < nums[1]
    - nums[n] = nums[n-1]
  - 直到base > nums[某數] 或 base比到最後一個都還是小於
  - 如直到base > nums[0]
    - nums[1] = base
  - 或base < nums[0]
    - nums[1] = nums[0]
    - nums[0] = base
  - 左邊數來第n個數字存到base，
  - 如果base < 左數(n-1)
    - 左數n = 左數(n-1)  #其實就是左數(n-1)右移
  - 如果base < 左數(n-2)
    - 左數(n-1) = 左數(n-2)
  - 以此類推
  - 直到base >= 左數(n-k)
    - 左數(n-k+1) = base

![079](https://hackmd.io/_uploads/SyzOdQddgg.png =85%x)

## Sort排序，高等排序，O(nlog n)
### Quick Sort：符合Divide and Conquer 
```python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 測試
nums = [4, 1, 3, 1, 5, 2]
sorted_arr = quick_sort(nums)
print("排序後的陣列:", sorted_arr)
```
```c
#include <stdio.h>
#include <stdlib.h>

void quick_sort(int arr[], int left, int right) {
    if (left >= right) return;  // 遞迴終止條件

    int mid = (left + right) / 2;
    int pivot = arr[mid];
    int i = left, j = right;
    int temp;

    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) { 
        // arr[j] < pivot && pivot < arr[i]
        // 交換 arr[i] 與 arr[j]
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    // 遞迴
    if (left < j) quick_sort(arr, left, j);
    if (i < right) quick_sort(arr, i, right);
}

int main() {
    int nums[] = {4, 1, 3, 1, 5, 2};
    int n = sizeof(nums) / sizeof(nums[0]);
    quick_sort(nums, 0, n - 1);
    return 0;
}
```
- 程式白話文說明：
  - 選最左邊的數字當中間點，大的放右邊小的放左邊分成兩區
  - 這兩區進入遞迴，再選該區最左邊的數字當中間點，兩區同上一步，大的放右邊小的放左邊，以此類推
- 程式說明：
  - 選定第一個數字作為哨兵 pivot = nums[left]
  - 設定 i = left，j = right，左右兩端指標
  - 先從右邊往左找，比哨兵小的數字。再從左邊往右找，比哨兵大的數字
  - 如果 i < j，就交換 nums[i] 和 nums[j]
  - 直到 i == j 時，把哨兵（nums[left]）和 nums[i] 交換，此時哨兵左邊都是比哨兵小的數字，右邊都是比哨兵大的數字
  - 對哨兵左邊與右邊各自進行遞迴
  - nums會一直動態調整
- 舉例：
  - [8, 3, 1, 6, 9, 7, 5, 4, 2, 10]
  - [3, 1, 6, 5, 4, 2] 7 [8, 9, 10]
  - [3, 1, 4, 2] 5 [6]
  - [3, 1, 2] 4 []
  - [] 1 [3, 2]
  - [] 2 [3]
  - 1, 2, 3, 4, 5, 6, 7, [8, 9, 10]
  - [8] 9 [10]
  - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

### Merge Sort：符合Divide and Conquer 
```python
def merge(nums: list[int], left: int, mid: int, right: int):
    """合併左子陣列和右子陣列"""
    # 左子陣列區間為 [left, mid], 右子陣列區間為 [mid+1, right]
    # 建立一個臨時陣列 tmp ，用於存放合併後的結果
    tmp = [0] * (right - left + 1)
    # 初始化左子陣列和右子陣列的起始索引
    i, j, k = left, mid + 1, 0
    # 當左右子陣列都還有元素時，進行比較並將較小的元素複製到臨時陣列中
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            tmp[k] = nums[i]
            i += 1
        else:
            tmp[k] = nums[j]
            j += 1
        k += 1
    # 將左子陣列和右子陣列的剩餘元素複製到臨時陣列中
    while i <= mid:
        tmp[k] = nums[i]
        i += 1
        k += 1
    while j <= right:
        tmp[k] = nums[j]
        j += 1
        k += 1
    # 將臨時陣列 tmp 中的元素複製回原陣列 nums 的對應區間
    for k in range(0, len(tmp)):
        nums[left + k] = tmp[k]

def merge_sort(nums: list[int], left: int, right: int):
    """合併排序"""
    # 終止條件
    if left >= right:
        return  # 當子陣列長度為 1 時終止遞迴
    # 劃分階段
    mid = (left + right) // 2 # 計算中點
    merge_sort(nums, left, mid)  # 遞迴左子陣列
    merge_sort(nums, mid + 1, right)  # 遞迴右子陣列
    # 合併階段
    merge(nums, left, mid, right)

nums = [7, 3, 2, 6, 0, 1, 5, 4]
merge_sort(nums, 0, len(nums) - 1)
print("合併排序完成後 nums =", nums)
```
```c
/* 合併左子陣列和右子陣列 */
void merge(int *nums, int left, int mid, int right) {
    // 左子陣列區間為 [left, mid], 右子陣列區間為 [mid+1, right]
    // 建立一個臨時陣列 tmp ，用於存放合併後的結果
    int tmpSize = right - left + 1;
    int *tmp = (int *)malloc(tmpSize * sizeof(int));
    // 初始化左子陣列和右子陣列的起始索引
    int i = left, j = mid + 1, k = 0;
    // 當左右子陣列都還有元素時，進行比較並將較小的元素複製到臨時陣列中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 將左子陣列和右子陣列的剩餘元素複製到臨時陣列中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 將臨時陣列 tmp 中的元素複製回原陣列 nums 的對應區間
    for (k = 0; k < tmpSize; ++k) {
        nums[left + k] = tmp[k];
    }
    // 釋放記憶體
    free(tmp);
}

/* 合併排序 */
void mergeSort(int *nums, int left, int right) {
    // 終止條件
    if (left >= right)
        return; // 當子陣列長度為 1 時終止遞迴
    // 劃分階段
    int mid = left + (right - left) / 2;    // 計算中點
    mergeSort(nums, left, mid);      // 遞迴左子陣列
    mergeSort(nums, mid + 1, right); // 遞迴右子陣列
    // 合併階段
    merge(nums, left, mid, right);
}
```
程式遞迴過程： 

| ![080](https://hackmd.io/_uploads/r1BM27udxe.jpg) | ![081](https://hackmd.io/_uploads/ry9Mhmddxx.jpg) |
| --- | --- |


#### Merge Sort 為什麼比較快？時間複雜度分析
* 拆分時間複雜度 `lg(n)` + 合併時間複雜度 `nlg(n)`，`O(lg(n) + nlg(n)) = O(nlg(n))`
* 為什麼逐步合併更高效？Merge Sort 逐步合併的關鍵在於「減少了比較次數」，對比 Bubble Sort

#### 範例：a, b, c, d 四個數字做 Merge Sort
* 拆成 `a`, `b`, `c`, `d`，拆解的時間複雜度忽略不計
* 第一次合併：
  * 合併成 `[a, b]`、`[c, d]`，共 **2 次比較**：
    * `a` 跟 `b` 比小、`c` 跟 `d` 比小
    * 此時得知 `a < b` 且 `c < d`
* 第二次合併：
  * 合併成 `[c, a, d, b]`，共 **3 次比較**：
    * `a` 跟 `c` 比小、`a` 跟 `d` 比小、`d` 跟 `b` 比小
* 總共比較 5 次
- 對比公式 `nlg(n) = 4lg(4) = 8`，理論上限為 8 次；此處 `n` 不夠大，所以比較 5 次是合理的

#### 對比：Bubble Sort 的比較次數（n = 4）
* 最多可能要比較：
  * `3 + 2 + 1 = 4 * (4-1) / 2 = n * (n-1) / 2 = 6` 次
* → 時間複雜度為 `O(n^2)`
* Merge Sort 比較次數較少 → 時間複雜度為 `O(nlg(n))`

#### 更大範例：a, b, c, d, e, f, g, h 八個數字做 Merge Sort
* 第一次合併：共 4 次比較
* 第二次合併**：共 6 次比較
* 第三次合併**：共 7 次比較
* 總比較次數：17 次
- 對比公式 `nlg(n) = 8lg(8) = 24`，實際比較次數小於理論上限
- 對比 Bubble Sort：`8 * 7 / 2 = 28` 次
- 這就是 **時間複雜度 O(n^2) 跟 O(nlogn) 的差異**

### Heap Sort 
```python
def sift_down(nums: list[int], n: int, i: int):
    """堆積的長度為 n ，從節點 i 開始，從頂至底堆積化"""
    while True:
        # 判斷節點 i, l, r 中值最大的節點，記為 ma
        l = 2 * i + 1
        r = 2 * i + 2
        ma = i
        if l < n and nums[l] > nums[ma]:
            ma = l
        if r < n and nums[r] > nums[ma]:
            ma = r
        # 若節點 i 最大或索引 l, r 越界，則無須繼續堆積化，跳出
        if ma == i:
            break
        # 交換兩節點
        nums[i], nums[ma] = nums[ma], nums[i]
        # 迴圈向下堆積化
        i = ma

def heap_sort(nums: list[int]):
    """堆積排序"""
    # 建堆積操作：堆積化除葉節點以外的其他所有節點
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    # 從堆積中提取最大元素，迴圈 n-1 輪
    for i in range(len(nums) - 1, 0, -1):
        # 交換根節點與最右葉節點（交換首元素與尾元素）
        nums[0], nums[i] = nums[i], nums[0]
        # 以根節點為起點，從頂至底進行堆積化
        sift_down(nums, i, 0)
```
```c
/* 堆積的長度為 n ，從節點 i 開始，從頂至底堆積化 */
void siftDown(int nums[], int n, int i) {
    while (1) {
        // 判斷節點 i, l, r 中值最大的節點，記為 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若節點 i 最大或索引 l, r 越界，則無須繼續堆積化，跳出
        if (ma == i) {
            break;
        }
        // 交換兩節點
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 迴圈向下堆積化
        i = ma;
    }
}

/* 堆積排序 */
void heapSort(int nums[], int n) {
    // 建堆積操作：堆積化除葉節點以外的其他所有節點
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(nums, n, i);
    }
    // 從堆積中提取最大元素，迴圈 n-1 輪
    for (int i = n - 1; i > 0; --i) {
        // 交換根節點與最右葉節點（交換首元素與尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根節點為起點，從頂至底進行堆積化
        siftDown(nums, i, 0);
    }
}
```
- 注意Heap(堆積)不是stack(堆疊)，雖然中文幾乎是同樣的意思
- 堆積是一種完整二元樹，任意節點大於其子節點，
- 先將數列入大頂堆積，再將數列從大到小出堆積，完成排序
- 入Heap跟出Heap都在資料結構類型Heap的單元有介紹

## Sort排序，其他排序，O(n+m)

### Bucket Sort
- 程式白話文：把數字分類到不同的桶，每個桶在進行排序，桶子的數量為m，
- 時間複雜度：桶子均勻分配：O(nlg(n/k))；桶子數量很多且均勻：O(n)；桶子不均勻：O(n^2)

![082](https://hackmd.io/_uploads/r1s027d_ge.png =85%x)

### Counting Sort 
時間複雜度：O(n+m)，m代表的是數列的最大數，m不能太大，否則可能比O(nlg(n))還大
程式說明：
Step1：找最大的數字；
Step2：創建m+1個空格的數列counter，因為0~m共可能出現m+1個數字
Step3：計算每個數字出現的次數，如0出現3次，counter[0] = 3
Step4：用兩個迴圈，遍歷counter把nums覆蓋掉

### Radix Sort 
用count sort，排序的對象是從最低位數字開始，如下圖，先排序個位、再十位、依序排序到第八位

台大劉智弘112-2演算法，Radix時間複雜度公式，(b/r)(n + 2^r)，用Claud說應該改成，(b/r)(n + k^r)，
b是幾位數，r是每次處理的位元，k是幾進位，k^r表示每次需要用到的count數量，
所以期中考前的講解才會說r≤ b，因為每次處理的位元不可能>總共幾位元

當台大複雜度r = 1，每次固定只處理一個位元，就會是hello演算法教的複雜度公式了
時間複雜度O((n+d)k)，n資料量，d幾進位，k最大位數，d、k小趨近O(n)，否則趨近O(n^2)

![083](https://hackmd.io/_uploads/BJs1TXudee.png =85%x)

## Dynamic Programming DP 動態規劃
###  爬樓梯問題
將一個問題分解為一系列更小的子問題，透過儲存子問題的解來避免重複計算，大幅提升時間效率
- 問題：每次可以上升一步或兩步，算到達某樓層有幾種走法
- dp[n] = 走法數量
- $dp[n] = dp[n-1] + dp[n-2]$
- 暴力搜尋：從答案往下把所有可能路徑推測出來
- 記憶畫搜尋：記憶化，Top-down，自上而下，會設定一個mem[i]紀錄dp[i]的走法，避免重複計算
- DP：動態規劃，Bottom-up，自下而上：從最小子問題的解開始，迭代地構建更大子問題的解，直至得到解，DP程式用迴圈跟遞迴，遞迴都很類似DFS，先深入到最底層再往上算，DP不需要回溯過程
- [python程式可視化](https://pythontutor.com/render.html#mode=display)

|![084](https://hackmd.io/_uploads/rk6Na7O_xg.png =85%x)|![086](https://hackmd.io/_uploads/ByAuumjOlx.png =85%x)|![085](https://hackmd.io/_uploads/H1WLa7O_eg.png =85%x)|
|-|-|-|

```python=
# ===================== 純 DFS =====================
def dfs_pure(i):
    if i == 1 or i == 2: return i
    count = dfs_pure(i - 1) + dfs_pure(i - 2)
    return count

def run_dfs_pure(n):
    result = dfs_pure(n)
    return result

# ===================== 記憶化 DFS =====================
def dfs_mem(i, mem):
    if i == 1 or i == 2: return i
    if mem[i] != -1: return mem[i]
    count = dfs_mem(i - 1, mem) + dfs_mem(i - 2, mem)
    mem[i] = count
    return count

def run_dfs_mem(n):
    mem = [-1] * (n + 1)
    result = dfs_mem(n, mem)
    return result

# ===================== 動態規劃 =====================
def run_dp(n: int) -> int:
    if n == 1 or n == 2: return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] # DP
    return dp[n]

# ===================== 動態規劃&空間最佳化 =============
def run_dp_comp(n: int) -> int:
    if n == 1 or n == 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1): a, b = b, a + b
    return b

# ===================== 測試 =====================
n = 9
print(run_dfs_pure(n))
print(run_dfs_mem(n))
print(run_dp(n))
print(run_dp_comp(n))
```

### 爬樓梯+cost 最佳化結構
- 問題：走到某樓層花費最小的cost
- 每次上升一步或兩步
- dp[i] = 花費的cost

#### 定義方式一：`dp[i]` 包含踏上第 i 階的 cost
$$ dp[i] = \min(dp[i-1], dp[i-2]) + cost[i] $$

* `dp[i]` = 走到第 i 階的最小花費（包含第 i 階的 cost）
* 狀態轉移：只能從 i-1 或 i-2 來，所以取其中花費較小者，再加上 cost\[i]。

#### 定義方式二：`dp[i]` 不包含踏上第 i 階的 cost

$$
dp[i] = \min(dp[i-1] + cost[i-1],\ dp[i-2] + cost[i-2])
$$

* `dp[i]` = 走到第 i 階的最小花費（不包含第 i 階 cost）
* 狀態轉移：要走到第 i 階，可以從 i-1 踏一步過來（此時要加上 cost\[i-1]），或從 i-2 踏兩步過來（要加上 cost\[i-2]），取兩者較小者。

```python
def min_cost_climbing_stairs_dp(cost: list[int]) -> int:
    n = len(cost) - 1
    if n == 1 or n == 2: return cost[n]
    dp = [0] * (n + 1) # 初始化 dp 表，用於儲存子問題的解
    dp[1], dp[2] = cost[1], cost[2] # 初始狀態：預設最小子問題的解
    for i in range(3, n + 1): dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] # 定義方式一
    return dp[n]

def min_cost_climbing_stairs_dp_comp(cost: list[int]) -> int:
    n = len(cost) - 1
    if n == 1 or n == 2: return cost[n]
    a, b = cost[1], cost[2]
    for i in range(3, n + 1): a, b = b, min(a, b) + cost[i]
    return b
```

### 爬樓梯+不能連續兩次上升一階 無後效性
- 動態規劃需要「無後效性」（未來只與「當前狀態」有關）
- 當加入「不能連續兩次跳 1 階」的限制時，單純用 `dp[i]`（只記高度）不足， 
- 必須把「上一跳的步數」一併納入狀態，才能達成無後效性

#### 狀態定義
- `dp[i, 1]`：到達第 `i` 階，且上一跳為 1 階的走法數
- `dp[i, 2]`：到達第 `i` 階，且上一跳為 2 階的走法數

總走法數：
$$
f(i) = dp[i,1] + dp[i,2]
$$

#### 遞推關係
$$
dp[n] = dp[n,1]+dp[n,2]
$$
- 若最後一跳為1 階，前一跳不可為 1 階，只能由「上一跳為 2 階」的狀態接上來：
$$
dp[i,1] = dp[i-1,2] \quad (i \ge 2)
$$
- 若最後一跳為2 階，可以從任何以 1 或 2 結尾的狀態接上來：
$$
dp[i,2] = dp[i-2,1] + dp[i-2,2] \quad (i \ge 1)
$$

```python
def climbing_stairs_constraint_dp(n: int) -> int:
    if n == 1 or n == 2: return 1
    dp = [[0] * 3 for _ in range(n + 1)] # 初始化 dp 表，用於儲存子問題的解
    dp[1][1], dp[1][2] = 1, 0 # 初始狀態：預設最小子問題的解
    dp[2][1], dp[2][2] = 0, 1
    for i in range(3, n + 1): # 狀態轉移：從較小子問題逐步求解較大子問題
        dp[i][1] = dp[i - 1][2]
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
    return dp[n][1] + dp[n][2]

'''
dp = [
#   0  1  2
    [0, 0, 0],   # dp[0]
    [0, 1, 0],   # dp[1]
    [0, 0, 1],   # dp[2]
    [0, 0, 0],   # dp[3]
    [0, 0, 0],   # dp[4]
    [0, 0, 0],   # dp[5]
]
dp[row][column]
dp[0]沒用到
'''
```

### Grid最短路徑
- 問題：從`grid[0][0]`走最小路徑到終點
- d[n][m] = 對應xy圖的座標
- $dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]$

```python
from math import inf

# --- DFS ---
def min_path_sum_dfs(grid, i, j):
    if i == 0 and j == 0: return grid[0][0]
    if i < 0 or j < 0: return inf
    up = min_path_sum_dfs(grid, i - 1, j)
    left = min_path_sum_dfs(grid, i, j - 1)
    res = min(left, up) + grid[i][j]
    return res

# --- DP ---
def min_path_sum_dp(grid):
    n, m = len(grid), len(grid[0])
    dp = [[0] * m for _ in range(n)]
    dp[0][0] = grid[0][0]

    # 狀態轉移：首行 row
    for j in range(1, m): dp[0][j] = dp[0][j - 1] + grid[0][j]

    # 狀態轉移：首列 column
    for i in range(1, n): dp[i][0] = dp[i - 1][0] + grid[i][0]

    # dp
    for i in range(1, n):
        for j in range(1, m): dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]

    return dp[n - 1][m - 1]

# --- 測試 ---
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]

print(min_path_sum_dfs(grid, len(grid) - 1, len(grid[0]) - 1))
print(min_path_sum_dp(grid))
'''
初始化dp = [
    [1, 4, 5],
    [2, 0, 0],
    [6, 0, 0]
]

最後dp = [
    [1, 4, 5],
    [2, 7, 6],
    [6, 8, 7]
]

dp[3][3] = 7，答案7
'''
```
### 背包問題：東西只能選一次
- capacity：包包容量
- weight：物品重量
- value：物品價值
- dp[i, cap], i = 第i品物品的決策
- $dp[i, cap] = max(dp[i-1, c], dp[i-1, c-wgt[i-1]]+val[i-1]) = max(不選i, 選i)$

| ![088](https://hackmd.io/_uploads/ry0zGsGtgg.jpg) | ![089](https://hackmd.io/_uploads/BkzQfoGKlg.jpg) |
|---|---|
|![086](https://hackmd.io/_uploads/rJhcb3-tgl.jpg)|![087](https://hackmd.io/_uploads/ByuwfnMKge.jpg)|

```python
def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int):
    if i == 0 or c == 0: return 0
    if wgt[i - 1] > c: return knapsack_dfs(wgt, val, i - 1, c)
    no = knapsack_dfs(wgt, val, i - 1, c)
    yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
    return max(no, yes)

def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    n = len(wgt)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c: dp[i][c] = dp[i - 1][c] # 若超過背包容量，則不選物品 i
            else: dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]) # 不選和選物品 i 這兩種方案的較大值
    return dp[n][cap]
```
### 完全背包問題：東西可以重複選
- dp[i, cap], i = 第i件物品的決策
- 01背包：$dp[i, cap] = max(dp[i-1, c], dp[i-1, c-wgt[i-1]]+val[i-1])$
- 完全背包：$dp[i, cap] = max(dp[i-1, c], dp[i, c-wgt[i-1]]+val[i-1])$
- 因為物品數量無限制，完全背包的 DP 轉移可以從同一 row 的左邊狀態更新，而不是像 01 背包只能從上一 row 轉移
- 同112-1台大生醫資訊學導論期中考

```python
def unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    n = len(wgt)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c: dp[i][c] = dp[i - 1][c] # 若超過背包容量，則不選物品 i
            else: dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]) # 不選和選物品 i 這兩種方案的較大值
    return dp[n][cap]
```

### 零錢問題：最少硬幣數量
- 題目：用硬幣湊出目標金額，使硬幣數量最少
- 「物品」對應「硬幣」，「物品重量」對應「硬幣面值」，「背包容量」對應「目標金額」
- 完全背包問題允許「不超過」背包容量，而零錢兌換要求「恰好」湊到目標金額
- Amount：金額
- i：要不要使用該幣值
- $dp[i][a] = 硬幣數量$
- 狀態轉移方程：$dp[i][a] = min(dp[i-1][a], dp[i][a-coins[i-1]] + 1)$

![091](https://hackmd.io/_uploads/HJOMshGFlg.jpg =75%x)

```python
def coin_change_dp(coins: list[int], amt: int) -> int:
    n = len(coins)
    MAX = amt + 1
    dp = [[0] * (amt + 1) for _ in range(n + 1)]
    for a in range(1, amt + 1): dp[0][a] = MAX
    for i in range(1, n + 1):
        for a in range(1, amt + 1):
            if coins[i - 1] > a: dp[i][a] = dp[i - 1][a] # 若超過目標金額，則不選硬幣 i
            else: dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1) # 不選和選硬幣 i 這兩種方案的較小值
    return dp[n][amt] if dp[n][amt] != MAX else -1
```
### 零錢問題：硬幣組合數量
- 題目：金額換成硬幣數量的組合數量
- $dp[i][a] = 組合數量$
- 狀態轉移方程：$dp[i, a] = dp[i-1, a] +dp[i, a-coins[i-1]]$
```python
def coin_change_ii_dp(coins: list[int], amt: int) -> int:
    n = len(coins)
    dp = [[0] * (amt + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = 1
    for i in range(1, n + 1):
        for a in range(1, amt + 1):
            if coins[i - 1] > a: dp[i][a] = dp[i - 1][a] # 若超過目標金額，則不選硬幣 i
            else: dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]] # 不選和選硬幣 i 這兩種方案之和
    return dp[n][amt]
```

### Matrix-chain multiplication
### Optimal binary search tree
### 編輯距離問題
- 題目：將 kitten 轉換為 sitting 最少需要編輯的步數
- $dp[i, j] = 修改次數$
- $dp[i, j] = min(dp[i, j-1], dp[i-1, j], dp[i-1, j-1])+1$
- 若$s[i-1]=j[i-1]$，則$dp[i, j] = dp[i-1, j-1]$
- 為什麼畫表格可以算出最少的步驟? 因為表格上的數字都可以同時代表刪除、修改、新增

![092](https://hackmd.io/_uploads/B12EkpGKlx.jpg =75%x)

```python
def edit_distance_dp(s: str, t: str) -> int:
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # 初始化
    for i in range(1, n + 1): dp[i][0] = i
    for j in range(1, m + 1): dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s[i - 1] == t[j - 1]: dp[i][j] = dp[i - 1][j - 1]
            else: dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

    # 印出 DP 表格
    print("DP 表格 (列=字串 s, 行=字串 t):")
    header = "    " + "  ".join([" "] + list(t))
    print(header)
    for i in range(n + 1):
        row_label = " " if i == 0 else s[i - 1]
        print(f"{row_label} {dp[i]}")

    return dp[n][m]

# 測試範例
s = "code"
t = "abcodez"
ans = edit_distance_dp(s, t)
print(f"編輯距離 = {ans}")

'''
      a  b  c  o  d  e  z
  [0, 1, 2, 3, 4, 5, 6, 7]
c [1, 1, 2, 2, 3, 4, 5, 6]
o [2, 2, 2, 3, 2, 3, 4, 5]
d [3, 3, 3, 3, 3, 2, 3, 4]
e [4, 4, 4, 4, 4, 3, 2, 3]
編輯距離 = 3
'''
```

### DP Longest common subsequence (LCS)

### DP公式總整理

<div style="overflow-x: auto; white-space: nowrap;">

| 題型 | 狀態定義 (dp) | 狀態轉移方程 | 備註 | 初始化 | 圖示
|-|-|-|-|-|-|
| 爬樓梯：算到達某樓層的走法數 | dp[n] = 走法數量 | $dp[n] = dp[n-1] + dp[n-2]$ | 基本 Fibonacci 類型 |```[1, 1, 0, 0, 0, 0, 0, 0]```|![image](https://hackmd.io/_uploads/SydZoPzLWx.png)|
| 爬樓梯：走到某樓層花費最小 cost | dp[i] = 花費 | $dp[i] = \min(dp[i-1], dp[i-2]) + cost[i]$ <br> 或 $dp[i] = \min(dp[i-1]+cost[i-1],\ dp[i-2]+cost[i-2])$ | 可以有不同的 cost 計算方式 |```[0, cost[1], cost[2] 0, 0, 0]```|![image](https://hackmd.io/_uploads/B19lnvGUZg.png)|
| 爬樓梯有後效性問題 | d[n] = 走的方法數量 <br> d[i,1] = 第 i 層上一步是往上 1 | $dp[n] = dp[n,1] + dp[n,2]$<br>$dp[i,1] = dp[i-1,2] \quad (i \ge 2)$<br>$dp[i,2] = dp[i-2,1] + dp[i-2,2] \quad (i \ge 1)$ | 有限制不能連續只上一步 |```　　 上1  上2```<br>```0階  [ 0,   0]```<br>```1階  [ 1,   0]```<br>```2階  [ 0,   1]```<br>```3階  [ 0,   0]```<br>```4階  [ 0,   0]``` |![image](https://hackmd.io/_uploads/Sy2vADfUbg.png)|
| 走最小路徑到終點 (Grid) | d[i][j] = 到座標 (i,j) 的最小路徑和 | $dp[i][j] = \min(dp[i][j-1],\ dp[i-1][j]) + grid[i][j]$ | 二維 DP |grid:<br>```[[1, 3, 1],```<br>``` [1, 5, 1],```<br>``` [4, 2, 1]]```<br>初始化 dp:<br>```[[1, 4, 5],```<br>``` [2, 0, 0],```<br>``` [6, 0, 0]]``` |![image](https://hackmd.io/_uploads/B1fUJ_GUZx.png)|
| 01 背包問題 | dp[i, cap] = 第 i 個物品決策下，容量為 cap 的最大價值 | $dp[i,cap] = \max(dp[i-1,cap],\ dp[i-1,cap-wgt[i-1]]+val[i-1])$ | 物品只能選一次 |```容量→　0　1　2　3　4```<br>```物品0  [0,  0,  0,  0,  0]```<br>```物品1  [0,  0,  0,  0,  0]```<br>```物品2  [0,  0,  0,  0,  0]```<br>```物品3  [0,  0,  0,  0,  0]``` |![087](https://hackmd.io/_uploads/ByuwfnMKge.jpg)|
| 完全背包問題 | dp[i, cap] = 第 i 個物品決策下，容量為 cap 的最大價值 | $dp[i,cap] = \max(dp[i-1,cap],\ dp[i,cap-wgt[i-1]]+val[i-1])$ | 物品可以重複選 |```容量→　0　1　2　3　4```<br>```物品0  [0,  0,  0,  0,  0]```<br>```物品1  [0,  0,  0,  0,  0]```<br>```物品2  [0,  0,  0,  0,  0]```<br>```物品3  [0,  0,  0,  0,  0]``` |![image](https://hackmd.io/_uploads/rJP2SufUWx.png)|
| 零錢問題：最少硬幣數 | dp[i][a] = 金額 a 所需最少硬幣數 | $dp[i][a] = \min(dp[i-1][a],\ dp[i][a-coins[i-1]] + 1)$ | 完全背包變形 | ```金額→　0　1　2　3　4```<br>```硬幣0  [0,  ∞,  ∞,  ∞,  ∞]```<br>```硬幣1  [0,  0,  0,  0,  0]```<br>```硬幣2  [0,  0,  0,  0,  0]```<br>```硬幣3  [0,  0,  0,  0,  0]``` |![image](https://hackmd.io/_uploads/r13xNdM8-l.png)|
|零錢問題：硬幣組合數量|dp[i][a] = 金額a的所有硬幣組合數量|$dp[i, a] = dp[i-1, a] +dp[i, a-coins[i-1]]$|硬幣變形題|```金額→　0　1　2　3　4```<br>```硬幣0  [1, 0,  0,  0,  0]```<br>```硬幣1  [1, 0,  0,  0,  0]```<br>```硬幣2  [1, 0,  0,  0,  0]```<br>```硬幣3  [1, 0,  0,  0,  0]``` |![image](https://hackmd.io/_uploads/SJYwudGUbl.png)|
| 編輯距離 (Edit Distance) | dp[i,j] = 將前 i 個字元轉換成前 j 個字元所需修改次數 | $dp[i,j] = \min(dp[i,j-1],\ dp[i-1,j],\ dp[i-1,j-1]) + 1$ <br> 若 $s[i-1]=t[j-1]$，則 $dp[i,j]=dp[i-1,j-1]$ | 字串 DP，插入、刪除、替換 | ```　 　 a　b　c　 o　d　e　z```<br>```　[0, 1, 2, 3, 4, 5, 6, 7]```<br>```c [1, 0, 0, 0, 0, 0, 0, 0]```<br>```o [2, 0, 0, 0, 0, 0, 0, 0]```<br>```d [3, 0, 0, 0, 0, 0, 0, 0]```<br>```e [4, 0, 0, 0, 0, 0, 0, 0]``` |![image](https://hackmd.io/_uploads/HkpngdzUbg.png)|



</div>



### Greedy

## Amortized Analysis 平攤分析
### Aggregate Method 聚集法
### Accounting Method 會計方法
### Potential Method 潛能方法

## Elementry Tree & Graph Algorithms 基本樹圖演算法
### 樹的 BFS（層序遍歷）
* 時間複雜度：O(n)
* 程式碼範例：

```python
from collections import deque

def bfs_tree(root):
    if not root: 
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

'''
print(node.val)是造訪過的點、走訪的路徑
quene是暫存的點
'''
```
適用：二元樹 / N 元樹層序遍歷。
鄰居是 固定的左右子節點。
![BFS 示意](https://hackmd.io/_uploads/HyGEk4vOxx.png)

### 圖的 BFS

* 特點：由近到遠，層層擴展
* 實現：使用 **Queue（先進先出）**，常用迴圈實現
* 用途：尋找最短路徑、層次遍歷等

參考程式：`ch9/graph_bfs.py`
```python
from collections import deque

def bfs_graph(start, adjacency_list):
    visited = set()
    q = deque([start])
    visited.add(start)
    
    while q:
        node = q.popleft()
        print(node)
        for neighbor in adjacency_list[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)

'''
visited是造訪過的點、走訪的路徑
quene是暫存的點

while q、for、if、q.append就是BFS

A - B
|
C

q = [A]
visited = {A}

q = [B, C]
visited = {A, B, C}

q = [C]

q = []
'''
```

適用：無向圖、有向圖的最短路徑、是否可達。
一定要有 `visited`，避免死循環。
![圖解 BFS](https://hackmd.io/_uploads/H1Vvpzwuex.png)
![BFS 範例](https://hackmd.io/_uploads/HJ1OTMwOxx.png)

### 樹的 DFS（遞迴版）
* 時間複雜度：O(n)
* 程式碼範例：

```python
def dfs_tree(root):
    if not root:
        return
    print(root.val)   # 前序遍歷
    dfs_tree(root.left)
    dfs_tree(root.right)

# print(root.val)是造訪過的點、走訪的路徑
```
適用：二元樹遍歷（前序、中序、後序都行）。
樹不會有環，所以 **不用 visited**。
| ![DFS 示意](https://hackmd.io/_uploads/r1nEkVDulg.png) | ![DFS 深度示意](https://hackmd.io/_uploads/rk_rkVvOel.png) |
| ---------------------------------------------------- | ------------------------------------------------------ |

### 圖的 DFS

* 特點：走到底再回頭
* 實現：使用 **Stack（先進後出）**，通常以遞迴實現
* 節點概念：
  * 邊有方向且是單向的
  * 節點 b 的鄰接節點如 c、e，先走完 b→c 的深度，再走 b→e

參考程式：`ch9/graph_dfs.py`
```python
def dfs_graph(node, adjacency_list, visited):
    if node in visited:
        return
    visited.add(node)
    print(node)
    for neighbor in adjacency_list[node]:
        dfs_graph(neighbor, adjacency_list, visited)

'''
迴圈內馬上遞迴就是DFS
visited是造訪過的點、走訪的路徑

A - B - D
|
C

處理順序：A → B → D → C
'''
```

適用：連通分量、拓撲排序、檢查是否有環。
圖可能有環，**一定要有 visited**。
![DFS 圖解](https://hackmd.io/_uploads/ryqYpMDugx.png)

#### 對照表

| 類型    | BFS                      | DFS                         |
| ----- | ------------------------ | --------------------------- |
| **樹** | queue + 左右子節點            | 遞迴 (前序/中序/後序)               |
| **圖** | queue + `visited` + 遍歷鄰居 | 遞迴/stack + `visited` + 遍歷鄰居 |

### BFS、DFS公式背法
```python
# 圖的BFS
while q:
        for
            if
                .add

# 圖的DFS
for
 DFS()
```

### 圖的DFS 找 Cycle（循環）
* 判斷方式：

  * DFS 過程中，若遇到鄰接節點為 **灰色**（正在訪問中），代表存在 cycle
  * 例：g → b，如果 b 是灰色，則有 cycle
* 特例：

  * 回到灰色節點是因為無路可走，則不算 cycle（如 d → c）
* 流程：

  1. 進入節點，標記為灰色
  2. 遞迴訪問鄰接節點
  3. 鄰接節點全部訪問完，標記為黑色

參考程式：`112-2劉智弘演算法/期末考前猜題_DFS找cycle.py`
![DFS 找 cycle](https://hackmd.io/_uploads/HJLY6MvOll.png =50%x)

### Topological Sort
### Disjoint Set Forests 不相交集

# Graph Algorithms 圖演算法 (圖論)
## Minimum Spanning Trees 最小生成樹：不cycle的情況下，每個點都連到
### Cut Property
### Prim algorithm
### Kruskal algorithm

## Single-Source Shortest Paths 單源最短路徑，題:給一個起點，算到某頂點V的最短距離：
### Two Operations：Initialization、Relax
### Bellman-Ford
### Directed Acyclic Graph (DAG)
### Dijkstra

## All-Pairs Shortest Paths，題:給一個圖，算任意兩點的最短距離：
### DP-MM (Matrix Multiply)
### DP-Floyd-Warshall
### Johnson

## Maximum Flow，最大流題目：給一個道路，求此道路最大進入終點流量：
### Ford-Fulkerson
### Minimum Cut
### Bipartite Matching

## NP-Completeness，NP完備 NP完全，證明題
### NP 完備與 NP 完全

# Reference
- [Hello Algo](https://www.hello-algo.com/zh-hant/)
- [GeeksforGeeks](https://www.geeksforgeeks.org/)
- [Leetcode](https://leetcode.com/)
- [Collegiate Programming Examination](https://cpe.mcu.edu.tw/)
- [HackerRank](https://www.hackerrank.com/)
