c++笔试题常用技巧

C++笔试输入输出

牛客网常用头文件

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

函数	解释
`cin>>`	遇到空格和换行符自动停止读入，下次读入自动跳过，读取后面的字符
`cin.get()`	读入字符，包括换行符`'\n'`和空格`' '`
`getline(cin, str)`	读取整行数据到`str`中
`cin.getline(char*, int)`	接收字符串储存到char*中，长度为n可以接受空格
`char a; cin.get(a)`	`a`中可以储存被`cin`丢弃的换行符

cin>>输入的数据不包含空格和回车，空格和回车会存入到cin的缓冲区中
如果想拿到输入的空格和回车，通过cin.get()获得

输入T组数据

int main() {
    int T;
    cin >> T;
    while (T--) {
        //code
    }
}

输入2个数字

输入：两个正整数a, b

1 5

10 20

输出：a + b 结果

6

30

int main() {
    int a, b;
    while(cin >> a >> b) {
        cout << a + b << endl;
    }
    return 0;
}

单组数据，已知有多少个数据，数据长度已知，一般用空格分隔。

int main() {
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
}

多组数据，已知有多少个数据，数据长度已知

int main() {
	int n, m;
    cin >> n >> m;
    vector<vector<int>> nums(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> nums[i][j];
        }
    }
}

单组数据，未告知多少个数据，数据长度未知，用逗号或空格隔开的数据

法1：

输入：用空格隔开每一个数据（逗号，分号同理）

123 456 789

int main() {
    vector<int> vec;
    int tmp;
    while (cin >> tmp) {
        vec.push_back(tmp);
        if (cin.get() == '\n') break;//只处理一行
    }
    
    for (auto c : vec) {
        cout << c << endl;
    }
}

输入：用空格隔开每一个数据，数据有多行

123 456 789

321 654 987

int main() {
    vector<vector<int>> vec;
    vector<int> path;
    int tmp;
    while (cin >> tmp) {
        path.push_back(tmp);
        if (cin.get() == '\n') {
            vec.push_back(path);
            path.clear();
            continue;
        }
        //vec.push_back(path);
    }
    
    for (auto c : vec) {
        for (auto d : c) {
            cout << d << endl;
        }
    }
}

法2：构造split函数，指定分隔符，对字符串进行切片

vector<int> split(string str, string pattern) {
    int pos = 0;
    vector<int> res;
    str += pattern;
    int size = str.size();
    for (int i = 0; i < size; i++) {
        pos = str.find(pattern, i);
        if (pos < size) {
            string s = str.substr(i, pos - i);
            res.push_back(stoi(s));
            i = pos + pattern.size() - 1;
        }
    }
    return res;
}

int main() {
    string input;
    getline(cin, input);
    //input = "7 17 27 35 8 49 50";
    vector<int> vec = split(input, " ");
    for (auto c : vec) {
        cout << c << endl;
    }
    
    string input;
    cin >> input;
    //input为"123, 456, 756"
    vector<int> vec = split(input, ",");
}

常用数据结构与函数

map与set的使用

初始化：
- 对于set：直接初始化set<int> myset={0,1,2}; 或者把vector复制过来set<int> myset(v.begin(),v.end());
- 对于map：map<int,int> mymap={{0,1},{2,3},{4,5}}
插入：
- 对于set：myset.insert(888);
- 对于map：mymap.insert(make_pair(6,7));or, mymap.insert(pair<int ,int>(6,7));or, mymap.insert{6,7}

成员函数	功能
begin()	返回指向头部的迭代器
end()	返回指向末尾的迭代器
empty()	如果为空则返回 true
find(val)	查找一个值为val的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，返回指向end() 的迭代器。
count(val)	返回指定元素val出现的次数
insert()	向容器中插入元素
erase()	删除容器中存储的一个元素
size()	返回容器中元素的个数
clear()	清空容器中所有的元素，即令容器的 size() 为 0
lower_bound(val)	返回一个指向当前容器中（key）第一个大于或等于 val 的元素的双向迭代器。
upper_bound(val)	返回一个指向当前容器中（key）第一个大于 val 的元素的迭代器。

queue与stack的使用

queue成员函数

成员函数	功能
empty()	如果 queue 中没有元素的话，返回 true
size()	返回 queue 中元素的个数
front()	返回 queue 中第一个元素的引用
back()	返回 queue 中最后一个元素的引用
push(const T& obj)	在 queue 的尾部添加一个元素的副本。调用底层容器的成员函数 push_back() 。
emplace()	在 queue 的尾部直接添加一个元素。
push(T&& obj)	以移动的方式在 queue 的尾部添加元素。调用底层容器的具有右值引用参数的成员函数 push_back()
pop()	删除 queue 中的第一个元素。

stack成员函数

成员函数	功能
empty()	当 stack 栈中没有元素时，该成员函数返回 true
size()	返回 stack 栈中存储元素的个数
top()	返回一个栈顶元素的引用，类型为 T&。如果栈为空，程序会报错。
push(const T& val)	先复制 val，再将 val 副本压入栈顶。调用底层容器的 push_back() 函数。
push(T&& obj)	以移动元素的方式将其压入栈顶。调用底层容器的有右值引用参数的 push_back() 函数。
pop()	弹出栈顶元素。

stack 和queue 没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

priority_queue的使用

优先队列具有与队列相似的操作：top()返回队首元素、pop()弹出队首元素、push()插入至队尾并排序。优先队列在内部添加了一个排序。其模板有3个参数：priority_queue< type, container, function >，type是存放的数据类型，container是实现优先队列的底层容器（一般都是vector<int>），function是元素之间的排序方式。

大顶堆（降序队列）

priority_queue<int> a; //缺省情况下同下面定义

priority_queue<int, vector<int>, less<int>> a;
小顶堆（升序队列）

priority_queue<int, vector<int>, greater<int>> c;
常常把pair<int,int>作为数据类型存放进priority_queue里面，这时排序的规则就是先比较第一个元素，如果第一个元素相等再比较第二个元素。
对于自定义类型存放进priority_queue，那么仿函数function需要自己写。

具体写法定义一个类，里面定义bool operator()(xxx,xxx){return a.x<b.x;}

STL常用算法

交换swap()

vector常用（交换容器中各元素的内存地址，并不是交换各个元素变量所存储的值）。

注意string是个例外，对string调用swap会导致迭代器、引用和指针失效

用法为：swap(vec1,vec2);
逆序reverse()

vector, string 常用，反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），无返回值。

用法为reverse(str.begin(),str.end());
统计count()

统计某一值在一定范围内[first,last)出现的次数。

比如int num = count(s.begin(),s.end(),'a');

排序sort()

sort (first, last) 对容器或普通数组中[first, last)范围内的元素进行排序，默认进行升序排序。

is_sorted (first, last) 检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序。

sort(vec.begin(), vec.end(), cmp) 自定义比较函数cmp

bool mycomp(int i, int j) {
    return (i > j);
}

int main() {
    std::vector<int> vec{ 32, 71, 12, 45, 26, 80, 53, 33 }
    //降序排列，通过自定义比较规则进行排序
    sort(vec.begin(), vec.end(), mycomp);
    //降序排列，利用lambda函数
    sort(vec.begin(), vec.end(), [&](int& i, int& j){return i > j;});
}

自定义结构体排序：

struct myData {
    int a, b;
    myData(int a_, b_) : a(a_), b(b_) {}
};
//自定义排序，按照a的大小，降序排列
class cmp {
public:
	bool operator()(const myData& data1, const myData& data2) const{
        return data1.a > data2.a;
    }    
};

int main() {
    set<myData, cmp> myset;
    myset.insert(myData(1, 100));
    myset.insert(myData(2, 200));
    myset.insert(myData(3, 300));
    for (auto c : myset) {
        cout << c.a << endl;
    }
}

二分查找函数：

lower_bound(vec.begin(), vec.end(), target)寻找vec数组中大于等于target的第一个数，返回其迭代器。

Upper_bound()则是寻找第一个大于target的数。
全排列函数

next_permutation()寻找下一个排列组合，prev_permutation()为上一个。

当 next_permutation() 返回 false 时，循环结束，表明到达最小排列。这样恰好可以生成序列的全部排列。
1
2
3
4
5
string str = "1234";
sort(str.begin(), str.end());
do {
cout << str << endl;
} while (next_permutation(str.begin(), str.end()));
原地删除erase()

对于string：
- erase(pos,n); 删除从下标pos开始的n个字符，比如erase(0,1)就是删除第一个字符。
- erase(position); 删除postion处的一个字符（position是一个string类型的迭代器）。
- erase(first,last); 删除从first到last之间的字符（first和last都是迭代器），注意是左闭右开。
对于map：
- mymap.erase(key)，会按key来删除map中对应的键值对。
- mymap.erase(position)，position为迭代器。
- mymap.erase(first,last)，删除迭代器表示的范围。
子字符串substr()

string sub=s.substr(pos);复制从下标pos开始的一直到结尾的字符串为新的sub子串。

string sub=s.substr(pos,n)；复制从下标pos开始的n个字符。
技巧：字符与数字的转换
- 字符char 转为数字int，利用str[0]-‘0’
- 数字int 转为字符char，利用(7+'0')
- 特殊字符char 转为 int，比如要把'a'转为0，'d'转为3。利用ASICII码，’a’的ASICII码为97，所以(int)str[2]-97
- 字符串string 转为 int，atoi()/stoi()函数
- 整数int 转为字符串string，to_string(value)函数