OJ常用函数/机试常用STL模板

  • 开发
  • 30

目录

机试涉及到的算法

排序算法，BFS，DFS，回溯法，打表法，双指针算法，贪心算法（背包问题、活动安排问题），动态规划（最大连续子序列和、LIS、LCS等等），压缩路径的并查集问题，dijkstra算法（最短路径），kruskal算法（最小生成树），树的前序中序后序转换及还原，二分图及图的着色问题，快速幂和快速乘算法，大整数/高精度运算，STL的运用（如vector、string、stack、queue的常见操作）

一、字符串

  1. 判断字符串中是否包含字符串
#include <iostream>
#include <string>
using  namespace  std;
int  main()
{
   
     string a= "abcdefghigklmn" ;
     string b= "def" ;
     string c= "123" ;
     string::size_type idx;
     
     idx=a.find(b); //在a中查找b.
     if (idx == string::npos) //不存在。
         cout <<  "not found\n" ;
     else //存在。
         cout << "found\n" ; 
     idx=a.find(c); //在a中查找c。
     if (idx == string::npos ) //不存在。
         cout <<  "not found\n" ;
     else //存在。
         cout << "found\n" ; 
     return  0;
}
  1. int 转 string
int val = 15;
// 使用 std 命名空间内的方法
string str = to_string(val);
  1. string 转 int
string str = "15";
// 转换为C字符串，然后利用 C 提供的函数 atoi 转换为 int 类型
int val = atoi(str.c_str())
  1. 在指定位置插入字符
string str = "abc";
int pos = 2;
// 在指定位置插入字符
str.insert(str.begin() + pos, 'd');
cout<<str<<endl; // 输出：abdc
  1. 在指定位置插入字符串
string str = "abc";
int pos = 2;
// 在指定位置插入字符串
str.insert(2, "de");
cout<<str<<endl; // 输出：abdec

二、vector

  1. 指定位置插入元素
#include <vector>
#include <iostream>
using namespace std;

int main()
{
   
    vector<int> digits = {
   1, 2, 3};
    for (int i = 0; i < digits.size(); i++)
    {
   
        cout << digits[i] << " ";
    }
    cout << endl;
    int pos = 1;
    digits.insert(digits.cbegin() + pos, 0);
    // digits = {1, 0, 2, 3}
    for (int i = 0; i < digits.size(); i++)
    {
   
        cout << digits[i] << " ";
    }
    return 0;
}

二、map

  1. 查找元素
// 判断 mp 中是否存在 key
if (mp.find(key) == mp.end()) {
   
    return -1;
}
  1. 插入/修改元素（关于通过下标访问map（或unordered_map）中不存在的元素，对容器的影响，可以参考：https://blog.csdn.net/myf_666/article/details/132192002）
// 更新哈希表
mp[key] = cur;
  1. 删除元素
mp.erase(key);
  1. 对于map和unordered_map，当我们采用下标运算符访问不存在的key值时，会先插入一个value（调用默认构造函数），然后返回。这样就会对原有变量造成破坏。如果我们不想拥有这种访问map或unordered_map导致的副作用，我们可以使用find操作，该操作不会对原有变量造成破坏。

三、set

  1. 添加元素
srcNames.insert(srcName);
srcNames.emplace(srcName); // 效率比insert更高一些

在这里插入图片描述

  1. 查找元素
opNames.find("*") == opNames.end()
  1. 合并两个集合
#include<algorithm>

set_union(roleSets.begin(), roleSets.end(),
	tmp.begin(), tmp.end(), 
	inserter(roleSets, roleSets.begin()));

四、queue

  1. 优先队列，默认是大根堆：
    priority_queue<int> girlsLike;
    priority_queue<int> boysLike;
  1. 如果想使用小根堆，在模板中添加参数，greater表示后面的元素要大于前面的：
    priority_queue<int, vector<int>, greater<int>> girlsLike;
    priority_queue<int, vector<int>, greater<int>> boysLike;

在使用小根堆来实例化自定义类型时，需要注意重载运算符>，重载<运算符会报错。示例代码如下：

struct Point
{
   
    int val;
    int x;
    int y;
    Point(int val, int x, int y) : val(val), x(x), y(y) {
   }
    // 重载>运算符，同时函数末尾注意添加const
    bool operator>(const Point &point) const
    {
   
        return this->val > point.val;
    }
};

greater是一个模板，关于这个模板的介绍可以参考：C++中的 greate/less 比较器模板的实现原理及作用：https://blog.csdn.net/myf_666/article/details/135374270

五、并查集

不带有路径压缩的并查集：

class UFSets {
   
public:
    vector<int> vec;

    UFSets(int sz) {
   
        vec = vector<int>(sz, -1);
    }
    int Find(int x) {
   
        while (vec[x] >= 0)x = vec[x];
        return x;
    }
    bool Union(int root1, int root2) {
   
        int r1 = Find(root1);
        int r2 = Find(root2);
        if (r1 == r2) {
   
            return false;
        }
        if (vec[r2] < vec[r1]) {
   
            vec[r2] = vec[r1] + vec[r2];
            vec[r1] = r2;
        }
        else {
   
            vec[r1] = vec[r1] + vec[r2];
            vec[r2] = r1;
        }
        return true;
    }
};

带有路径压缩的并查集：

// 加权并查集
class UFSets {
   
public:
    vector<int> parent;

    UFSets(int n) {
   
        parent = vector<int>(n);
        for (int i = 0; i < n; i++) {
   
            parent[i] = i;
        }
    }

    int Find(int x) {
   
        if (x != parent[x]) {
   
        	// 递归进行路径压缩
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }

    void Union(int x, int y) {
   
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX == rootY) {
   
            return;
        }
        parent[rootX] = rootY;
    }
};

五、cmath

#include<cmath>

里面角度的大小均为弧度制，如果是角度，需要进行转换 θ ∗ P I / 180 \theta*PI/180 θ∗PI/180

#define PI acos(-1.0)

函数相关功能如下：

在这里插入图片描述

六、读入数据

6.1 示例1

输入描述：
输入包括两个正整数a,b(1 <= a, b <= 1000),输入数据包括多组。

输出描述：
输出a+b的结果

输入例子：
1 5
10 20

输出例子：
6
30

代码：

#include <iostream>
using namespace std;

int main() {
   
    int a, b;
    while (cin >> a >> b) {
    // 注意 while 处理多个 case
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

6.2 示例2

输入描述：
输入第一行包括一个数据组数t(1 <= t <= 100)
接下来每行包括两个正整数a,b(1 <= a, b <= 1000)

输出描述：
输出a+b的结果

输入例子：
2
1 5
10 20

输出例子：
6
30

#include <iostream>
using namespace std;

int main() {
   
    int a, b;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
   
        cin >> a >> b;
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

6.3 示例3

输入描述：
输入包括两个正整数 a , b ( 1 < = a , b < = 1 0 9 ) a,b(1 <= a, b <= 10^9) a,b(1<=a,b<=109),输入数据有多组, 如果输入为0 0则结束输入

输入例子：
1 5
10 20
0 0

输出例子：
6
30

#include <iostream>
using namespace std;

int main() {
   
    int a, b;
    while (true) {
   
        cin >> a >> b;
        if (a == 0 && b == 0) {
   
            break;
        }
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

6.4 示例4

输入描述：
输入数据包括多组。
每组数据一行,每行的第一个整数为整数的个数n(1 <= n <= 100), n为0的时候结束输入。
接下来n个正整数,即需要求和的每个正整数。

输出描述：
每组数据输出求和的结果

输入例子：
4 1 2 3 4
5 1 2 3 4 5
0

输出例子：
10
15

#include <iostream>
using namespace std;

int main() {
   
    int a, b;
    while (true) {
    // 注意 while 处理多个 case
        int n;
        cin >> n;
        if (n == 0)break;
        int sum = 0;
        for (int i = 0; i < n; i++) {
   
            int tmp;
            cin >> tmp;
            sum += tmp;
        }
        cout << sum << endl;
    }
}
// 64 位输出请用 printf("%lld")

6.5 示例5

输入描述：
输入的第一行包括一个正整数t(1 <= t <= 100), 表示数据组数。
接下来t行, 每行一组数据。
每行的第一个整数为整数的个数n(1 <= n <= 100)。
接下来n个正整数, 即需要求和的每个正整数。

输出描述：
每组数据输出求和的结果

输入例子：
2
4 1 2 3 4
5 1 2 3 4 5

输出例子：
10
15

#include <iostream>
using namespace std;

int main() {
   
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
   
        int numberNum;
        cin >> numberNum;
        int sum = 0;
        for (int j = 0; j < numberNum; j++) {
   
            int tmp;
            cin >> tmp;
            sum += tmp;
        }
        cout << sum << endl;
    }
}
// 64 位输出请用 printf("%lld")

6.6 示例6

输入描述：
输入数据有多组, 每行表示一组输入数据。
每行的第一个整数为整数的个数n(1 <= n <= 100)。
接下来n个正整数, 即需要求和的每个正整数。

输出描述：
每组数据输出求和的结果

输入例子：
4 1 2 3 4
5 1 2 3 4 5

输出例子：
10
15

#include <iostream>
using namespace std;

int main() {
   
    int n;
    while (cin >> n) {
   
        int sum = 0;
        for (int i = 0; i < n; i++) {
   
            int tmp;
            cin >> tmp;
            sum += tmp;
        }
        cout << sum << endl;
    }
}
// 64 位输出请用 printf("%lld")

6.7 示例7

输入描述：
输入数据有多组, 每行表示一组输入数据。
每行不定有n个整数，空格隔开。(1 <= n <= 100)。

输出描述：
每组数据输出求和的结果

输入例子：
1 2 3
4 5
0 0 0 0 0

输出例子：
6
9
0

#include <iostream>
using namespace std;

int main() {
   
    int tmp;
    int sum = 0;
    while (cin >> tmp) {
   
        sum += tmp;
        if (cin.get() == '\n') {
   
            cout << sum << endl;
            sum = 0;
        }
    }
}
// 64 位输出请用 printf("%lld")

6.8 示例8

输入描述：
输入有两行，第一行n
第二行是n个字符串，字符串之间用空格隔开

输出描述：
输出一行排序后的字符串，空格隔开，无结尾空格

输入例子：
5
c d a bb e

输出例子：
a bb c d e

#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main() {
   
    string str;
    int n;
    cin >> n;
    vector<string> vec;
    for (int i = 0; i < n; i++) {
   
        cin >> str;
        vec.push_back(str);
    }

    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++) {
   
        cout << vec[i] << " ";
    }
}
// 64 位输出请用 printf("%lld")

6.9 示例9

输入描述：
多个测试用例，每个测试用例一行。
每行通过空格隔开，有n个字符，n＜100

输出描述：
对于每组测试用例，输出一行排序过的字符串，每个字符串通过空格隔开

输入例子：
a c bb
f dddd
nowcoder

输出例子：
a bb c
dddd f
nowcoder

#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main() {
   
    string str;

    vector<string> vec;

    while (cin >> str) {
   
        vec.push_back(str);
        if (cin.get() == '\n') {
   
            sort(vec.begin(), vec.end());
            for (int i = 0; i < vec.size(); i++) {
   
                cout << vec[i] << " ";
            }
            cout << endl;
            vec.clear();
        }
    }

}

6.10 示例10

输入描述：
多个测试用例，每个测试用例一行。
每行通过,隔开，有n个字符，n＜100

输出描述：
对于每组用例输出一行排序后的字符串，用’,'隔开，无结尾空格

输入例子：
a,c,bb
f,dddd
nowcoder

输出例子：
a,bb,c
dddd,f
nowcoder

#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main() {
   
    string str;

    vector<string> vec;
    while (cin >> str) {
   
        string cur;
        for (int i = 0; i < str.size(); i++) {
   
            while (str[i] != ',' && i < str.size()) {
   
                cur += str[i];
                i++;
            }
            vec.push_back(cur);
            cur = "";
        }
        sort(vec.begin(), vec.end());
        for (int i = 0; i < vec.size(); i++) {
   
            if (i == vec.size() - 1) {
   
                cout << vec[i] << endl;
            } else {
   
                cout << vec[i] << ",";
            }
        }
        vec.clear();
    }

}

6.11 示例11

数据范围：
0 < a , b < 2 × 1 0 10 0<a,b<2×10^{10} 0<a,b<2×1010

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M

输入描述：
输入有多组测试用例，每组空格隔开两个整数

输出描述：
对于每组数据输出一行两个整数的和

输入例子：
1 1
输出例子：
2

#include <iostream>
using namespace std;

int main() {
   
    long a, b; // 不要用 int a, b, 因为测试数据会越界，为了效果，所以这个题目故意不在题面说数据范围
    while (cin >> a >> b) {
    // 注意 while 处理多个 case
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

七、输入输出

  1. 控制输出位数：
#include <iomanip>
using namespace std;

int main(){
   
	double result = 3.1415926;
	std::cout << fixed << setprecision(3) << result << std::endl;
}
  1. 关掉缓冲区同步，提高输入输出效率
	//提高cin,cout的速度 
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  1. 将 endl 替换为 \n 可以提高效率。因为在插入换行符的同时，endl还会刷新缓冲区，使得输出字符立即显示到屏幕上，这一操作会造成较为昂贵的开销。在输入数据较小的情况下，区别不大，但如果需要大量输出换行的题目，时间提升很明显。

八、排序

  1. 排序主要利用sort函数，默认从小到大排
	vector<int> A(M, 0);
	for (int i = 0; i < M; i++) {
   		 // 朋友近视眼度数
		cin >> A[i];
	}
	sort(A.begin(), A.end()); // 从小到大
  1. 排序map，并自定义排序规则
	vector<pair<int,int>> HP(N);
	for (int i = 0; i < N; i++) {
    // 高度
		cin >> HP[i].first;
	}

	for (int i = 0; i < N; i++) {
    // 位置
		cin >> HP[i].second;
	}

	sort(HP.begin(), HP.end(), [&](pair<int, int> a, pair<int, int> b) {
   
		return a.second < b.second;
		});
  1. 从大到小排
	vector<int> A(M, 0);
	for (int i = 0; i < M; i++) {
   		 // 朋友近视眼度数
		cin >> A[i];
	}
	sort(A.begin(), A.end(), greater<int>()); // 从大到小，用greater<int>()

九、数学相关

  1. PI如何定义

通过下面这种反函数，来定义宏进行实现。

# define PI acos(-1)

十、大数的表示

在设置一些无限大的参数时，我们往往纠结于要设置多大。具体选择这两个数的原因参见博客：https://blog.csdn.net/tigercoder/article/details/70338623 和 https://blog.csdn.net/u010129448/article/details/37941123

int minVal = 0x3f3f3f3f;
int maxVal = -0x3f3f3f3f - 1;

或者，当所有情况的值都大于0，而且我们想要保存某个最大值的时候：

int maxVal = 0;

因为不会出现负数的情况嘛，所以没有必要考虑无穷小。

十一、IDE

VS2012中需要使用下面代码来停住窗口，查看结果。

system("pause");
阅读全部

相关推荐

  2. SQL常用函数

    2024-01-20 12:58:02       18 阅读

  4. hive sql常用函数

    2024-01-20 12:58:02       37 阅读

  5. SQL常用函数收藏

    2024-01-20 12:58:02       23 阅读

  7. SQL常用时间处理函数总结

    2024-01-20 12:58:02       39 阅读

  8. SQL之常用字符串函数

    2024-01-20 12:58:02       23 阅读

  9. sql sqlserver常用日期函数

    2024-01-20 12:58:02       21 阅读

  10. STL——常用算法

    2024-01-20 12:58:02       12 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-01-20 12:58:02       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-01-20 12:58:02       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-01-20 12:58:02       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-01-20 12:58:02       20 阅读

热门阅读

  2. 【卡梅德生物】如何制备纳米抗体?

    2024-01-20 12:58:02       29 阅读

  5. Git 的基本概念、使用方式及常用命令

    2024-01-20 12:58:02       37 阅读

  7. C++：通过ofstream写入二进制文件内容

    2024-01-20 12:58:02       37 阅读

  9. 代码随想录算法训练营第三十七天| 738.单调递增的数字、968.监控二叉树

    2024-01-20 12:58:02       31 阅读

  15. 2024年1月19日Arxiv最热CV论文：RAP-SAM: Towards Real-Time All-Purpose Segment Anything

    2024-01-20 12:58:02       33 阅读

  22. uniapp技术积累

    2024-01-20 12:58:02       26 阅读

  24. MySQL经典面试题

    2024-01-20 12:58:02       29 阅读

  29. kafka hang 问题记录

    2024-01-20 12:58:02       28 阅读