数据结构与算法笔记
数据结构与算法笔记
考完蓝桥杯,混完省三参与奖,开始重新补数据结构与算法,目标是Leetcode Knight
数学相关算法
LCM(最小公倍数)
使用公式LCM(a, b) = |a * b| / GCD(a, b)
然后使用辗转相除法球的最大公约数
- b = 0, GCD = a;
- a = b, b = a % b, 递归至b = 0;可以看作是一个长方形,长边是a,短边是b。如何使用一个正方形将该长方形填满,所求的最大的正方形边长就是a和b的最大公约数。
1
2
3
4
5
6int gcd(int a, int b){
while(b != 0){
int temp = b;
b = a%
}
}
先使用小技巧
需要将一个数字按位分离,可以使用to_string()
函数
快速幂
1 |
|
快速幂的原理都很清楚,可是对一个更大的数求快速幂需要使用到取余的操作,这里对取余操作写下思考。
1 |
|
对应的快速幂代码是
1 |
|
小技巧
一个数字可以分数位求幂,例如2 ^ 123,可以求{2 ^ 3} * {(2^10) ^ 2} * {(2^100) ^ 1}
数据结构与算法笔记
https://bromikey.github.io./2024/04/30/数据结构与算法笔记/