[TOC]

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
欧几里得算法求最大公约数
递归实现：
*/
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

//非递归实现：
int gcd(int m, int n) {
    while (n != 0) {
        int rem = m % n;
    	m = n;
    	n = rem;
    }
    return m;
}

整数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Wikipedia 上的写法
int binary_search(const int arr[], int start, int end, int key) {
    int ret = -1;  // 未搜索到数据返回-1下标

    int mid;
    while (start <= end) {
        mid = start + (end - start) / 2;  //直接平均可能會溢位，所以用此算法
        if (arr[mid] < key)
            start = mid + 1;
        else if (arr[mid] > key)
            end = mid - 1;
        else {  // 最後檢測相等是因為多數搜尋狀況不是大於要不就小於
            ret = mid;
            break;
        }
    }

    return ret;  // 单一出口
}
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
// acWing 写法
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

判断奇偶数

1
2
3
4
5
6
7
bool isOdd(int n) {
    return n & 1;	//奇数返回true
}
/*
if(n & 1 == 0)  判断为偶数是错误的，==优先级比&高
改为 if((n & 1) == 0)
*/

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
set<string> res; // 字典序排序， 对aabc这样的排列去重

void dfs(string& s, int st) {
    if (st == s.length() - 1) {
        res.insert(s);
        return;
    }
    for (int i = st; i < s.length(); i++) {
        swap(s[st], s[i]);
        dfs(s, st + 1);
        swap(s[st], s[i]);
    }
}

组合

https://zh.wikipedia.org/wiki/組合#組合_C

1

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// s[]是长文本，p[]是搜索词，下标都是从1开始，n是s的长度，m是p的长度
// 求搜索词的ne数组：
for(int i = 2, j = 0; i <= m; i++ ) {
    while(j && p[i] != p[j + 1]) j = ne[j];
    if(p[i] == p[j + 1]) j++ ;
    ne[i] = j;
}

// 匹配
for(int i = 1, j = 0; i <= n; i ++ ) {
    while(j && s[i] != p[j + 1]) j = ne[j];
    if(s[i] == p[j + 1]) j ++ ;
    if(j == m) {
        // 匹配成功后的逻辑
        j = ne[j];
    }
}

二叉树的遍历

后续中序转前序

1
2
3
4
5
6
7
8
9
10
int post[] = {3, 4, 2, 6, 5, 1};
int in[] = {3, 2, 4, 1, 6, 5};
void pre(int root, int start, int end) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    printf("%d ", post[root]);
    pre(root - 1 - end + i, start, i - 1);	// 当前根节点 - 右子树节点数 - 1
    pre(root - 1, i + 1, end);
}

前序中序转后序

1
2
3
4
5
6
7
8
void postorder(int r, int st, int ed) {
	if(st > ed)	return;
	int i = st;
	while(i <= ed && in[i] != pre[r]) i++;
	postorder(r + 1, st, i - 1);
	postorder(r + 1 + i - st, i + 1, ed);
	printf("%d ", pre[r]);
}

string与int之间的转化

to_string函数（int 转string)

c++11标准增加了全局函数std::to_string：

string to_string (int val); 其余类似

atoi函数（string 转int）

1
2
3
string s = "123";
int n = atoi(s.c_str());
cout << n;	//123

类似的还有浮点型atof()，long型atol()

stoi函数（string 转int）

atoi()的参数是 const char* ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char*类型的,而stoi()的参数是const string*,不需要转化为 const char*；

stoi()会做范围检查，默认范围是在int的范围内的，如果超出范围的话则会runtime error！
而atoi()不会做范围检查，如果超出范围的话，超出上界，则输出上界，超出下界，则输出下界；

1
2
3
4
5
6
string s1 = "2147482", s2 = "-214748";
string s3 = "214748666666663", s4 = "-21474836488";
cout << stoi(s1) << endl;	//2147482
cout << stoi(s2) << endl;	//-214748
cout << atoi(s3.c_str()) << endl;	//2147483647
cout << atoi(s4.c_str()) << endl;	//-2147483648
函数 类型
stoi(s,p,b) 把字符串s从p开始转换成b进制的int
stol(s,p,b) long
stoul(s,p,b) unsigned long
stoll(s,p,b) long long
stoull(s,p,b) unsigned long long
stof(s,p) float
stod(s,p) double
stold(s,p) long double

string类成员函数find()，find_first_of()，find_first_not_of()

find()

find() 可以在指定字符串中查找完全匹配子串的位置，没找到返回string::nops

1
2
3
str1.find(str2);	//从串str1中查找时str2，返回str2中首个字符在str1中的下标
str1.find(str2,5);	//从str1的第5个字符开始查找str2
str1.find("of big",2,2);	//从str1中的下标为2处开始查找of big的前两个字符

find_first_of()

find_first_of() 查找在字符串中第一个与str中的某个字符匹配的字符，返回它的位置，没找到返回string::nops

1
2
3
4
5
6
7
8
9
10
11
12
13
string str = "abcdefacbdef";
int index;

index = str.find_first_of("xcyz");	//index值为2
//str中c最早出现，c的下标为2

index = str.find_first_of(str0, n);
//str0是子串，n是从下标为n的字符开始查找

index = str.find_first_of(str0, n, m);
//str0是子串，n是从下标为n的字符开始查找，m是只看str0子串的前m位字符

find_last_of() 与find_first_of() 查找顺序相反，其他类似

find_first_not_of()

find_first_not_of() 在字符串中查找第一个与str中的字符都不匹配的字符，返回它的位置，没找到返回string::nops

1
2
3
4
5
6
7
8
9
10
11
string a="12345";
auto s=a.find_first_not_of("1238"); //结果为 s=3;
//a字符串中有，而子串没有的是"45"，而'4'字符是最先出现的，它的下标为3

find_first_not_of(str,n);
//str是子串，n是从下标为n的字符开始查找

find_first_not_of(str,n,m);
//str是子串，n是从下标为n的字符开始查找，m是只看str子串的前m位字符

find_first_not_of()与find_last_not_of()查找顺序相反，其他类似

素数

试除法判定素数

1
2
3
4
5
6
7
8
bool is_prime(int x) {
    if(x < 2)	return false;
    for(int i = 2; i <= x / i; i++) {
        if(x % i == 0)
            return false;
    }
    return true;
}

朴素筛法求素数

合数有被重复筛除的情况

1
2
3
4
5
6
7
8
9
10
11
int primes[N], cnt;	//primes[]存储所有素数
bool st[N];	//st[x]存储x是否被筛过

void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(st[i])	continue;
        primes[cnt++] = i;
        for(int j = i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法求素数

原理：用一个合数的最小质因子来筛掉这个合数，合数只被筛一次

1
2
3
4
5
6
7
8
9
10
11
12
13
int primes[N], cnt;	//primes[]存储所有素数
bool st[N];	//st[x]存储x是否被筛过

void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i])	primes[cnt++] = i;
        //primes[j] * i <= n 转化为 primes[j] <= n / i
        for(int j = 0; primes[j] <= n / i; j++) {
            st[i * primes[j]] = true;	//primes[j] * i 为合数
            if(i % primes[j] == 0)	break;	//确保primes[j]是这个合数的最小质因子
        }
    }
}

排序

比较

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n2​) O(n) O(n2) O(1) 稳定
简单选择排序 O(n2) O(n2) O(n2) O(1) 稳定
直接插入排序 O(n2) O(n) O(n2) O(1) 稳定
希尔排序 O(nlogn)~O(n2) O(n1.3) O(n2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定

冒泡排序

1
2
3
4
5
6
void bubble_sort(int arr[], int len) {
	for (int i = 0; i < len - 1; i++)
		for (int j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

直接插入排序

1
2
3
4
5
void insert_sort(int a[], int n) {
    for(int i = 1; i < n; i++)
        for(int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
            swap(a[j], a[j + 1]);
}

简单选择排序

1
2
3
4
5
6
7
8
void selection_sort(int a[], int n) {
    for(int i = 0; i < n - 1; i++) {
        int min = i;
        for(int j = i + 1; j < n; j++)
            if(a[j] < a[min]) min = j;
        swap(a[i], a[min]);
    }
}

希尔排序

1
2
3
4
5
6
7
8
9
void shell_sort(int a[], int n) {
    int gap = 1;	//步长
    while(gap < n / 3)
        gap = 3 * gap + 1;
    for(; gap > 0; gap /= 3)
        for(int i = gap; i < n; i++)
            for(int j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)	//每个元素与自己组内的数据进行直接插入排序
                swap(a[j], a[j + gap]);
}

具体步长选择方法可以参照：维基百科 or 大佬的简书

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void quick_sort(int a[], int l, int r) {
    if(l >= r)	return;
    
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while(i < j) {
        do i++;	while(a[i] < x);	//while(a[++i] < x);
        do j--;	while(a[j] > x);	//while(a[--j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}
/*
	用i的话：
    x = a[l + r + 1 >> 1];
    quick_sort(a, l, i - 1);
    quick_sort(a, i, r);
    */

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int a[], int l, int r) {
    if(l >= r)	return;
    
    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(a[i] < a[j]) tmp[k++] = a[i++];
    	else tmp[k++] = a[j++];
    
    while(i <= mid)	tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    
    for(i = l, j = 0; i <= r; i++, j++)
        a[i] = tmp[j];
}

堆排序

堆本质上是一棵完全二叉树。以小根堆为例，其每个点都是小于等于左右子节点的，根节点就是整个树的最小值。

堆的存储方式：用一维数组存储，heap[1]是整个堆的根节点，设某节点的下标是x，则左儿子是2x，右儿子是2x+1。

往下调整与往上调整：
如果某个数变大了，就要把它往下移,直到不能下移为止；反之，则要往上移。

堆的一些操作

1
2
3
4
5
heap[++size] = x;up(size); //插入一个数
heap[1]; //求最小值
heap[1] = heap[size];size--;down(1); //删除最小值
heap[k] = heap[size];size--;down(k);up(k); //删除任意一个元素
heap[k] = x;down(k);up[k]; //修改任意一个元素

堆排序

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
int h[N], size; //heap[]从1开始，size为数组长度(下标)

void down(int u) {
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    
    if (u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}

void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

void heap_sort() {  //先要建立小根堆，最终得到递减数列
    for (int i = size / 2; i; i--) //建立小根堆
        down(i);
    int t = size; //暂存size
    while(size) {
        swap(h[1], h[size--]);
        down(1);
    }
    size = t;
}