算法基础--基础算法
前言：学校学完数据结构与算法后，感觉自己什么都没学到，唯一就知道好像有那么个东西，别说代码实现，就是复杂一点的问题连原理都不清楚了。然 为了提高算法水平，想系统的学习算法。想要有实质的提高必须学习+刷题，所以以赛促学，从算法竞赛角度入手。在此我比较喜欢在ACwing的网站上学习，并记录学习的心得与路程。
下面的模板在ACwing都有对应的习题，超好啊！！！
排序
- 快速排序
- 归并排序
- C++ sort（一般用的比较多）
- sort(begin, end, cmp)
二分
- 整数二分
bool check(int x) {/*...*/} //检查是否满足某种特性
//区间分成[l,mid],[mid+1,r]时使用
int bsearch_1(int l, int r)
{
while(l < r)
{
int mid = l + r >> 1; //两个二分的区别就在这mid上
if(check(x)) r = mid;//通过这里判断mid取值
else l = mid + 1;
}
return l; //return r 也是可以的
}
//区间分成[l,mid-1],[mid,r]时使用
int bsearch_2(int l, int r)
{
while(l < r)
{
int mid = l + r + 1 >> 1; //这里需加1
if(check(x)) l = mid;
else r = mid - 1;
}
return l; //return r 也是可以的
}
- 浮点数二分（很少用，用也能快速写出）
高精度算法
在面试的时候用的多一些，暂时不学习。
前缀与差分
他们都有一维二维应用，鉴于现在水平弄好一维即可
- 前缀和
//作用：能快速求出数列里某一段的和
//例：s[l--r] = s[r] - s[l-1]
//数组都从下标1开始存，方便
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
- 差分
//头一次知道差分概念可能需要琢磨摸下
差分数组定义：b[i] = a[i] - a[i-1]
构造差分数组：
for(int i = 1, i <= n; i++)
B[i] += a[i], B[i+1] -= a[i];
//作用：可对数组某段区间的数都加上某个值
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
双指针算法
//i是后面的指针
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
位运算
(1) 求n的二进制第k位数字: n >> k & 1
解析下原理：>> 本意通过位移运算实现乘除运算，但在这里直接利用位移原理实现二进制内部的变化，达到目的。
(2) 返回n的二进制最后一位1：lowbit(n): return n & -n;
离散化
//离散化还是比较复杂的，是一种特殊的哈希算法。
// 离散化用于求某区间的和
// 哈希用于查找
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
区间合并
// 将所有存在交集的区间合并,类似贪心算法里的区间问题
/*第一步：按a端排序
* 分三种情况
* 1. 全包裹 要长的
* 2. 有交集 合并右边延长
* 3. 无交集 原区间返回，重新看新的
*/
void merge(vector<PII> &segs)
{
vector<PII> res; //存放答案
sort(segs.begin(), segs.end()); //在pair中默认比first元素
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;
}
