### stringstream 讀字串裡的東西 :+1:
- 用法 :
- 1 . 先讀字串 : `getline(cin,s)`
- 2 . 定義一個stringstream : `stringstream ss(s)`
- 3 . 把每一資料像cin一樣間隔空格讀出來 `ss>>a[i]`
- 例子 :
```c++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin >> n){
cin.ignore();
int a[10001] = {0}, i = 0;
string s;
getline(cin, s);
stringstream ss(s);
while(ss >> a[i]){
cout << a[i] << " ";
i++;
}
cout << endl;
}
return 0;
}
```
### sort函式進階用法
1 . **用 `vector` 排序**
```c++
vector<int> v = {5,2,9,1};
sort(v.begin(), v.end());
```
2 . `compare function`
- **核心定義** :
```c++
//只能回傳true/false
compare(a, b) == true --> a 在 b 前面
compare(a, b) == false --> b 在 a 前面
```
```c++
//不能寫成 >= 或 <=
return a<=b;
```
- **小到大排列,大到小排列** :
```c++
// 小到大
bool compare(int a, int b){
return a>b;
}
```
```c++
// 大到小
bool compare(int a, int b){
return a<b;
}
```
- **比較複雜條件** :+1:
* 常遇到這種類型 :
* 先用「第一優先」排序
* 若相同，用「第二優先」排序
* 若還相同，用「第三優先」排序
```c++
bool compare(int a, int b){
if(第一條件不同) return 第一條件比較結果;
if(第二條件不同) return 第二條件比較結果;
return 第三條件比較結果;
}
```
```
//舉例
bool compare(int a, int b){
int A = a % m, B = b % m;
if(A != b) return A<B;
bool OddA = a % 2 != 0;
bool OddB = b % 2 != 0;
if(OddA != OddB) return OddA;//1 0 --> 0 1
if(OddA) return a>b;
return a<b;
}
```
### vector的使用
- 定義 : 可以自動變大、變小的陣列 ， 不同於普通陣列(ex : int s[100])
#### 簡易用法
1 . **加入數字** :
```c++
vector<int> s;
s.push_back(10);
s.push_back(20);
s.push_back(30);
```
- 陣列裡面就是 s[2] = {10, 20, 30};
2 . **看陣列長度** :
```c++
cout<<s.size();
```
3 . **刪除最後一個**
```c++
cout<<s.pop_back();
```
4 . **清空**
```c++
s.clear();
```
##### 簡單範例
```c++
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> s;
int n, m;
cin >> n; // 輸入 n 筆資料
for(int i=0; i<n; i++){
cin >> m;
s.push_back(m); // 放進 vector
}
for(int i=0; i<s.size(); i++){
cout << s[i] << " ";
}
return 0;
}
```
#### 進階用法
1 . **vector排序(sort)**
- 升序(小->大)
```c++
sort(s.begin(), s.end());
```
或是
```c++
bool compare(int a, int b){
reutrn a<b;
}
```
- 降序(大->小)
```c++
sort(s.begin(), s.end(), greater<int>());
```
或是
```c++
bool compare(int a, int b){
return a>b;
}
```
2 . **找某個元素(find)**
```c++
vector<int> s = {1, 2, 7}//找到
auto it = find(s.begin(), s.end(), 7);
if(it != s.end()){//find() 找不到東西就跑到最後 (end())，所以判斷要用 it != s.end()。
cout << "找到" << endl;
}else{
cout << "沒有" << endl;
}
```
3 . **刪除特定位置(erase)**
- 刪除某個值
```c++
s.erase(s.begin()+4);
```
- 刪除某一段
```c++
s.erase(s.begin()+2, s.begin()+4);
```
4 . **插入元素(insert)**
- 在第i個位置插入x
```c++
s.insert(s.begin()+2, 3);
```
5 . **二維vector(DP/地圖/棋盤)**
- 宣告二維vector
```c++
vector<vector(int)> s;
```
6 . 常見競程技巧
- 計算某數值出現次數
```c++
int sum = count(s.begin(), s.end(), 5);
```
- 反轉vector
```c++
reverse(s.begin(), s.end());
```
- 刪除重複元素
```
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
```
### pair的使用
- 定義 : 一個同時可以存兩個值的容器
- 容易搞混的地方 : pair 是基本單位，map 是用 pair 組成的容器。需要存單對值就用 pair，需要存多對查找方便就用 map。
1 . **pair基本語法**
```c++
pair<int,int> p; // 宣告一個 pair，裡面放兩個 int
p.first = 10; // 第一個值
p.second = 20; // 第二個值
cout << p.first << " " << p.second << endl; // 輸出 10 20
```
2 . **pair裡面可以放不同型別**
```c++
pair<string, int> p;
p.first = "rain";
p.second = 20;
cout<<p.first<<" "<<p.second<<endl;
```
3 . **vector< pair >最常見的組合** :+1:
- 好處 : 方便存兩個值一組的資料
```c++
int main() {
int n, score;
cin >> n;
vector<pair<int,int>> v;
for(int i = 1; i <= n; i++){
cin >> score;
v.push_back({score, i}); // 第一個是分數，第二個是編號
}
// 按分數升序排序
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); i++){
cout << "編號 " << v[i].second << ", 分數 " << v[i].first << endl;
}
}
```
### 數學 GCD最大公因數/LCM最小公倍數/Primes質數 :+1:
``` c++
//gcd
int gcd(int a, int b){
while(b){
int t = a%b;
a = b;
b = t;
}
return a;
}
```
```c++
//lcm
long long lcm(long long a, long long b){//12 8
return a / gcd(a, b) * b;//
}
```
```c++
//Primes
bool isPrime(int x){
for(int i=2; i*i<=x; i++){//17
if(x % i == 0) return false;
}
return true;
}
```
* 進階 : 做質數表
```c++
bool prime[1000001] = true;
void build_prime_table(){//true是質數 false不是質數
prime[0] = false;
prime[1] = false;
for(int i=2; i*i<=1000000; i++){
if(prime[i]){//5
for(int j=i*i; j<=1000000; j+=i){//j=25
prime[j] = false;
}
}
}
}
```
### stack(後進先出) :+1:
- **定義** : 是一種資料結構，先進去的最後出來，後進去的先出來( ex : 疊盤子)
- `push(x)` : 放入一個資料
- `pop()` : 移除頂端資料(最後一筆資料)
- `top()` : 查看頂端資料(不拿走)
- `empty()` : 判斷是否為空
- **用法** : 爆字串
```
//aabbccdd → 刪掉相鄰相同 → 全部消失
for(char c : s){
if(!isempty() && st.top() == c){
st.pop();
}else st.push(c);
}
//stack 空 → Yes / stack 有剩 → No
```
```
//top的特性
st.push(3); // stack: 3
st.push(5); // stack: 3, 5
st.push(7); // stack: 3, 5, 7 (7 最上)
cout << st.top(); // 顯示 7
```
### queue(佇列) 先進先出
* 定義 : 是一種資料結構，先進去的先進來，像是排隊一樣
- `push(x)` : 把x加到最後
- `pop()` : 把最前面的拿掉
- `front()` : 看最前面的人是誰
- `back()` : 看最後面的人是誰
- `empty()` : 是否為空
- `size()` : 現在有幾個
```c++
//UVA 10935 – Throwing cards away
/*一個牌堆 1, 2, 3, ..., n
規則：
丟掉最上面的牌（queue.pop）
下一張放到下面（push(front), pop）*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n && n){
queue<int> q;
for(int i=1; i<=n; i++){
q.push(i);
}
cout << "Discarded cards: ";
int first = 1;
while(q.size() > 1){
if(first == 1){
cout << q.front();
first = 0;
}else{
cout << ", " << q.front();
}
q.pop();
q.push(q.front());
q.pop();
}
cout << "\nRemaining card: " << q.front() << endl;
}
}
```
### deque(Double-Ended Queue)雙端佇列
* 說明 : queue的加強版
- `push_back(x)` : 從後面加入
- `push_front(x)` : 從前面加入
- `pop_back()` : 從前面刪除
- `pop_front()` : 從前面刪除
- `front()` : 看最前面元素
- `back()` : 看後面元素
- `size()` : 看長度
- `empty()` : 判斷是否為空的
```c++
#include <bits/stdc++.h>
using namespace std;
int main(){
deque<int> q;
q.push_back(10);
q.push_front(20); // 20 10
q.push_back(30); // 20 10 30
cout << q.front() << endl; // 20
cout << q.back() << endl; // 30
q.pop_front(); // 10 30
q.pop_back(); // 10
cout << q.front() << endl; // 10
}
```
### priority_queue(優先佇列)
* 定義 : 最大堆(max heap) ， 取出的值都是最大值
- `push(x)` : 從後面加入
- `pop()` : 移除最大值
- `top()` : 查看最大值
- `empty()` : 是否是空的
- `size()` : 看長度
```c++
#include <bits/stdc++.h>
using namespace std;
int main(){
priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(30);
cout << pq.top() << endl; // 30 最大
pq.pop(); // 移除 30
cout << pq.top() << endl; // 10
}
```
### DP
##### 一維dp
* 外層`i` : 遍歷每一種硬幣
* 內層`j` : 遍歷可以組成的錢數
* 核心公式 : `dp[j] = dp[j] + dp[j-coin[i])`
```c++
//一維dp舉例
#include <bits/stdc++.h>
using namespace std;
int main() {
int coins[5] = {1, 5, 10, 25, 50}, n;
int dp[30001]={0};
dp[0]=1;
for(int i=0; i<5; i++){
for(int j=coins[i]; j<=30001; j++){
dp[j] += dp[j-coins[i]];
}
}
while(cin>>n){
if(dp[n] == 1) cout << "There is only 1 way to produce " << n << " cents change." << "\n";
else cout<<"There are "<<dp[n]<<" ways to produce "<<n<<" cents change."<<endl;
}
return 0;
}
```
##### 二維dp[i][j]
* 定義 : 用表格記錄「子問題的答案」，避免重複計算。
* ex :
- 🎒背包問題 :
- 維度1 : i = 第幾個物品
- 維度2 : j = 目前容量
- 最常共同子序列(LCS) :
- 維度1 : 字串A的前i個字母
- 維度2 : 字串B的前j個字母
- 區間DP
- 維度1 : 左端點
- 維度2 : 右端點
* **只要問題有2種範圍/狀態就是2D dp**
* 二維dp的通用模板 :
```c++
建立dp[][]陣列
設定初始值
for i 從 i 到 n :
for j 從 1 到 m :
dp[i][j] = 用 dp[i-1][?], dp[?][j-1], dp[i-1][j-1] 推出答案是dp[n][m]
```
- 背包問題範例 : (每件物品只能拿一次，容量有限，要拿出最大價值)
- n件物品
- 每件物品有`重量w[i]` & `價值v[i]`
- 背包容量`w`
```c++
dp[i][j] = 前 i 件物品，容量 j 時，能得到的最大價值
```
```c++
如果第 i 件物品的重量 w[i] > j :
dp[i][j] = dp[i-1][j]
如果裝得下 (w[i] <= j)：
不拿：dp[i-1][j]
拿： dp[i-1][j - w[i]] + v[i]
---> dp[i][j] = max( 不拿 , 拿 )
```
```c++
//範例
/*
3 5
2 3
3 4
4 5 ans(7)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, W;
cin>>n>>W;
vector<int> w(n+1), v(n+1);
for(int i=1; i<=n; i++) cin>>w[i]>>v[i];
vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
for(int i=1; i<=n; i++){
for(int j=1; j<=W; j++){
//不能拿這件(太重)
dp[i][j] = dp[i-1][j];
//可以拿
if(j >= w[i]){
dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
}
}
}
cout<<dp[n][W]<<enl;
return 0;
}
```
- LCS(Longest Common Subswquence) 最長共同子序列
- 給兩個字串 :
- `A`長度`n`
- `B`長度`m`
- 找到他們的共同子序列長度(不是連續，是subsequence)
```c++
dp[i][j] = A 的前 i 個字元和 B 的前 j 個字元的 LCS 長度
```
```c++
如果 A[i] == B[i]
dp[i][j] = dp[i-1][j-1] + 1
```
```c++
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
```
```c++
/*
ABCBDAB
BDCABA
ans(4)
共同子序列之一 : BCBA or BDAB
*/
#include <bits/stdc++.h>
using namesapce std;
int main(){
string A, B;
cin>>A>>B;
int n = A.size();
int m = B.size();
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(A[i-1] == B[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
}
```
### Binary Search
* 以生活舉例 : 自己最少需要多少錢買到一套電競設備
```yaml=
鍵盤 1500
滑鼠 800
椅子 3000
螢幕 4000
耳機 2000
```
- 如果有10000元，夠嗎?
- 夠，但可以少一點。
- 如果有1000元，夠嗎?
- 不夠，可以多一點。
- 不太可能0~10000元一個個慢慢試
- 所以我會猜一半 :
- 猜 5000 -> 夠
- 猜 2500 -> 不夠
- 猜 3750 -> 不夠
- 猜 4375 -> 不夠
- 猜 4687 -> 夠
- **這就是Binary Search找答案的原理**
### Greedy(貪心法)
* 核心定義 : 能塞就塞，能放就放
* 舉個例子 : 你有一台10公斤的行
```yaml=
7kg
2kg
6kg
4kg
5kg
```
* 問題 : 「行李箱最多 10kg 時，是否能全部塞完？如果不行，需要幾個箱子？」
- 箱子1 :
- 放 7kg --> OK
- 再放 2kg --> 9kg
- 再放 6kg --> 15kg 太大裝不下 --> 停下
- 箱子2 :
- 放 6kg --> OK
- 再放 4kg --> 10kg
- 再放 5kg --> 15kg 超過 --> 停
- 箱子3 :
- 放5 --> OK
* **每個箱子都塞到不能再塞，這就是Greedy**
```c++
//例子
#include <bits/stdc++.h>
using namespace std;
bool ok(int limit, int s[], int n, int k){
int cnt=1, now=0;
for(int i=0; i<n+1; i++){
if(now+s[i] > limit){
cnt++;
now=0;
}
now += s[i];
}
return cnt <= k+1;
}
int main(){
int n, k;
while(cin>>n>>k){
int s[10001]={0}, Max=0, sum=0;
for(int i=0; i<n+1; i++){
cin>>s[i];
sum += s[i];
Max = max(Max, s[i]);//每個箱子最大的容量(不能在更小了)
}
int left = Max, right = sum;
while(left < right){
int mid = (left + right) / 2;
if(ok(mid, s, n, k)) right = mid;
else left = mid+1;
}
cout<<left<<endl;
}
return 0;
}
```
### BFS (Breadth-First Search) 廣度優先搜尋
* 定義 : 將每一層的節點由左至右依序取出
* 用廣度優先搜尋的方式走訪的步驟為:
* 第1層 取出10
* 第2層 取出8, 11
* 第3層 取出5, 9 ,15
* 第4層 取出2, 13, 19
* 通常會用queue
### DFS (Depth-First-Search) 深度優先搜尋
* 定義 : 走到底
* PreOrder 前序 : 根節點 → 左節點 → 右節點
* InOrder 中序 : 左節點 → 根節點 →右節點
* PostOrder 後序 : 左節點 → 右節點 → 根節點
* 
* 差異
* dfs範例程式碼
```c++
void dfs(int num){
times++; // 我走過一個人了！
sum[num] = true; // 這個人「整體上」已經走過了
check[num] = true; // 這次走訪中也走過他
if (!check[sent[num]]) // 如果他的下一個還沒走到
dfs(sent[num]); // 就繼續往下一個走
}
```
Sign in with Wallet
Connect another wallet