快速排序
快速排序先确定一个基准点$P$,然后调整序列,使得基准点$P$左边的点小于等于$P$,右边的点大于等于$P$。这样$P$的位置便是排好序后的位置,再递归的对$P$左边和右边的子序列做同样调整(选一个新的基准点)。因此快排总结为3步:
- 确定基准点。可以随机选,也可以端点或中点。
- 调整基准点两边的数据。可左右扫描选择不满足的两个进行交换。
- 确定子序列,继续递归。
1 | void qsort(int a[], int l, int r){ |
归并排序
归并排序使用分治策略,将无序序列不断二分,最终每个子序列(单个数)都是有序的。再回溯该过程,将有序的子序列合并为一个序列。
- 二分为两个子序列。
- 对两个子序列递归。
- 递归返回时,合并已有序的子序列。
1 | void merge_sort(int a[], int l, int r){ |
希尔排序
拓扑排序
判环
1 | bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { |
整数二分
二分常常与单调有序的情况联系起来,比如二分查找。但二分的本质并不只是单调性,它可将一段数据按是否满足某条件而分为两段。用二分来找到这两段邻接的边界,当然可以是左边界,也可以是右边界。在二分查找中这个条件就是数值大小。当序列中有重复数字时,二分时区间不同得到的结果可能是不同的。这时可取左边界,也可右边界,这样分为两种情况的区间:
- $[l,\;mid]$ 与 $[mid+1, \; r]$
- $[l,\;mid-1]$ 与 $[mid, \; r]$
这两种区间有着不同的特性,比如在二分搜索时,若使用第一种区间,可看到$mid$是偏向左端的,因此若结果有重复的多个数据,结果位置会返回较左端近的位置。于是第一种方式可以认为是查找大于等于$num$的最左端位置。
实质上二分是将序列按照某种性质分割为两个区间,常用的性质是大小。『 其中分割点属于哪个区间是比较关键的,它可以是满足左边性质的点,也可以是满足右边性质的点』。上述两个区间就是分别查找性质属于右边和左边的分割点,对于重复点,如果使用查右半边性质的方法1,那么找到的就是重复点的最左端。
1 | // ##区间[l, r]被划分成[l, mid]和[mid + 1, r]时: |
两种方法的区别可以通过下面这个题理解一下,求一串非递减序列中某个数字的存在范围,即起始位置到终止位置。当基准点$mid$两端边界更新的优先不同时,会得到满足查找数字$num$区间的不同端点。
1 | int main(){ |
大数加法
输入数据超过64位时,便不能再使用简单数据类型保存。结果的长度未知,可用向量来动态添加。为了加法计算方便,向量中保存的数据应是逆序的。
1 | vector<int> add(vector<int> a, vector<int> b){ |
大数减法
减法与加法类似,只需要判断是否有借位即可。另需保证被减数A的数值大于B的数值,不能只是简单的像加法那样判断长度。减法的高位可能存在有多余的0的情况,需要去掉。
1 | vector<int> sub(vector<int> a, vector<int>b){ |
大数乘小数
一个大数与一个可用基本类型表达的数作乘法,可按位将大数中的每一位与小数作乘法,再求和。
1 | vector<int> mul(vector<int> a, int b){ |
大数除小数
除法与其它运算不同的是它从高位开始计算,余数往后扩位。
1 | vector<int> sub(vector<int> a, int b, int &r){ |
前缀和
一维前缀和比较简单,公式如下
二维前缀和与一维差不多,不过是将输入数组变为二维的矩阵形式。其公式为
这是以$(x_1,y_1)$为左上角,$(x_2,y_2)$为右下角的子矩阵的和。其前缀和的建立可图示如下:
为了求解图中蓝色子矩阵的和,用这四个小矩阵组成的大矩阵,减去绿色和红色区域代表的子矩阵的和,显然它们的交叉区域多减了一次,于是加上交叉区域的和。
1 | vector< vector<int>> s(n+1, vector<int>(m+1, 0)); // 必须初始化为0 |
差分
差分与前缀和关系较密切,甚至可以看作逆操作。对差分数组求前缀和可得到原始数组,同样,对前缀和求差分也能得到原数组。
差分数组还有个特性:对原始数组$[l,\; r]$区间上的内容$+c$等价于对差分数组的这两个端点执行$d[\;l\;]+c, \;d[r+1]-c$ 。因为变回原始数组求前缀和时会将$d[l]$上多出的$c$加到$l$之后的元素上,$r$之后的不需要加$c$,因此在$r+1$处减去$c$抵消。
1 | for(int i = 1; i <= n; i++) //构造差分数组,差分需用两个数组 |
对于二维差分,与一维差不多,类似于一维前缀和到二维前缀和的扩展。对于二维的图示,只需将前缀和的图片旋转180即可。
对于差分矩阵,在某个点加上一个数值相当于给它右下方矩阵所有值加上这个数值,于是它的情况正好和前缀和相反。
1 | void insert(vector< vector<int>> &a, int x1, int y1, int x2, int y2, int v){ |
二进制中1的个数
利用二进制减法的借位和按位与运算。二进制非$0$ 即 $1$,$num-1$ 时会取走$num$当前最低位的 $1$,若有借位,借位后面的$0$ 都会变成 $1$,但是与原$num$进行按位与操作后便为 $0$,这样一遍操作便取走一个 $1$,直到$num=0$ 。
1 | int count = 0; |
双指针算法
双指针一般有两种思路:
- 对于一个序列,用两个指针维护一段区间
- 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
对于第一种,需要确定的是这段区间的性质以及如何维护这段区间。例如最大无重复子串,需要维护的区间是子串,子串的性质是区间内无重复字符。那么主要的任务就是保证这段区间内的字符不重复,可以使用另一个数组来记录字符出现的次数,也可以记录字符出现的位置。若使用次数则维护次数<=1,若使用位置则保证前指针指向的字符没有出现过或是出现的位置不在子串内。
1 |
|
对于第二种,维护两个序列之间的某种关系。关键是找到它们之间的联系,例如求解两个升序序列中元素和为某个值的元素位置。那么目标就是计算两两之间的和,但是由于是升序,可以判断和的大小来剪去多余计算。
1 | for(int i = 0, j = m-1; i < n; i++){ //对于第二个数组从后往前遍历 |
也可用将其中一个数组建立$hash$表,第二个数组根据它们关于$x$的互补关系查找哈希表。
1 | unordered_map<int, int> ha; |
离散化
- 区间和
例如一个无限长的数轴,每次在某一位置上加c,再询问其某段区间的和。可以将其地址离散保存,再对地址进行排序后,后面的加c和前缀和都通过二分查询这个离散地址来实现。
1 | const int N = 3e5+10; |
- 区间合并
只需将区间左边界排序,依次比较前面区间的ed与后面区间的st和ed的关系,它们只有三种关系,按情况对其进行更新即可。
1 |
|