一些算法学习的笔记

本文最后更新于：2023年9月12日 晚上

竞赛寄巧

sync_with_stdio将C++语言和C的输出解绑，提升输出效率，cin.tie(0)将C++输入与C输入解绑，提升输入效率，解绑之后cin与cout速度大幅提升，但不能与scanf和printf混用

1
2
3
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);

使用文件输入

1
2
#include<fstream>
ifstream cin("a.in");

string对象与数值相互转化

需要#include<sstream>，注意两个自定义的函数，提高转化效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<sstream>
#include<string>
using namespace std;
//数值转化为string
string convertToString(double x) {
	ostringstream o; 
	if (o << x) 
		return o.str();
	return "conversion error";//if error
}
//string转化为数值
double convertFromString(const string& s) {
	istringstream i(s); 
	double x; 
	if (i >> x) 
		return x; 
	return 0.0;//if error
}
int main() {
	string s = convertToString(1947.9);
	int p = convertFromString("2048") + 4;
	cout << s << "*\n" << p << endl;
}

使用map实现数字分离

对数字的各位进行分离使用取余等数学方法较慢，可以把数字看做字符串使用map映照

1
2
3
4
5
6
7
8
9
10
11
//该程序计算一个数字各个位的和
map<char, int>m;
//构建字符映射数字
for (int i = 0; i < 10; i++)
	m[i + '0'] = i;
string a = "123764";
int sum = 0;
for (int j = 0; j < a.size(); j++) {
	sum += m[a[j]];
}
cout << sum << endl;

同样也可以用数字映射字符，实现数字转字符

1
2
3
4
map<int, char>m;
//构建字符映射数字
for (int i = 0; i < 10; i++)
	m[i] = i + '0';

二叉树的遍历

有分层遍历和深度遍历，分层遍历通过队列可以简单实现，故在此不赘述，二叉树的深度遍历有递归和非递归两种方式，其中非递归方式主要借助栈实现，非递归的后序遍历比较有难度，有两种方式可以实现，其一为记录上一个节点，其二为增加标识位

递归

递归实现比较简单，在此用二维数组vector<vector<int>> tree(n, vector<int>(2))表示一个二叉树，例如tree[i][0]表示第i个节点的左子节点，tree[i][1]表示第i个节点的右子节点，则前后中序的递归方式遍历如下

前序遍历

1
2
3
4
5
6
7
void VLR(const vector<vector<int>>& tree,int cur) {
	if (cur == 0)
		return;
	cout << cur << " ";
	VLR(tree, tree[cur-1][0]);
	VLR(tree, tree[cur-1][1]);
}

后序遍历

1
2
3
4
5
6
7
void LRV(const vector<vector<int>>& tree, int cur) {
	if (cur == 0)
		return;
	LRV(tree, tree[cur - 1][0]);
	LRV(tree, tree[cur - 1][1]);
	cout << cur << " ";
}

中序遍历

1
2
3
4
5
6
7
void LVR(const vector<vector<int>>& tree, int cur) {
	if (cur == 0)
		return;
	LVR(tree, tree[cur-1][0]);
	cout << cur << " ";
	LVR(tree, tree[cur-1][1]);
}

非递归

非递归方式的遍历，完整代码在github仓库。后序遍历相对难度大一点;节点的部分定义如下

1
2
3
4
5
class BNode {
private:
	BNode<T>* left, * right;
	T data;
};

迭代器

类似于set容器背后的结构，通过前向迭代器从begin()到end()的遍历完成树的中序遍历，比较困难，还不会写。

大数运算

相较于python等语言，C++对于数据类型的处理更精细，繁琐。比如浮点数的精度和大数字运算，C++都需要特殊处理，这是由于C++中数据类型的位数有限所导致，因此需要通过自定义数据类型实现大数运算

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
// 直接将输入的数字读取为string类型
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main() {
	string a, b;
	cin >> a>>b;
	int alen = a.size();
	int blen = b.size();
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	int maxlen = max(alen, blen);
	vector<int>res(maxlen + 1);
	for (int i = 0; i < maxlen+1; i++) {
		if (i < alen && i < blen)
			res[i] = a[i] - '0' + b[i] - '0' + res[i];
		else if (i < alen)
			res[i] = a[i] - '0' + res[i];
		else if (i < blen)
			res[i] = b[i] - '0' + res[i];
		if (res[i] >= 10) {
			res[i + 1] = res[i] / 10 + res[i + 1];
			res[i] = res[i] % 10;
		}
	}
	for (int i = res[maxlen] == 0 ? maxlen - 1 : maxlen; i >= 0; i--)
		cout << res[i];
}

快速幂

推荐网站，快速幂算法比较经典，能够以O(logn)的时间复杂度计算乘方，在一些算法问题中常有输出结果较大，需要mod 1e+7再输出，该类问题也可以应用快速幂实现，同样有着递归和非递归两种方式

递归快速幂

如果n是偶数（不为0），先计算a的n/2次方，后平方；如果n是奇数，先计算a的n-1次方，再乘a；递归出口是a的0次方为1。递推公式如下：
$a^{n}=a^{n-1} \cdot a$ , if n is odd
$a^{n}=a^{\frac{n}{2}\cdot \frac{n}{2} } $ ,if n is even but not 0
$a^{n}=1$,if n=0

1
2
3
4
5
6
7
8
9
10
11
12
int qpow(int a, int n)
{
	if (n == 0)
			return 1;
	else if (n % 2 == 1)
			return qpow(a, n - 1) * a;
	else
	{
			int tmp = qpow(a, n / 2);
			return tmp * tmp;
	}
}

非递归快速幂

1
2
3
4
5
6
7
8
9
10
11
12
double Pow(double x, int n)
{
    double result = 1;
    while (n)
    {
        if (n & 1)// n为奇数
            result *= x;
        n >>= 1; // n/2
        x *= x;  
    }
    return result;
}

对一个大素数取模，可以用上述的大数运算，但没有必要，直接在快速幂中取模，
非递归方式

1

扩展

该思想可以扩展到快速乘，与快速幂类似。以a*n为例，n为偶数（非0），计算a*n/2两个再相加;n为奇数，计算a*(n-1)再与a相加，直到n为0，结束运算。
快速乘

1

对结果取模的快速乘，做了部分简化，比如b为奇数时的处理可以与b为偶数时的处理合并

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
const ll mod = 1e9+7;
ll qpow(ll a,ll b) {
	ll s = 0;
	while (b) {
		if (b & 1) //b为奇数
			s = (s + a) % mod;
		a = (a + a) % mod;//b为偶数或者已经对奇数处理结束（后续b/2时会将奇数变为偶数），a扩大一倍
		b >>= 1;//b除以2
	}
	return s;
}

图论

A*搜索算法

最短路径算法floyd算法

常用算法

gcd最大公约数

greatest common divisor，只要两数不相等，就反复用大数减小数， 直到相等为止，此相等的数就是两数的最大公约数

1
2
3
4
5
6
7
8
9
int gcd(int x, int y) {
	while (x != y) {
		if (x > y)
			x = x - y;
		else
			y = y - x;
	}
	return x;
}

最小公倍数

最小公倍数=XY/gcd(x,y)，由于XY可能超出INT_MAX所以跟换顺序X/gcd(x,y)*Y

线段树

参考资料

  1. 参考资料1 ↩
  2. 参考资料2
    启发函数：f(n)=g(n)+h(n)，其中f(n)为节点n的优先级，g(n)为节点n距起点的代价，h(n)是节点n到终点的预计代价。用于计算点的优先级
    算法的思路如下所示：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    分别使用集合A，B表示未遍历和已遍历的点
    1. 初始化A和B，将起点加入A中
    2. A非空，从A中取优先级最高的点n
    	1. 点n为终点，回退：
    		1. 从终点开始逐步追踪parent点，直到起点，返回结果，结束
    	2. 点n非终点，
    		1. 将n从A删除，加入B中
    		2. 遍历n的有邻接节点
    			1. 若邻接节点m在B中（已遍历），跳过，继续
    			2. 若邻接节点m不在B中，设置m的parent为节点n
    				1. 计算m优先级
    				2. 将m加入B中

    算法实现(参考资料2中有Python,C++,C#版本实现) ↩
learning-notes
#C++
一些算法学习的笔记
https://danmoliuhen.github.io./2023/01/28/一些算法笔记/
作者
CaiYe
发布于
2023年1月28日
许可协议