# 愛心筆記
#include <bits/stdc++.h>
using namespace std;
int main(){}
分號 return
long long
cout <<
二分搜要排序過!!
奇數除二 會無條件捨去!
## `switch` 語句
```cpp
int choice;
switch (choice) {
case 1:
cout << "你選擇了 1。" << endl;
break;
default:
cout << "選項無效！" << endl;
break;
}
```
**注意事項**
1. **加上冒號**：每個 `case` 後必須加上冒號 (`:`)。
2. **使用 `break` 關鍵字**：通常需要在每個 `case` 後加上 `break`，避免執行穿透到下一個 `case`。除非你有意使用穿透。
3. **`default` 是可選的**：`default` 可以處理所有不符合的情況，建議使用。
4. **僅支持整數類型**：`switch` 變量僅支持 `int`、`char`、`enum` 等整數類型，不能使用 `float` 或 `string`。
---
## `vector` 使用指南
#### 1. 宣告和初始化
```cpp
vector<int> vec1; // 空的 int vector
vector<int> vec2(5, 10); // 大小為5，每個元素初始化為10
```
#### 2. 基本操作（增加與刪除元素）
```cpp
vec1.push_back(6); // 尾部添加 6
vec1.emplace_back(7); // 尾部直接構造 7（效率較高）
vec1.pop_back(); // 移除最後一個元素
vec1.erase(vec1.begin()); // 移除指定位置元素
vec1.clear(); // 清空 vector，刪除所有元素
```
#### 3. 大小與容量操作
```cpp
int size = vec1.size(); // 獲取當前元素數量
int capacity = vec1.capacity(); // 顯示目前已分配的儲存容量
vec1.resize(10); // 調整 vector 大小為 10
bool isEmpty = vec1.empty(); // 判斷 vector 是否為空
```
#### 4. 進階操作
```cpp
vec1.insert(vec1.begin() + 1, 99); // 在第二個位置插入 99
vec1.emplace(vec1.begin(), 88); // 在第一個位置直接構造 88
vec1.swap(vec2); // 與 vec2 交換內容
```
---
### 二維 `vector` 使用方法
#### 1. 宣告二維 `vector`
```cpp
vector<vector<int>> matrix; // 宣告一個空的二維 int vector
```
#### 2. 初始化固定大小的二維 `vector`
```cpp
vector<vector<int>> matrix(3, vector<int>(4, 0)); // 3 行 4 列，初始化為 0
```
#### 3. 使用列表初始化
```cpp
vector<vector<int>> matrix = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
}; // 初始化為 3x4 的矩陣
```
#### 4. 增加行或列
- **增加行**：使用 `push_back()` 在末尾添加一行。
- **增加列**：需要對每一行分別執行 `push_back()`。
```cpp
matrix.push_back({13, 14, 15, 16}); // 增加一行 {13, 14, 15, 16}
// 在每行的末尾增加一個元素 99
for (auto& row : matrix) {
row.push_back(99);
}
```
#### 5. 刪除行或列
- **刪除行**：`pop_back()` 刪除最後一行，或 `erase()` 刪除指定行。
- **刪除列**：遍歷每一行，刪除對應的列元素。
```cpp
matrix.pop_back(); // 刪除最後一行
matrix.erase(matrix.begin()); // 刪除指定行
// 刪除每行的最後一個元素
for (auto& row : matrix) {
row.pop_back();
}
```
#### 6. 獲取行和列數量
```cpp
int rows = matrix.size(); // 獲取行數
int cols = matrix[0].size(); // 獲取列數（假設每行元素數量一致）
```
#### 7. 迭代二維 `vector`
使用巢狀迴圈遍歷整個二維 `vector`：
```cpp
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
```
## DFS&&BFS(迷宮)
假設迷宮是一個 `n x m` 的二維網格，其中：
- `0` 表示可以走的路徑，
- `1` 表示牆壁（無法穿過）。
我們的目標是從起點 `(0,0)` 出發，到達終點 `(n-1,m-1)`，並找到一條可行的路徑。
---
### 使用 DFS 來解迷宮問題
DFS 會盡量沿著一條路徑深入，直到無路可走再回溯，因此找到的並不一定是最短路徑。
#### DFS 實現範例
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 定義四個移動方向：上、下、左、右
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool dfs(int x, int y, vector<vector<int>>& maze, vector<vector<bool>>& visited) {
int n = maze.size(), m = maze[0].size();
// 如果到達終點，則返回 true 表示成功找到路徑
if (x == n - 1 && y == m - 1) {
cout << "(" << x << "," << y << ")" << endl;
return true;
}
visited[x][y] = true; // 標記當前節點已訪問
// 遍歷四個方向
for (int i = 0; i < 4; i++) {
int nx = x + directions[i][0];
int ny = y + directions[i][1];
// 確保新位置在邊界內且未訪問過，且為可走通路
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) {
if (dfs(nx, ny, maze, visited)) {
cout << "(" << x << "," << y << ")" << endl; // 輸出路徑節點
return true;
}
}
}
return false; // 無路可走，回溯
}
int main() {
vector<vector<int>> maze = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
int n = maze.size(), m = maze[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
if (!dfs(0, 0, maze, visited)) {
cout << "無法找到通往終點的路徑" << endl;
}
return 0;
}
```
#### DFS 結果分析
- **路徑**：程序會輸出一條從終點到起點的可行路徑（如果找到的話）。
- **注意**：DFS 找到的並不是最短路徑，僅是一條可行的路徑。
---
### 使用 BFS 來解迷宮問題
BFS 會逐層展開所有可能的路徑，因此第一條找到的路徑一定是最短路徑，這對於找最短路徑的迷宮問題來說非常合適。
#### BFS 實現範例
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int x, y, dist;
};
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int bfs(vector<vector<int>>& maze) {
int n = maze.size(), m = maze[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
queue<Node> q;
q.push({0, 0, 1});
visited[0][0] = true;
while (!q.empty()) {
Node node = q.front();
q.pop();
// 到達終點，返回距離
if (node.x == n - 1 && node.y == m - 1) {
return node.dist;
}
for (int i = 0; i < 4; i++) {
int nx = node.x + directions[i][0];
int ny = node.y + directions[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) {
q.push({nx, ny, node.dist + 1});
visited[nx][ny] = true;
}
}
}
return -1; // 表示無法找到通往終點的路徑
}
int main() {
vector<vector<int>> maze = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
int shortestPath = bfs(maze);
if (shortestPath != -1) {
cout << "最短路徑長度為: " << shortestPath << endl;
} else {
cout << "無法找到通往終點的路徑" << endl;
}
return 0;
}
```
#### BFS 結果分析
- **最短路徑**：BFS 保證找到的第一條路徑即為最短路徑。
- **距離計算**：`dist` 表示從起點到當前節點的步數，若找到終點則返回最短路徑的步數。
## 🧾 C++ deque 筆記（重點版）
`<deque>（double-ended queue）`是一種 兩端都能高效插入/刪除 的序列容器。
特性介於 vector（隨機存取快）與 list（插刪快）之間。
### 1️⃣ 基本語法
```c++
#include <deque>
using namespace std;
deque<int> dq;
```
### 2️⃣ 基本操作與常用函式（必考）
```c++
// ✔ 插入與刪除（高效）
dq.push_front(x); // 在前端插入，O(1)
dq.push_back(x); // 在後端插入，O(1)
dq.pop_front(); // 在前端刪除，O(1)
dq.pop_back(); // 在後端刪除，O(1)
// ✔ 存取元素
dq.front(); // 取得前端元素
dq.back(); // 取得後端元素
dq[i]; // 隨機存取（無界線檢查）
dq.at(i); // 隨機存取（有界線檢查）
// ✔ 容量
dq.size(); // 大小
dq.empty(); // 是否為空
dq.clear(
```
### 3️⃣ 特別好用但常被忽略的函式（加分題）
#### ✔ 在任意位置插入 / 刪除（比 vector 好用）
```cpp
dq.insert(dq.begin() + 2, 100);
dq.erase(dq.begin() + 3);
```
但效率不如 push_front/back（因為會在內部做搬移）。
#### ✔ 使用 assign() 一次設定內容
```cpp
dq.assign(5, 10); // 變成 {10,10,10,10,10}
dq.assign({1, 2, 3});
```
#### ✔ emplace_front() / emplace_back()（建構後直接放入，不用多一次拷貝）
與 push_ 系列相比，emplace_ 會「就地建構」，較快。
```cpp
dq.emplace_front(1);
dq.emplace_back(2);
```
#### ✔ resize() 改變大小
```cpp
dq.resize(10); // 變大：新元素 = 0
dq.resize(3); // 變小：後面刪掉
dq.resize(5, 99); // 新增元素給定預設值
```
#### ✔ swap() 互換兩個 deque
```cpp
deque<int> a = {1,2,3};
deque<int> b = {4,5};
a.swap(b);
```
--
### 4️⃣ deque 與其他容器差異（考題愛問）
| 容器 | 隨機存取 | 前端插入刪除 | 後端插入刪除 |
| ------ | ----- | ------ | ------ |
| vector | ⭐⭐⭐⭐⭐ | ❌ 慢 | ⭐⭐⭐⭐⭐ |
| list | ❌ 慢 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| deque | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ | ⭐⭐⭐⭐ |
**重點：**
* deque 有真正的雙端 O(1) 插刪
* deque 的 `[]` 隨機存取比 vector 稍慢（但仍是常數時間）
* 記憶體不是連續區塊（由多個區塊組成）
---
### 5️⃣ 必背小範例
#### 📌 雙端佇列常見用途：滑動視窗
```cpp
deque<int> dq;
dq.push_back(3);
dq.push_back(5);
dq.push_front(1);
for (int i = 0; i < dq.size(); i++)
cout << dq[i] << " ";
```
#### 📌 迭代器使用例
```cpp
for (auto it = dq.begin(); it != dq.end(); it++) {
cout << *it << " ";
}
```
---
### 6️⃣ 超常見考題整理（考前必看）
#### ✔ deque 的特性是什麼？
* 兩端插入 / 刪除效率高
* 支援隨機存取
* 記憶體分段（不是連續像 vector）
#### ✔ push_front / push_back 的時間複雜度？
➡ **O(1)**
#### ✔ 在中間插入效率？
➡ **O(n)**（會移動區塊）
#### ✔ 訪問元素時間複雜度？
➡ **O(1)** 隨機存取
#### ✔ deque 擅長什麼用途？
* 滑動視窗
* 雙端 BFS
* 需要兩端都可以快速插入的情境
* 模擬 queue / stack 的升級版
---
如果你要，我可以幫你把全部 deque 筆記合併成 **完整 HackMD 版（含目錄 TOC）**！
---
### 哈希表（Hash Table）：
#### 使用 `unordered_map` 的寫法
```cpp
int main() {
unordered_map<string, int> menu; // 宣告一個無序 map，鍵是菜名，值是價格
menu["炸雞"] = 100;
menu["滷肉飯"] = 50;
menu["珍奶"] = 80;
cout << "珍奶價格：" << menu["珍奶"] << " 元" << endl;
if (menu.count("牛排")) { // 0 表示不存在，1 表示存在
cout << "牛排價格：" << menu["牛排"] <<
```
---
希望這段筆記能讓你未來使用哈希表時，一秒找到解答 ❤️
## 特殊函式
1. **`lower_bound(v.begin(), v.end(), x)`**
- 使用內建的二分搜尋，回傳 `x` 插入的位置，前提是 `v` 已經排序好。
2. **`find(v.begin(), v.end(), x)`**
- 尋找 `x`，回傳第一個 `x` 的位置（若找不到則回傳 `v.end()`）。
3. **`sort(v.begin(), v.end())`**
- 快速排序 `vector` 或任意範圍的元素。
#### 1. `accumulate()`：累加和
- 位於 `<numeric>` 頭文件，用於計算範圍內所有元素的總和。
```cpp
#include <numeric>
vector<int> vec = {1, 2, 3, 4, 5};
int sum = accumulate(vec.begin(), vec.end(), 0); // 總和為15
```
#### 2. `count()`：計算元素出現次數
- 計算範圍內指定值的出現次數。
```cpp
vector<int> vec = {1, 2, 3, 1, 1};
int ones = count(vec.begin(), vec.end(), 1); // ones 為 3
```
#### 3. `max_element()` 和 `min_element()`：最大和最小元素
- 回傳指向範圍內最大或最小元素的迭代器。
```cpp
vector<int> vec = {1, 9, 3, 7, 5};
int max_val = *max_element(vec.begin(), vec.end()); // 最大值 9
int min_val = *min_element(vec.begin(), vec.end()); // 最小值 1
```
#### 4. `unique()`：刪除相鄰重複元素
- 刪除相鄰的重複元素，返回最後一個不重複元素的下一個位置的迭代器。
- **需先排序**，並搭配 `erase()` 使用來真正刪除多餘元素。
```cpp
vector<int> vec = {1, 1, 2, 3, 3, 4};
vec.erase(unique(vec.begin(), vec.end()), vec.end()); // vec 為 {1, 2, 3, 4}
```
#### 5. `reverse()`：反轉
- 反轉範圍內的元素順序。
```cpp
vector<int> vec = {1, 2, 3, 4};
reverse(vec.begin(), vec.end()); // vec 為 {4, 3, 2, 1}
```
#### 6. `distance()`：計算迭代器距離
- 返回兩個迭代器之間的距離，常用於找出位置。
```cpp
vector<int> vec = {10, 20, 30, 40};
int index = distance(vec.begin(), find(vec.begin(), vec.end(), 30)); // index 為 2
```
#### 1. `shuffle()`：隨機排列
- 位於 `<algorithm>`，將範圍內元素隨機排列，適合洗牌等操作。
```cpp
vector<int> vec = {1, 2, 3, 4, 5};
random_device rd;
mt19937 g(rd());
shuffle(vec.begin(), vec.end(), g); // 隨機排列 vec
```
#### 2. `sqrt()` 和 `cbrt()`：平方根與立方根
```cpp
double result1 = sqrt(16); // result1 為 4
double result2 = cbrt(27); // result2 為 3
```
#### 3. `ceil()` 和 `floor()`：向上或向下取整
```cpp
double result1 = ceil(4.2); // result1 為 5
double result2 = floor(4.7); // result2 為 4
```
希望這些補充對你比賽有幫助！❤️
代林: 水題解一解就有佳作
Google Drive
Gist
Clipboard
Sign in with Wallet
