C++ 算法刷题 - 常用技巧汇总

定义变量

自带的宏常量

1
2
3
4
5
6
int N = INT_MAX; // 2147483647
int M = INT_MIN; // -2147483648
const int INF = 0x3f3f3f3; INF: // 66319347，在图论中通常用来代替最大值，防止运算过程中溢出
std::cout << "N: " << N << std::endl;
std::cout << "M: " << M << std::endl;
std::cout << "INF: " << INF << std::endl;

字符串及字符处理

字符串初始化

让字符串重复，利用构造函数来初始化

1
2
std::string str(10, 'h'); 
std::cout << str << std::endl; // 会输出10个h

字符串判断函数

isdigit(c) // 判断给定字符是否是数字字符

isalpha(c) // 判断字符是否是字母

isalnum(c) // 判断字符是否是字符或数字

tolower(c)// 转为小写

toupper(c) // 转为大写

transform(str.begin(), str.end(), str.begin(), ::tolower; // 所有字符转为小写

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
std::vector<char> res = {'a','b','c','5','6','7'};
int cnt = 0;
for(auto x : res) {
    if(isdigit(x)) {
        std::cout << (x - '0') << ' '; // 字符数字转整数,5,6,7
    }
    if(std::isalnum(x)) { // 是否是字母数字，res=6
        cnt++;
    }
}
std::cout << std::endl;
std::cout << "cnt: " << cnt << std::endl;

for(auto &x : res) { //使用 &x 可以通过引用修改原始容器中的元素
    if(isalpha(x)) {
        x = toupper(x); // x是引用
    }
    std::cout << x << ' '; // x: A B C 5 6 7
}
std::cout << std::endl;
for(auto t : res) std::cout << t << ' '; // 变为大写


std::string str1 = "TOM, jack";
transform(str1.begin(), str1.end(), str1.begin(), ::uplower); // 加头文件<algorithm>
std::cout << str1; // 都变为小写: tom, jack

字符串和数字间的转化

00.字符串转整数（秦九韶算法）

1
2
3
4
5
6
std::string str = "123456";
int res = 0;
for(int i = 0; i < str.size(); i++) {
    res = res * 10 + str[i] - '0';
}
std::cout << "res: " << res << std::endl; // int: 123456

应用题型：

【AcWing 4945. 比大小 - 进位制、秦九韶】 题解

【LeetCode 8. 字符串转换整数 (类atoi)】 题解

Ps:相关函数: to_string(num) 整型转字符串

01.stoi() 字符串转整数

int stoi( const std::string& str, std::size_t* pos = 0, int base = 10 );

pos: 可选参数，指向第一个无效字符位置的指针 base: 进制数, 默认是10

std::to_string(num)数字转字符串，包含double

1
2
3
4
int num = 100;
std::string str = std::to_string(num); // 数字转字符串
int n = stoi(str); // 字符串转整型，stol()转长整型
std::cout << "str: " << str << '\n' << "n: "  << n << std::endl;

02.atoi() C风格字符串转整数

int atoi(const char* str);

1
2
3
const char* str = " 41.9999";
int n  = std::atoi(str); // 只能处理简单的整数转换
std::cout << n << std::endl; // n: 41

03.atof() C风格字符串转浮点数

double atof(const char* str);

atof()会从字符串中解析出有效的浮点数，无法解析时，会返回0

1
2
3
const char* str = "  -2.45x6";
double f = std::atof(str);
std::cout << "f: " << f << std::endl; // f: 2.45

Ps:

atof()（只能处理以null结尾的C风格字符串（const char str*),

若是处理C++里的std::string，需要使用.c_str()方法获取其地址，然后在进行转换

代码示例，

1
2
3
std::string str = " -3.141/5";
double f = std::atof(str.c_str());
std::cout << "f: " << f << std::endl; // f: 3.141

04.str.c_str()用法

const CharT* c_str() const;

返回值，指向底层字符存储的指针。

s.c_str()函数,返回一个指向C字符串的指针常量, 内容与本string串相同.

1
2
3
4
5
6
std::string str = "hello";
const char* s = {};
s = str.c_str(); // const char* 类型
std::cout << "s: " << s << std::endl; // s: hello

printf("%s", str.c_str()); // 使用C风格的printf输出

c_str()返回的是一个临时指针，不能对其进行操作

代码示例，

1
2
3
4
5
6
// 正确用法
char c[10];
std::string str = "good morning";
// <cstring> 头文件
strcpy(c, str.c_str());	// 这样才不会出错，c_str()返回的是一个临时指针，不能对其进行操作
std::cout << c << std::endl; // c: good morning

【s.c_str()使用详情】

相关拓展: 取出数字的每一位

int t = x % 10; // 循环，从低位到高位取每一位数字
x /= 10;

代码示例，

1
2
3
4
5
6
7
8
9
10
11
int x = 45678;
std::vector<int> res;
while(x) { // 取出x的每位数字 ( 从低位到高位取)
    int t = x % 10;
    res.push_back(t);
    x /= 10;
}
reverse(res.begin(), res.end());
for(auto n : res) {
    std::cout << n << ' '; // 45678
}

**应用题型：

蓝桥杯 1245. 特别数的和 题解

知识点：【reserve() 字符串反转】

字符串按空格分隔

将字符串按空格进行分割，类似其他语言的split()方法

代码示例，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 需要引入头文件 <sstream>
std::string str = "hello I  am fine  hhh";
std::stringstream ss(str);
std::string s;

int cnt = 0;
while(ss >> s) { // 可忽略多个空格
    cnt++; // 统计分隔的数量
    std::cout << s << std::endl;
}
std::cout << cnt << std::endl;
// 输出结果为，
hello
I
am
fine
hhh
5

相关题型，

【AcWing 770. 单词替换 】 【题解】

字符串按格式拆分

可以按自定义格式进行拆分

void* memcpy(void* dest, const void* src, std::size_t count);

用于将src指针指向的内存区域的数据复制到dest指针指向的内存区域，复制的字节数由count指定。注意memcpy不会添加末尾空字符

int sscanf(const char* str, const char* format, ...);

从一个字符串中读取数据并根据指定的格式进行解析。

代码示例，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::string a = "12:36:40";
std::string b = "45s67,55";

char str[100];
memcpy(str, a.c_str(), strlen(a.c_str())); // strlen() 需引入<cstring>
int u,v,w;
sscanf(str, "%d:%d:%d", &u, &v, &w); // 按指定格式从字符数组中来读
std::cout << u << ' ' << v << ' ' << w << '\n'; // 12 36 40

char str1[100];
memcpy(str1, b.c_str(), strlen(b.c_str()));
int x,y,z;
sscanf(str1, "%ds%d,%d", &x, &y, &z);
std::cout << x << ' ' << y << ' ' << z << '\n'; // 45 67 55

另外一种写法，

``istringstream` 自动截取分隔符号

需要注意的是，将std::string类型的字符串转换成char类型的字符数组

并使用sscanf的方式不是C++中推荐的做法。C++提供了更加安全和便捷的方式来解析字符串，

例如使用std::istringstream，这样可以避免手动内存管理和潜在的缓冲区溢出问题

1
2
3
4
5
6
std::string c = "1s2-4,5?99";
std::istringstream iss(c); // 需引入<sstream>
char delimiter;
int x,y,m,n,q;
iss >> x >> delimiter >> y >> delimiter >> m >> delimiter >> n >> delimiter >> q; // iss会自动截取分隔符号(空格不行)
std::cout << x << ' ' << y << ' ' << m << ' ' << n << ' ' << q << '\n'; // 1 2 4 5 99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
std::string str = "hello I am fine hhh";
std::stringstream ss(str); // 需引入头文件 <sstream>
std::string s;

int cnt = 0;
while(ss >> s) {
    cnt++; // 统计读取串的数量
    std::cout << s << std::endl;
}
std::cout << cnt << std::endl;

// 输出结果为
hello
I
am
fine
hhh
5

利用字符串四舍五入保留小数

在C++语言中，**printf函数本身并不提供四舍五入的功能。**

printf是一个格式化输出函数，用于将数据按照指定格式输出到标准输出或其他输出流中，但它并不会对数据进行四舍五入操作。

方法一：利用字符串

sprintf()函数是C语言标准库中的一个函数，用于将格式化的数据写入到字符串中。

1
2
3
4
5
char str[10];
double num = 123.456;
sprintf(str, "%.2f", num);
std::string s = str; // 转为字符串，会有自动的隐式类型转换：string(const char* s);
std::cout << s << std::endl; // 结果：123.3

方法二：利用库函数

使用头文件中的std::fixed 和 std::setprecision ,来指定保留的小数位

1
2
3
4
5
// 需要引入头文件 <iomanip>
double num = 3.14159;
int k = 3; // 设置要保留的小数位数

std::cout << std::fixed << std::setprecision(k) << num << std::endl; // 结果： 3.142

迭代器的二分

// 一般升序使用

lower_bound(nums.begin(), nums.end(), 44) - nums.begin(); // 用于查找大于等于给定值的第一个元素

upper_bound(nums.begin(), nums.end(), 55) - nums.begin(); // 用于查找大于给定值的第一个元素

代码示例，

1
2
3
4
5
6
7
8
9
std::vector<int> nums{1,2,34,44,55,66};
// 第一个大于等于目标值的迭代器位置
int k = lower_bound(nums.begin(), nums.end(), 44) - nums.begin(); // 下标为3

// 找到第一个大于目标值的迭代器位置
int m = upper_bound(nums.begin(), nums.end(), 55) - nums.begin(); // 下标为5 ， 查66小标为6

std::cout << "k: " << k << std::endl;
std::cout << "m: " << m << std::endl;

大根堆和小根堆

1
2
3
4
5
6
7
8
9
10
11
priority_queue<int> pq; // 默认是大根堆
priority_queue<int, vector<int>, greater<int>> pq; // 定义成小根堆的方式

// 可支持以下操作
#include <queue> // 引入头文件
size()
empty()
push()  插入一个元素
top()  返回堆顶元素
pop()  弹出堆顶元素
q = queue<int>(); 初始化队列 相当于clear

代码示例，

【洛谷 模拟堆操作 - 模板题】，STL实现小根堆的增删改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> heap; // 定义小根堆
    
    int n, op;
    scanf("%d", &n);
    while(n--) { 
        scanf("%d", &op);
        if(op == 1) {
            int x;
            scanf("%d", &x);
            heap.push(x); // 插入元素
        }
        else if(op == 2) {
            printf("%d\n", heap.top()); // 输出堆顶元素
        }
        else {
            heap.pop(); // 弹出栈顶元素
        }
    }
    return 0;
}

相关应用，

【洛谷 模拟堆操作 - 模板题】

【剑指 - Offer 40. 最小的k个数】 【题解】

【LeetCode 47. 前 K 个高频元素】 【题解】

【AcWing 堆排序 - 模板题】 【题解】

【AcWing 模拟堆 - 模板题】 【题解】

快速初始化数组

memset(), 按字节来初始化元素的值或清空数组，常用于图论题

1
2
3
4
// 注意需要包含头文件 <cstring>
memset(nums, 0, sizeof nums); 
memset(nums, -1, sizeof nums);
memset(nums, 0x3f, sizeof nums);

bitset 压位

自己目前还没遇到过这类题型，可能是考察的少(应该是刷题少了)，后续有做到类似的题再补充

1
2
3
4
5
6
// 下面的功能是将给定的32位无符号整数（uint32_t）表示的数字的二进制位反转，并返回反转后的新数字。
uint32_t reverseBits(uint32_t) {
    string s = bitset<32>(n).to_string();
    reverse(s.begin(), s.end());
    return bitset<32>(s).to_ulong()
}

一些C++11新特性

1
2
3
4
auto p = new ListNode(); // auto，会自动推断返回的类型
Node* pre = nullptr; // 用nullptr代替NULL
unordered_map<int, int> map; // 哈希表， 内部无序
unordered_set<int> st; // 无序集合

自定义排序规则

结构体排序

代码示例，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <algorithm>

struct node{
    int a, b;
    bool operator < (const node &_node) const { // 重载小于号，自定义升序排列
        if(a != _node.a) return a < _node.a; // 按第一关键排
        return b < _node.b; // 第一关键字相等按第二关键字排
    }
};

int main() {

    std::vector<node> arr;
    arr.push_back({1,3});
    arr.push_back({1,2});
    arr.push_back({2,5});
    arr.push_back({2,1});
    sort(arr.begin(), arr.end()); // 按照自定义排序规则
    for(auto node : arr) {
       std::cout << node.a << ' ' << node.b << '\n';
    }
    return 0;
}

// 结果为
1 2
1 3
2 1
2 5

类似用法，

【文档 结构体排序的四种方法】

优先队列自定义排序

代码示例，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <queue>


struct node{
    int a, b;
    // 注意，优先队列的排序是相反的，这里指a大的排在前面，a相同时，b大的排前面
    bool operator < (const node &_node) const { // 重载小于号，这里实际是一个降序序列
        if(a != _node.a) return a < _node.a; // 按第一关键排
        return b < _node.b; // 第一关键字相等按第二关键字排
    }
};

int main() {

    std::priority_queue<node> heap; // （优先队列默认是大根堆）自定义排序规则，这里维护的是一个大根堆
    heap.push({1,3});
    heap.push({1,2});
    heap.push({2,5});
    heap.push({2,1});

    while(!heap.empty()) {
        std::cout << heap.top().a << ' ' << heap.top().b << '\n'; // 这样输出的结果是降序排列的，是大根堆
        heap.pop();
    }
    return 0;
}

// 结果为，
2 5
2 1
1 3
1 2

类似题型，

【LeetCode 47. 前 K 个高频元素】 【题解】

pair二元组关键字排序

pair 默认对first升序，当first相同时对second升序

相关题型，

【AcWing 3425. 小白鼠排队】 【题解】

【AcWing 3451. 字符串排序II】 【题解】

sort()自定义排序，需重载比较函数

sort()常规用法，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
std::vector<int> res = {4,92,1,-1,4};
sort(res.begin(), res.end()); // 默认升序排列
for(auto x : res) {
    std::cout << x << ' ';
}
std::cout<<'\n';

// 两种降序排列写法
sort(res.rbegin(), res.rend()); // 降序排列写法
for(auto x : res) {
    std::cout << x << ' ';
}
std::cout<<'\n';

sort(res.begin(), res.end(), std::greater<int>()); // 另一种写法
for(auto x : res) {
    std::cout << x << ' ';
}
std::cout<<'\n';

// 输出结果为：
-1 1 4 4 92
92 4 4 1 -1
92 4 4 1 -1

其他用法，

【文档 C++ 二维vector排序(sort用法)】

其他一些常用库函数

求最值，max,min

需要引入```头文件, 使用初始化列表形式来传参

1
2
3
4
int ma = std::max({99,1,30,0}); // 比较多个数大小，可以采用初始化列表的方式
int mi = std::min({1,-33,10});
std::cout << ma << std::endl;
std::cout << mi << std::endl;

查找最值元素下标，max_element min_element

1
2
3
int a[]={1,4,3,2,99};
std::cout << std::max_element(a,a+5)-a << std::endl; // index: 4
std::cout << std::min_element(a,a+5)-a << std::endl; // index: 0

求排列，prev_permutation next_permutation

prev_permutation函数是生成给定序列的上一个较小的排列。

next_permutation函数是求下一个全排列。

相关应用，

【prev_permutation函数】

【AcWing 51. 数字排列】

好了，暂时先收录这些，有新内容了在抽空更新整理吧

….

参考资料

【文档 C++ 刷题常用技巧】

【视频 C/C++常用刷题技巧】

【视频 C++ 那些写起来简单方便的函数】