记录用，迅速复习。

1.关于c++中的sort()函数

  • STL中提供的sort算法有个限制，利用sort算法只能对序列容器进行排序，如vector，list，deque等。若要对map容器进行value排序，方法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//把map中的key值和value值分别转存到一个pair类型的vector中，在对vector按照一定的规则排序即可。这样的方法对值一样的情况也能够使用。
int cmp(pair<string, int> x, pair<string, int> y){ 
    return x.second > y.second;
}    
    
int main(){  
	vector<pair<string,int>> tVector;  
	sort(tVector.begin(), tVector.end(), cmp);
	for(int i = 0; i < tVector.size(); i++)  
		cout<< tVector[i].first << ": " << tVector[i].second << endl;  
	return 0;  
}

//注意：若要将map中的元素转化为pair，可调用make_pair()函数
for (auto curr = tMap.begin(); curr != tMap.end(); curr++)   
		tVector.push_back(make_pair(curr->first, curr->second));
  • c++使用sort自定义函数cmp能够方便地解决一些排序问题（尤其是多重排序/结构体）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
struct stu { // 定义一个结构体stu，number表示学号，score表示分数
    int number;
    int score;
}
bool cmp(stu a, stu b) { // cmp函数，返回值是bool，传入的参数类型应该是结构体stu类型
    if (a.score != b.score) // 如果学生分数不同，就按照分数从大到小排列
        return a.score > b.score;
    else // 如果学生分数相同，就按照学号从小到大排列    
        return a.number < b.number;
}
//写法二
bool cmp(stu a, stu b) {
    return a.score != b.score ? a.score > b.score : a.number < b.number;
}
//...以下是sort用法，与上面的无关
int array[10];
sort(array, array + 10, cmp);
vector<int> v(10);
sort(v.begin(), v.end(), cmp);
  • stable_sort()的用法与sort()一致，区别是stable_sort函数遇到两个数相等时，不对其交换顺序

注意：sort函数的cmp最后返回值的判断条件必须是严格大于或严格小于（快排）
TIPS：排序传参建议用引用传参，这样速度更快 

1
2
3
4
5
6
7
8
9
//...
struct node {
    string t;
    int value;
};
bool cmp(const node &a, const node &b) {
    return a.value != b.value ? a.value > b.value : a.t < b.t;
}
//...

2.常用小函数

判断素数的isprime()写法如下（减小时间复杂度）

1
2
3
4
5
6
bool isprime(int a) {
    if(a == 1) return false;
    for (int i = 2; i * i <= a; i++)
        if (a % i == 0) return false;
    return true;
}

求两个数的最大公约数

1
2
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);}

求两个数的最小公倍数

1
x = a * b / gcd(a, b);

将一个十进制数在radix进制下反转生成十进制数（即将原始十进制数转换为radix进制，再反转，再转回十进制数）

1
2
3
4
5
6
7
8
int rev(int n, int radix){
	int sum = 0;
	while(n > 0){
		sum = sum * radix + n % radix;
		n /= radix;
	}
	return sum;
}

长整数加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//在此之前，需要将n和t的长度调整到相同，在短字符串前补0直至长度与长字符串相等
void add(string n, string t){
    int len = n.length(), c = 0;
    for(int i = len - 1; i >= 0; i--){
        n[i] = n[i] + t[i] + c - '0';
        c = 0;
        if(n[i] > '9'){
            n[i] -= 10;
            c = 1;
        }
    }
    if(c != 0)
        n = '1' + n;
}

长整数除法（被除数为长整数）

1
2
3
4
5
6
7
8
9
10
11
12
string Divide(string str, int x){ // x为除数
    int remainder = 0; // 余数
    for(int i = 0; i < str.size(); i++){
        int current = remainder * 10 + str[i] - '0';
        str[i] = current / x + '0';
        remainder = current % x;
    }
    int pos = 0;
    while(str[pos] == '0')
        pos++;
    return str.substr(pos); // 去掉前面多余的0
}

3.数组原地循环右移的方法

如数组大小为n，需循环右移m位。原地移动的方法是：先将数组倒置，再将数组前m位倒置，最后将数组后（n-m）位倒置即可。倒置函数reverse()在algorithm头文件中。
为防止m > n，最开始先 m %= n;

Tips：reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数无返回值
e.g. 反转字符串：reverse(str.begin(), str.end()) 反转vector容器同理。

4.判断字符为数字/字母等

头文件cctype 常用函数如下：

1
2
3
4
5
6
7
isalpha（字母，大小写均包含）
isdigit（数字）
islower（小写字母） -> 转化为小写 tolower()
isupper（大写字母） -> 转化为大写 toupper()
isalnum（字母或数字）
isblank（space和\t）
isspace（space \t \r \n）

5.进制转换

（1）设十进制数t转化为D进制，将每一次t%d的结果保存在int类型的数组s中，然后将t/d，直到t等于0为止，此时s中保存的就是t在D进制下每一位的结果的倒序，最后倒序输出s数组即可（注意特殊情况：为0，边界情况等）

1
2
3
4
5
6
7
while(t != 0){
    int last = t % d;
    binary.push_back(last);
    t /= d;
}
for(int i = binary.size() - 1; i >= 0; i--)
    printf("%d", binary[i]);

（2）设D进制数x转化为十进制数，依次取x的最高位，加到sum中，并每次循环时sum*d

1
2
3
4
5
6
//这里为了方便，D进制数x用string储存
int number = 0;
for(int i = 0; i < x.size(); i++){
    number *= d;
    number += ChartoInt(x[i]); // 防止D>10, 会有字母出现
}

6.字符串相关

字符串切割：

  • s.substr(5，3)//从下标为5起，共三个字符
  • s.substr(5)//从下标为5起直到结尾

查找字母：find()
string中find()返回值是字母在母串中的位置（下标记录），如果没有找到，那么会返回一个特别的标记npos（返回值可以看成是一个int型的数） 判断条件如下：b.find(a[i]) == string::npos

读取一个含有空格的字符串
使用getline(cin, str)
（注：若在getline之前用scanf从输入流里读入了某个参数，要记住在getline()之前getchar()，读取换行）

字符串倒置
reverse(str.begin(), str.end())//无返回值

从字符串中读取指定格式的数据
sscanf() – 从一个字符串中读进与指定格式相符的数据
sprintf() – 字符串格式化命令，主要功能是把格式化的数据写入某个字符串中

1
2
3
4
5
6
7
#include <cstdio>
#include <string.h>
char a[50], b[50];
scanf("%s", a);
sscanf(a, "%lf", &temp);
sprintf(b, "%.2f",temp);
//接受最多精确到小数点后两位的数

7.输出格式控制

%(0)md m为指定的输出字段的宽度。如果数据的位数小于m，则左端补以空格(0)，若大于m，则按实际位数输出。
四舍五入：(int)(a + 0.5)（a为小数）；若是b/2四舍五入（b为整数），则b / 2 + b % 2

8.数据类型的范围

ASCII码表里，字符转换为数字的最大值为127
int的取值范围为: -2^31——2^31-1,即-2147483648——2147483647（≤10^9可用int表示）
long long的取值范围为：-2^63——2^63-1,即-922 3372 0368 5477 5808 ～ 922 3372 0368 5477 5807（≤10^18可用long long表示）
注：大数阶乘，大数的排列组合等，一般都要求将输出结果对1000000007取模（取余）
（以下给出柳婼学姐的大概（？）解释

  1. 1000000007是一个质数（素数），对质数取余能最大程度避免冲突～
  2. int32位的最大值为2147483647，所以对于int32位来说1000000007足够大
  3. int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出
    所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出
    出处From:https://www.liuchuo.net/archives/645 例子：PAT 甲级1093）

9.查找

1.algorithm中的find()函数

1
2
3
4
//a为STL容器
find(a.begin(), a.end(), value);
//a为数组
find(a, a + length, value);

返回值均为迭代器（容器）或指针（数组），若不存在则返回a.end()

2.各容器自己的成员函数的find()实现
vector没有find函数
其余的STL容器返回的均是迭代器
string的find函数返回的是下标索引

3.判断条件
对于返回迭代器的情况：
find(a.begin(), a.end(), value) != a.end()
对于string：
a.find(value) == string::npos

10.最大/最小元素

函数：min_element()与max_element（），需包含头文件#include
作用：返回容器中最小值和最大值的指针。可针对数组、字符串、STL容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<algorithm>
using namespace std;
bool cmp(int a, int b){
	return a < b;
}
//cmp为可选参数，默认是从小到大排序min取最小max取最大，若自定义cmp为从大到小排序，则min取最大，max取最小
int main(){
	int num[]={2,3,1,6,4,5};
	cout<<"最小值是 " << *min_element(num, num + 6) << endl;
	cout<<"最大值是 " << *max_element(num, num + 6) << endl;
	cout<<"最小值是 " << *min_element(num, num + 6, cmp) << endl;
	cout<<"最大值是 " << *max_element(num, num + 6, cmp) << endl;
	return 0; 
}

11.细碎小知识点

  • 加法的进位不可能大于1（n + n = 2 * n 故而其结果不会大于当前进制）
  • 当元素具有非重复性时（即不可能有两个元素相等），一般记录方式采用map或set
  • 若数组过大，建议设置为全局变量。若放在某个函数里会溢出栈（解释by柳神：大数组一定要开全局，而不是写在main函数里面，否则容易发生段错误（因为大数组在main函数里面的话是存储在栈里，而栈空间是在进程创建时初始化的，有固定的大小，一般为几十KB，所以太大的数组会耗光栈空间。而全局变量占用的堆空间，堆空间中的内存是按需分配，自由增长的，可以非常大，比如32位的系统中可以大到4GB。将大数组放在全局变量中能避免栈溢出））
  • 在做与图相关的题目时，要注意添加输入判断。若题中没有明确说明两点间只有一条路和输入路径一定都是有效路径，则首先应将e[x][x]初始化为0（以防输入里有首尾同点，但距离大于0的情况），在之后读入距离时，注意判断e[u][v]是否不为inf，若此次距离小于e[u][v]则读入（选取最小距离）。（虽然一般题目应该不会挖这种坑但还是以防万一吧…
  • 闰年的判断规则：(year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)→该条件为true时为闰年，闰年的2月有29天，其余情况2月28天。
  • 计算周几的小公式——基姆拉尔森计算公式：W= (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1)%7

12.填充（初始化）数组/容器

1.整体填充-fill()函数

1
2
3
4
#include <algorithm>
fill(vec.begin(), vec.end(), val);
fill(array + 3, array + 6, val);
//区间范围依旧是前闭后开

注意：fill函数只能对输入范围内已存在的元素进行操作。即若是STL容器，需要进行初始化，空容器会报错

2.容器初始化

1
2
3
4
vector<int> v(10); // 直接定义长度为10的int数组，默认这10个元素值都为0
//注意：只有初始化过的vector数组，后面才可以用[]索引进行直接赋值
vector<int> v3(100, 9);// 把100长度的数组中所有的值都初始化为9
vector<int> v2(a, a + n); // 将int a[1000]中a[0]到a[n - 1]的值拷贝到该vector中

13.常见单词解释

polynomial - 多项式
be accurate to 1 decimal place - 精确到小数点后一位
significant digits - 有效数字
to be rounded up or down 就是四舍五入. round up = 五入, round down = 四舍
radix - 进制 decimal system - 十进制
even number - 偶数
descendant - 子孙，后代
inverted binary tree 反转二叉树
preorder traversal: root-left-right（先序遍历）
inorder traversal: left-root-right（中序遍历）
postorder traversal: left-right-root（后序遍历）
level order traversal：层序遍历
acyclic - 无环的
duplication - 重复
lexicographically - 字典序
Quadratic probing - 二次方探查法（HashTable）
volume - 体积
topological order - 拓扑序列

14.常见题型的小技巧

  • 当要检测某个元素是否存在时（如最开始输入一系列学生信息，由结构体存储，而后输入一些学生编号以查询信息，其中可能有不存在的学生编号），常见方法是使用数组作索引（如先初始化数组均为0，写一个for循环，对于每个已知的编号，exist[stu[i].id] = i + 1 → i + 1的原因是避免0的出现，0可作为是否存在的判断依据）。这样既可以判断一个学生编号是否合法，也可以根据exist数组来进行索引，由学生编号索引到包含该编号的结构体变量。
  • 若需要对一个数组进行特别值初始化（如均初始化为某一非零特定值），建议使用vector
  • 若输入项数不定（如输入未知个数个字符串，以空格相隔，回车表示结束）一般可采取的判断方法为：
    1
    2
    3
    4
    5
    6
    while(cin >> key){
    	//...
    	char c = getchar();
    	if(c == '\n')
    		break;
    }
  • 为防止使用string、cin、cout超时、越界等情况，当已知输入string的结构时，可采取将string用char[]接受，并转化为int的方法。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //e.g. 已知字符串为三个大写字母和一个数字的形式
    int getid(char *name) {
        int id = 0;
    	for(int i = 0; i < 3; i++)
    		id = 26 * id + (name[i] - 'A');
    	id = id * 10 + (name[3] - '0');
    	return id;
    }
    const int maxn = 26 * 26 * 26 * 10 + 10;
    vector<int> v[maxn];
    int mian(){
        char name[5];
        scanf("%s", name);
        ...
    }
  • 在不知道树的根节点的情况下，可以采取如下方法：写一个循环进行判断，没有出现在child结点中的序号即为根节点
  • 当需要用到二维矩阵作标记而数组太大时（如需标记每两个点的连接情况，每个点的id为4位数，若直接表示为二维矩阵则为arr[10000][10000]），为避免内存超限，可采取unordered_map<int, bool>形式，如a与b相连，即可表示成m[id_a * 10000 + id_b] = true（即int的前四位表示第一个点，后四位表示第二个点）。

15.特定题型的算法

  • 完全二叉树的判断
    先记录每个节点的left child和right child（结构体或vector均可），从根节点开始对整个树进行dfs，若左节点不为空则嵌套左节点开始的dfs，若右节点不为空则嵌套右节点开始的dfs，同时函数传参节点序号（根节点为1，左节点为2 * index，右节点为2 * index + 1），将最大的序号记录在一个全局变量中，若最大序号等于节点数，则是完全二叉树，否则不是。
  • 连通分量的统计
    1.采取并查集的方法，即统计Find(i) == i的结点数（连通的道路都在同一个集合里）
    2.采取DFS的方法，以邻接矩阵存储边，遍历所有未访问的节点，将与该节点相连通的所有节点都标记为已访问，记录主程序中访问的节点数。

__END__