C++ 算法Trick

笔记

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/ 快递分拣

时间复杂度

枚举

穷举所有可能的情况，循环枚举解空间

如果觉得文章对你有用，请随意赞赏

C++

C++ 算法Trick

https://www.idealx.cn/archives/cpp-trick

作者

爱丽丝

发布于

2024-02-29

更新于

2024-03-23

许可协议

CC BY 4.0