---
title: DSA bestmark520
autoHeadingNumber: true
---
[TOC]
<!-- 按 Ctrl+Shift+P → Markdown: Create Table of Contents-->
# 容器：線性結構
## 線性容器語法總整理：Python, C, C++, string, list, dict
<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）
|  |  |
| --- | --- |
|  |  |
| --- | --- |
```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
注意陷阱：錯誤初始化
```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`要自己手刻
| |  |
| --- | --- |
雜湊函式hash function，index = hash(key) % capacity，如下圖capacity = 100
雜湊衝突與擴容，用上述方法，%100可能會一樣的答案，解決方法為改成%200
|||
| --- | --- |
```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
```
# 容器：Linked List
## Linked List 鏈結串列
- 各個節點記錄當下的值跟下一個值(引用指標)，它們的記憶體位址無須連續，尾節點指向空
- 在 C、C++、Go 和 Rust 等支持指標的語言中，上述引用應被替換為指標
- 插入節點，改變兩個節點的引用(指標)
- 刪除節點，改變一個節點的引用(指標)
| |  |
| --- | --- |
|  |  |
用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
```
```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;
}
```
|||
|-|-|
### 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
}
```
### 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)
先入後出，如桌面上的一疊盤子，如果想取出底部的盤子，則需要先將上面的盤子依次移走
|  |  |
| --- | --- |
### 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)，資料只能朝同一個方向走
|  |  |
| --- | --- |
### 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
|  |  |
| --- | --- |
```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) 必須：
> 左子樹所有值 <父節點
> 右子樹所有值 >父節點
名詞
|  |  |
| --- | --- |
| 名詞 | 說明 |
| ------------------- | ----------------------- |
| 根節點 (root) | 位於樹頂，沒有父節點 |
| 葉節點 (leaf) | 沒有子節點，左右指標均為 `None` |
| 邊 (edge) | 節點與節點之間的連線 |
| 層 (level) | 從上到下計數，根節點在第 1 層 |
| 節點的度 (degree) | 子節點數量，二元樹中度 ∈ {0, 1, 2} |
| 樹的高度 (tree height) | 根到最遠葉節點的邊數 |
| 節點的深度 (depth) | 根到該節點的邊數 |
| 節點的高度 (node height) | 該節點到最遠葉節點的邊數 |
#### 插入與刪除
* 插入與鏈結串列類似，透過修改指標完成。
* 1. 插入：根據數值大小，遞迴找到空位後插入。
* 2. 刪除：
* 無子節點 → 直接刪除。
* 只有一個子節點 → 用子節點替代該節點。
* 兩個子節點 → 找到右子樹的最小值（或左子樹的最大值）替換該節點，再刪除該替代節點。
#### 二元樹種類
| 種類 | 說明 |
| ---------------- | -------------------------------- |
| 完美二元樹 (Perfect) | 每層節點都填滿，高度 h → 節點數 = `2^(h+1)-1` |
| 完全二元樹 (Complete) | 除最後一層外，其餘層填滿；最後一層節點靠左 |
| 滿二元樹 (Full) | 每個節點的度要麼是 0，要麼是 2 |
| 平衡二元樹 (Balanced) | 任意節點左右子樹高度差 ≤ 1 |
| 退化樹 (Degenerate) | 每個節點只有一個子節點，退化成鏈結串列 |
|  |  |
| -- | -- |
|  |  |
#### 陣列表示法
| 完美二元樹轉陣列 | 完全二元樹轉陣列 |
|----------------|--------------|
| | |
| 任意二元樹轉陣列 | |
|-------------------|-------------------|
| | |
## 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
|  |  |
| --- | --- |
|  |  |
|  | |
#### 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.
|  |  |
| --- | --- |
|  |  |
#### 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交換後刪除
|  |  |
| --- | --- |
|  | |
### 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 |
### Heap 堆積說明
是一種特定條件的完全二元樹，有分小頂堆積、大頂堆積。
對於大頂堆積（小頂堆積），堆積頂元素（根節點）的值是最大（最小）的
名詞：堆積頂、堆積底
- 大頂堆積 (max heap)：任意節點的值 ≥ 其子節點的值
- 小頂堆積 (min heap)：任意節點的值 ≤ 其子節點的值
完全二元樹非常適合用陣列來表示，任意節點與其左子節點、右子節點、父節點的關係皆相同。
#### 元素入堆積
很像二元搜尋樹，但堆積的規則是節點一定要都大於或都小於子節點
以大頂堆積為例，因為是完全二元樹，從最後一個位子插入，一直跟自己的父節點比，若自己較大就交換。
#### 堆積頂元素出堆積
直接跟最後一個元素交換後刪除。
以大頂堆積為例，接著頂元素一直跟子節點比，與最大的子節點交換。
#### 串列建立成堆積的方法
##### 方法 1：用入堆積實現
建立一個空堆積，再對每個元素做入堆積操作。
- `n` 個元素，每個元素最多花 `log(n)` 時間
- 時間複雜度：`O(n log n)`
- ps. 分成兩個子節點，時間都會是 `log(n)`
##### 方法 2：用訪問實現
不整理串列，直接將所有元素依序放進完全二元樹中，依次對每個 **非葉節點** 執行 **從頂至底堆積化**。
需要堆積化的節點是 `(n-1)/2`，時間是 `log(n)`，看似時間複雜度是 `O(n log n)`，但這個算法計算錯了，因為較低層的節點數量遠大於較高層的節點數量，所以需要重新計算。
複雜度分析（以完美二元樹為例）：
時間複雜度
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
##### Top-K 方法 2：HeapSort
- 依序把最大的元素出堆積，依次記錄出堆積元素，即可得到從大到小排序的序列
- 複雜度：`O(n log n)`
- 缺點：會超額完成任務（因為會全部排序）
##### 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}
|||
| --- | --- |
#### 鄰接矩陣（adjacency matrix）
- 原理：以二維矩陣記錄頂點間是否有邊，用 **空間換時間**
- 定義：
- `M[i, j] = 1` → 表示 `V[i]` 到 `V[j]` 有邊
- `M[i, j] = 0` → 表示沒有邊
- 主對角線通常為 0（因為頂點不會連到自己）
操作複雜度：
- 初始化：`O(n^2)`（建立全 0 矩陣）
- 新增 / 刪除邊：`O(1)`（直接修改對應位置）
- 新增頂點：`O(n)`（新增一列與一行）
- 刪除頂點：`O(n^2)`（移動矩陣資料）
參考程式：`ch9/graph_adjacency_matrix.py`
#### 鄰接表（adjacency list）
- 原理：每個頂點維護一個「鄰接節點列表」，用 **時間換空間**
- 解釋：假設有頂點 A，它的鄰接表可能是 `[B, C, E]`，表示 A 與這三個點相連。
- 這種方式不會為不存在的邊浪費空間，適合稀疏圖。
- 初始化時，每個頂點都會有一個空列表，之後依邊資料把對應的節點加進去。
操作複雜度：
- 初始化：`O(n + m)`（n 為頂點數，m 為邊數）
- 新增邊：`O(1)`（直接在對應列表加節點）
- 刪除邊：`O(m)`（可能需要搜尋整個列表）
- 新增頂點：`O(1)`（新增一個空列表）
- 刪除頂點：`O(n + m)`（需刪除所有與它相關的邊）
參考程式：`ch9/graph_adjacency_list.py`
# 演算法
## 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紀錄第幾個值最小，最後才把最小的數字交換到最左邊
### 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
## 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);
}
```
程式遞迴過程：
|  |  |
| --- | --- |
#### 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)
### 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)
## 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)
||||
|-|-|-|
```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)$
|  |  |
|---|---|
|||
```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)$
```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]$
- 為什麼畫表格可以算出最少的步驟? 因為表格上的數字都可以同時代表刪除、修改、新增
```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]```||
| 爬樓梯：走到某樓層花費最小 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]```||
| 爬樓梯有後效性問題 | 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]``` ||
| 走最小路徑到終點 (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]]``` ||
| 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]``` ||
| 完全背包問題 | 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]``` ||
| 零錢問題：最少硬幣數 | 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]``` ||
|零錢問題：硬幣組合數量|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]``` ||
| 編輯距離 (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]``` ||
</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
* 特點：由近到遠，層層擴展
* 實現：使用 **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`，避免死循環。
### 樹的 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
* 特點：走到底再回頭
* 實現：使用 **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**。
#### 對照表
| 類型 | 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`
### 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/)
Sign in with Wallet
Connect another wallet