算法备忘录·基础算法
本文最后更新于 2024年5月15日 凌晨
一直以来,没能系统学习算法,是我心中的痛;现在学了 y 总的算法基础课,做做笔记,希望能够有所收获。
这是第一节,基础算法。
基础算法
排序
快速排序
核心思想:
- 设定分界值 ;
- 左边小于分界值,右边大于分界值
- 双指针,两端开始,找到左边一个大于分界值,右边一个小于分界值,就将二者交换
- 必须严格大于/小于,否则会
Memory Limit Exceeded
;
- 递归
模板
1
2
3
4
5
6
7
8
9
10void 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);
do j --; while(a[j] > x);
if (i < j) swap(a[i], a[j]);// 注意这里的if判断
}
quick_sort(a, l, j), quick_sort(a, j + 1, r);
}
归并排序
核心思想
- 递归排序 和
- 归并,将左右两个有序序列合并成一个有序序列
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void 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 i = l, j = mid+1, k=0;
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 (int i = l, j = 0; i <= r; i ++ , j++ ) a[i] = tmp[j]; // 复制回原数组
}
二分
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…
- 单调性❌ 二分性✅
- 把
else if
每个情况写清楚,就能很好地避免错误
整数二分
- 参考:详解二分查找算法
寻找一个数
搜索区间:
- 所以 while 的判断条件是
l <= r
,这样保证退出循环时,搜索区间是空集
- 所以 while 的判断条件是
使用
l = mid + 1
和r = mid -1
是因为mid
已经被排除了模板
1
2
3
4
5
6
7
8
9
10int bsearch(int a[], int target){
int l = 0, r = a.size() - 1;
while (l <= r){ // 重点
int mid = (l + r) >> 1;
if (a[mid] == target) return mid;
else if (a[mid] < target) l = mid + 1; // 重点
else if (a[mid] > target) r = mid - 1; // 重点
}
return -1;
}
寻找左边界
搜索区间:
- 所以 while 的判断条件是
l < r
,这样保证退出循环时,搜索区间是 空集
- 所以 while 的判断条件是
为什么是
l = mid +1
和r = mid
,因为每次分割变成 和返回
r
,因为a[mid] == target
时,有r = mid
。这也是为什么能够搜索左边界——当找到 target 后,并不是立刻返回,而是缩小上界如果
target
不存在,可以修改返回为a[l] == target ? l : 1
模板
1
2
3
4
5
6
7
8
9
10int l_bsearch(int a[], int target){
int l =0, r = a.size(); // 重点
while (l < r){
int mid = (l + r) >> 1;
if (a[mid] == target) r = mid; // 重点
else if (a[mid] < target) l = mid + 1;
else if (a[mid] > target) r = mid; // 重点
}
return r; // 重点
}
寻找右边界
搜索区间:
- 所以 while 的判断条件是
l < r
,这样保证退出循环时,搜索区间是 空集
- 所以 while 的判断条件是
为什么是
l = mid +1
和r = mid
,因为每次分割变成 和返回
l - 1
,因为a[mid] == target
时,有l = mid +1
。这也是为什么能够搜索左边界——当找到 target 后,并不是立刻返回,而是缩小下界如果
target
不存在,可以修改返回为a[l - 1] == target ? l - 1 : 1
模板
1
2
3
4
5
6
7
8
9
10int l_bsearch(int a[], int target){
int l =0, r = a.size(); // 重点
while (l < r){
int mid = (l + r) >> 1;
if (a[mid] == target) l = mid + 1; // 重点
else if (a[mid] < target) l = mid + 1;
else if (a[mid] > target) r = mid; // 重点
}
return l - 1; // 重点
}
浮点数二分
模板
1
2
3
4
5
6
7
8
9double bsearch(double l, double r){
const double eps = 1e-6;
while (r - l > eps){
double mid = l + (r -l) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
高精度
- 存储:
vector<int>
,倒序存储,小位在左- 这样方便添加新的高位
- 压位:一般来说我们用数组的一个元素来表示一个位数。但是,为了节省空间,可以一个元素表示多个位数
- 读取:一般输入都是
string
读入,再逆序存储到vector<int>
中,记得要-'0'
- 下面的各个运算均为非负数,负数的情况判断符号位,转换为绝对值加减
高精度加法
注意会有新的进位
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15vector<int> add(vector<int> &A, vector<int> &B){
if (A.size() < B.size()) return add(B,A);
vector<int> C;
int t = 0;
for (int i =0; i < A.size(); i ++ ){
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t % 10); // 新的进位
return C;
}
高精度减法
需要去除前置 0
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14// A >= B
vector<int> sub(vector<int> &A, vector<int> &B){
vector<int> C;
int t;
for (int i = 0; i < A.size(); i ++){
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前置 0
return C;
}
高精度乘法
vector<int> * int
需要去掉前置 0
注意会有新的进位
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16vector<int> mul(vector<int> &a, int b){
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i++){
t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (t){
C.push_back(t % 10);
t /= 10;
} // 新的进位
while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前置 0
return C;
}
vector<int> * vector<int>
有更快的 FFT 方法
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23vector<int> mul(vector<int> &A, vector<int> &B){
vector<int> C(A.size() + B.size());
for (int i = 0; i < A.size(); i ++){
for (int j = 0; j < B.size(); j ++){
C[i + j] += A[i] + B[j];
}
}
int t = 0;
for (int i = 0; i < C.size(); i ++){
t += C[i];
C[i] = t % 10;
t /= 10;
}
while (t){
C.push_back(t % 10);
t /= 10;
} // 新的进位
while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前置 0
return C;
}
高精度除法
注意
/
和%
的使用位置所得结果需要
reverse
,然后去前置 0模板
1
2
3
4
5
6
7
8
9
10
11
12vector<int> div(vector<int> &A, int b, int r){
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i --){
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
前缀和与差分
前缀和
- 便于处理从 l 到 r 之间元素求和
- 由于需要方便设定 和 ,所以 录入数据的时候是下标从 开始
一维前缀和
- (注意是 )
二维前缀和
- :第 行 列格子上左上部分所有元素之和
- 以 为左上角, 位右下角的子矩阵所有元素之和:
差分
一维差分
给区间 中的每个数加上 :
模板
1
2
3
4void insert(int l, int r, int c){
b[l] += c;
b[r +1 ] -= c;
}这样一来,生成差分数组就有了两种方法
法 1:根据定义
法 2:对原数组,可以视其为 数组逐个插入 元素得来的
1
for (int i = 1; i <= n ; i ++) insert(i, i, a[i]);
二维差分
- 给以 为左上角, 位右下角的子矩阵所有元素的加上 :
双指针算法
将暴力 根据具体问题中的性质简化到
- 某种“单调性”
常见问题
- 对于一个序列,用两个指针维护一段区间。e.g:滑动窗口
- 对于两个序列,维护某种次序。e.g:归并排序中合并两个有序序列
模板
1
2
3
4for (int i = 0, j = 0; i < n; i ++){
while (j < i && check(i, j)) j ++;
// 具体问题的逻辑
}
位运算
求 的第 位数字
1
n >> k & 1
返回 的最后一位 1
1
lowbit(n) = n & -n
离散化
将值域大但是数量少的值映射到一个小值域区间上
步骤
- 储存所有待离散化的值
- 排序后去重
- 一定是先排序!
- 利用二分法求出对应的离散化的值
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15vector<int> alls; // 储存待离散化的值
sort(alls.begin(),alls.end()); // 排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重
// 二分法求对应离散化值,找到第一个大于等于 x 的位置,相当于求大于等于 x 的左边界
int find(int x){
int l = 0, r = alls.size(), mid;
while(l < r){
mid = l + (r - l) / 2;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r;
}对于有的语言,不含
unique()
函数,则可以用双指针写1
2
3
4
5
6vector<int>::iterator unique(vector<int> &a){
for(int i = 0; i < a.size(); i ++){
if (!a[i] || a[i] != a[i - 1]) a[j ++] = a[i];
} // a[0] ~ a[j - 1] 为所有 a 中不重复的数
return a.begin() + j;
}对于二分查找,也可以直接使用
low_bound()
函数
1
2
3int find(int x){
return low_bound(alls.begin(), alls.end(), x) - alls.begin(); // 下标从 0 开始
}
区间合并
用于将所有存在交集的区间合并
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(), segs.end()); // c++ 在排序 pair 类型时,会先比较第一个,若第一个一样再比较第二个
int st = -2e9, ed = -2e9;
for (auto seg : segs){
if (ed < seg.first){
if (st != -2e9) res.push_back({st, ed});
st = seg.first;
ed = seg.second;
}else{
ed = max(ed, seg.second);
}
}
if (st != -2e9) res.push_back({st, ed}); //勿忘!
segs = res;
}
算法备忘录系列目录:
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·杂项
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析
第九节 算法备忘录·杂项