（筆記）C++算法技巧

C++ 算法 Trick

萬能頭文件#

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    // 請在此輸入您的代碼
    
    return 0;
}

取消同步流#

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

getline#

getline(cin, string);

string 類的 c 語言風格字符串#

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    char buffer[100];
    scanf("%s", buffer);
    string str(buf);
    printf("str = %s\n", str.c_str());
    
    return 0;
}

str.c_str();

// 獲取字符串長度
str.length();
// 拼接字符串
string res1 = str1 + "," + str2;
string res2 = str1.append(",").append(str2);
// 字符串查找
str.find();
// 字符串替換
// 子串起始位置，子串長度，替換後的字符串
str.replace(7, 5, "xxxxx");
// 提取字符串 不要越界
str.substr(7, 5);
// 字符串比較
str1.compare(str2);

常見的遍歷 string 的方法#

循環枚舉下標

for(int i=0;i < s.length(); ++i) cout << s[i];

auto 枚舉

排序 sort#

// sort(起始地址，結束地址的下一位， *比較函數)
// 比較函數默認升序
// 自定義比較函數
bool cmp(const int &u, const int &v){
    // 寫成 int u, int v也可以
    return u > v;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // init v
    vector<int> v = {5,1,3,9,11};
    // 對數組進行排序，降序排列
    sort(v.begin(), v.end(), cmp);
    // 輸出
    for(int i=0; i < v.size(); ++i){
        cout << v[i] << ' ';
    }
}
// 使用lambda表達式自定義比較函數
sort(v.begin(), v.end(), [](const int &u, const int &v)
{
    return u > v;
});
// 結構體自定義比較函數
struct Node
{
    int u, v;
    bool operator < (const Node &m)const{
        return u == m.u ? v < m.v : u < m.u;
    }
}
// 跟空格和跟回車的技巧
for(int i = 1; i <=n; i++){
    // 正序輸出
    cout << a[i] << " \n"[i == n];
}

最值查找#

min(a, b);
min({1,2,3,4})=1;
max(a, b);

min_element(st, ed); // 返回最小的那個值的地址
max_element(st, ed); //
// 示例
vector<int> v = {5, 1, 3, 9, 11};
cout << *max_element(v.begin(), v.end()) << '\n';

ntn_element(st, k, ed); // 部分排序
// k處於正確位置 前面比它小 後面比它大
// https://www.lanqiao.cn/problems/497/learning/

二分查找#

只能對單調數組進行查找

// binary_search函數
// 用於在已排序的序列（數組或容器vector）中查找特定元素。
vector<int> numbers = {1, 3, 5, 7, 9};
int target = 5;
// 使用binary_search查找目標
bool found = binary_search(numbers.begin(), numbers.end(), target);

lower_bound & upper_bound

// 前提：數組必須為非降序
// lower_bound(st, ed, x)返回地址[st, ed)中第一個大於等於x的元素的地址。
// upper_bound(st, ed, x)返回地址[st, ed)中第一個大於x的元素的地址。
// 如果不存在則返回最後一個元素的下一個位置，在vector中即end()
vector<int> v = {5, 1, 7, 3, 10, 18, 9};
sort(v.begin(), v.end());
for(auto &i : v) cout << i << ' ';
cout << '\n';
// 找到數組中第一個大於等於8的元素的位置
cout << (lower_bound(v.begin(), v.end(), 8) - v.begin()) << '\n';
// https://www.lanqiao.cn/problems/1389/learning/

大小寫轉換#

// islower/isupper函數 檢查char類型是否為小寫或大寫字幕
#include <cctype>
// tolower/toupper函數
char ch1 = 'A';
char lowercaseCh1 = tolower(ch1);

全排列#

next_permutation () 函數

vector<int> nums = {1, 2, 3};

cout << "Initial permutation: ";

for(int num : nums){
    cout << num << " ";
}
cout << '\n';

// 生成下一個排序 next_permutation返回true/false
while (next_permutation(nums.begin(), nums.end())){
    cout << "Next permutation: ";
    for(int num : nums){
        cout << num << " ";
    }
    cout << endl;
}

prev_permutation () 函數

vector<int> nums = {3, 2, 1};

cout << "Initial permutation: ";

for(int num : nums){
    cout << num << " ";
}
cout << '\n';

// 生成上一個排序 prev_permutation返回true/false
while (prev_permutation(nums.begin(), nums.end())){
    cout << "Next permutation: ";
    for(int num : nums){
        cout << num << " ";
    }
    cout << endl;
}

使用搜索 / DFS 的方法會使用全排列的方法

其他庫函數#

memset(void* ptr, int value, site_t num)#

設置內存塊值的函數 #include <cstring>

void* memset(void* ptr, int value, site_t num)

ptr 指向要設置值的內存塊的指針

value 要設置的值通常是一個整數

num 要設置的字節數

memset(arr, 0, sizeof(arr)); //初始化一個數組arr

memset () 函數對於非字符類型的數組可能會產生未定義行為。
在處理非字符類型的數組時，更好使用 C++ 中的其他方法，如循環遍歷來初始化數組。
memset 會將每個 byte 設置為 value。

int main(){
    int a[5];
    memset(a, 0, sizeof(a));
    for(int i = 0; i < 5; i++){
        // cout << bitset<32>(a[i]) << '\n';
        cout << a[i] << '\n';
    }
    return 0;
}

swap(T &a, T &b)#

交換

std::swap(a, b);

reverse(BidirIt first, BidirIt last)#

#include <algorithm>
template(class BidirIt)
void reverse(BidirIt first, BidirIt last);

將[first, last)反轉

reverse(vec.begin(), vec.end());

unique(ForwardIt first, ForwardIt last)#

#include <algorithm>
template(class ForwardIt)
ForwardIt unique(ForwardIt first, ForwardIt last)

int main(){
    vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5};
    auto it = unique(vec.begin(), vec.end()); // 去除相鄰重複元素
    vec.erase(it, vec.end()); // 刪除了重複的元素
    
    for(int num : vec) {
        cout << num << " ";
    }
    cout << '\n';
    
    return 0;
}

STL 庫#

pair 對值#

pair(const T1& x, const T2& y);
// 表示一對值的組合 將兩個值組合在一起，並進行傳遞、存儲和操作
pair<int, double> p1(1, 3.14);
pair<char, string> p2('a', "Hello")
cout << p1.first << ", " << p1.second << endl;

pair 的嵌套：
將一個 pair 對象作為另一個 pair 對象的成員

pair 自帶排序規則，按照 first 成員進行升序排序

vector<pair<int, int>> vec;
vec.push_back(make_pair(3, 2));
vec.push_back(make_pair(1, 4));
vec.push_back(make_pair(2, 1));

sort(vec.begin(), vec.end());

for (const auto& p : vec) {
    cout << p.first << ", " << p.second << endl;
}

vector 動態數組#

動態數組容器存儲一系列相同類型的元素

#include <vector>
vertor<T> vec;

// 元素訪問: 0~size()-1
// 元素增刪: push_back() pop_back() insert() erase()
// 容器大小管理: size() empty() resize()
// 迭代器: begin() end()

vector<int> vec = {10, 20, 30};
for(auto it = vec.begin(); it != vec.end(); ++it){
    cout << *it << " ";
}

sort(vec.begin(), vec.end());

// 排序去重
vector<int> vec = {10, 20, 30};
sort(vec.begin(), vec.end());
auto last = unique(vec.begin(), vec.end());
vec.erase(last, vec.end());
for(const auto& num : vec){
    cout << num << " ";
}

list 列表#

用得很少

雙向鏈表

list<T>

stack 堆疊#

後進先出的數據結構

#include <stack>
stack<T>

// 常用函數
push(x) // 堆疊頂插入元素x
pop() // 彈出堆疊頂元素
top() // 返回堆疊頂元素
empty() // 檢查堆疊是否為空
size() // 返回堆疊中元素的個數
// stack不能遍歷

queue 隊列#

//queue
//priority_queue優先隊列
//deque雙端隊列

//queue FIFO
push(x)
pop()
front()
back()
empty()
size()

https://www.lanqiao.cn/problems/1113/learning/

//priority_queue優先隊列 默認從大到小排列
1. push()：將元素插入優先隊列。插入後會自動按照優先級重新排列。
2. pop()：彈出隊列頂部的元素。這將移除隊列中優先級最高的元素。
3. top()：返回隊列頂部（即優先級最高）的元素，但不會將其從隊列中移除。
4. size()：返回隊列中的元素數量。
5. empty()：如果隊列為空，則返回 true；否則返回 false。

struct Compare{
    bool operator()(int a, int b) {
        return a > b;
    }
}
int main(){
    priority_queue<int, vector<int>, Compare> pq;
}
// 或
// priority_queue<int, vector<int>, greater<int>> pq;

//deque雙端隊列
push_back(x)
push_front(x)
pop_back()
pop_front()
front()
back()
empty()
size()
clear()

set 集合#

// set集合 默認升序排序
// set內部實現使用紅黑樹存儲元素
// set不允許重複元素
insert()
erase()
find()
lower_bound()
upper_bound()
size()
empty()
clear()

// 更改排序方法 1
set<int, greater<int>> mySet;
// 2
struct MyCompare(){
    bool operator()(const int& a, const int& b) const {
        // 自定義比較邏輯
        return a > b;
    }
}
int main(){
    set<int, myCompare> mySet;
}

// multiset多重集合 允許存儲重複的元素

// unordered_set無序集合

map 鍵值對#

map()
// 根據key來排序
insert(K, V)
erase(key)
find(key)
count(key)

// 多個相同的鍵
multimap()

// 無序
unordered_map()

小結#

https://www.lanqiao.cn/problems/3226/learning/ 寶藏排序2
https://www.lanqiao.cn/problems/1624/learning/ 小藍吃糖果
https://www.lanqiao.cn/problems/2490/learning/ 小藍的括號串1
https://www.lanqiao.cn/problems/1531/learning/ 快遞分揀

時間複雜度#

枚舉#

窮舉所有可能的情況，循環枚舉解空間

模擬#

遞歸#

進制轉換#

前綴和#

差分#

差分的原理和特點

對於一個數組a[]，差分數組diff[]的定義是：

diff[i] = a[i] - a[i-1]

對差分數組做前綴和可以還原為原數組：

diff[1] = a[1]
diff[2] = a[2] - a[1]
diff[3] = a[3] - a[2]
...
diff[n] = a[n] - a[n-1]

差分的實現

跑一遍 O (n) 的循環即可，建議a[0]=0，下標從 1 開始。