算法基础知识总结

Efficient procedures for solving problems on large inputs.

一、基础算法

1、快速排序

1、类别：快速排序是一种 交换排序，冒泡排序也是一种交换排序。

2、原理：将未排序的元素根据一个作为基准的主元（Pivot）分成两个子序列，其中一个子序列的数都大于主元，另一个子序列的数都小于主元，然后递归地对两个子序列进行排序。

3、本质：分而治之的思想。减小问题规模再分别进行处理。

4、时间复杂度：最好和平均：$O(NlogN)$， 最差 $O(N^2)$ 。不适合用于数据量比较小的时候。数据比较小的时候可以用插入排序。

5、基本步骤：

第一步：设置左右指针和主元

第二步：根据快速排序的原理移动左右指针，当指针停止移动并且没有错位时交换两个指针指向的元素

第三步：递归解决左右两边

6、代码注意点：

（1）注意程序停止的条件：当要排序的序列左下标大于等于右下标时无法排序，则停止。
（2）所有比较都不带等于号！

2、归并排序

1、原理：将长度为N的序列看成N个长度为1的子序列，对相邻两个子序列进行归并操作不断迭代直到序列长度变成N。

2、核心：归并操作+分而治之

3、时间复杂度：$O(NlogN)$

4、基本步骤：

第一步：递归地排序左子列

第二步：递归地排序右子列

第三步：归并

​ （1）创建一个空数组用于存放排序结果

​ （2）让两个指针分别指向已经排好序的子序列的第一个位置，然后依次比较两个指针指向的元素，将较小的放入空数组，并将当前指针后移一位。重复该步骤

第四步：扫尾

5、代码注意点：

（1）需要创建一个新的空数组来存放比较结果。两个指针的开始位置应该是两个序列的开头。
（2）判断逆元的时候要用 res += mid - i + 1 而不能 res += j - i，因为 j 在循环中不断变化。

3、归并排序与快速排序

1、比较：快速排序为什么快？归并排序时间复杂度和快速排序相同，并且快速排序最差的时候会是$O(N^2)$ 。

首先时间复杂度忽略了系数。事实上快速排序的系数是最小的，并且它不需要开辟额外的空间，因此总体来说在平均意义上快速排序是表现最好的。而诸如堆排序，几乎不会比较相邻元素对cache不友好很少被采用。

2、代码注意点：

（1）根据快排的定义，我们需要将每个元素和主元比较，因此得首先计算出主元而不能写在循环里！int x = nums[(l + r) >> 1];

但是归并排序是依次比较两个指针指向的元素，所以需要在循环里一个一个比较。

4、整数二分

1、二分与单调性：有单调性的一定可以二分，但是能够二分的未必一定要有单调性（分段处理，使其满足在每一段解空间具备单调性）。

2、二分的本质：边界。如果定义了某个性质，使得某个边界的一边满足该性质，另一边不满足的话，二分法可以找到这个边界点。

3、基本步骤：

第一步：确定左右指针初始位置。

第二步：找到中点

第三步：根据是否满足性质移动左右指针。

4、代码注意点：

（1）应当在while循环内部定义中点，因为中点需要随着循环更新；

（2）循环结束的条件是左指针大于等于右指针；

（3）千万不能漏掉更新左右指针时的 else ！！！！

（4）对于 l = mid; r = mid - 1的更新方式应该有：mid = (l + r + 1) >> 1！原因是，当 l = r - 1时，如果更新方式为：l = mid并且mid = (l + r) >> 1 = l就会发生死循环。但是如果mid = (l + r + 1) >> 1，就会更新：l = mid = r然后循环结束。
（5）对于check(mid)的两种模板，我们首先应该确定要找的答案满足什么样的边界性质。例如：
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
样例：a[6] = {1, 2, 2, 3, 3, 4}，查找3的起始位置和终止位置。对于起始位置，它满足的性质可以是左边的数都小于自己，那么check函数为：a[mid] < 3，更新方式自然就是true: l = mid + 1; false: r = mid，它的性质也可以是右边的数都大于等于自己那么check函数为：a[mid] >= 3，更新方式为true: r = mid; false: l = mid + 1。对于终止位置，它满足的性质可以是左边的数都小于等于自己，那么check函数为：a[mid] <= 3，更新方式自然就是true: l = mid; false: r = mid - 1，它的性质也可以是右边的数都大于自己那么check函数为：a[mid] > 3，更新方式为true: r = mid - 1; false: l = mid。

5、高精度加法

1、作用：解决两个超长整数相加的问题

2、基本思想：用数组存放加数和最终结果，手动模拟加法过程

3、代码注意点：

（1）定义vector时不能初始化长度，因为vector本身就是变长数组。

（2）数字应该倒着存储，以便于最后有进位时可以直接添加在数组最后，而不用把整个数组往后移动。

（3）add( ) 函数的参数是两个vector的引用！

（4）要记得比较两个加数的长度，应该遍历长度更长的一个，这样便于直接把答案添加到新的vector中

（5）循环结束后，记得把最后的进位添加到数组中

6、高精度减法

1、作用：解决两个超长整数相减的问题

2、基本思想：用数组存放数据，手动模拟减法过程

3、代码注意点：

（1）存放数据是依然是倒序

（2）在比较两个数的大小时应该从高位开始比较

（3）注意求差的小技巧：(t + 10) % 10

（4）注意最后”去 0“操作时结果的长度至少是1，因为有可能结果为0。

7、高精度乘法

1、作用：解决两个超长整数相乘

2、基本思想同上

3、代码注意点：

（1）乘法不用管数字的长度或者大小

（2）和加法一样要记得添加最后的进位

（3）和减法一样记得最后去0

8、高精度除法

1、作用：解决两个超长整数相除的问题

2、基本思想同上

3、代码注意点：

（1）依然是倒序存储

（2）在进行除法时，应该从高位开始。但是高位得到的结果可能会是前导0，所以还需要把 res 翻转然后来一个删除前导0操作，最后再倒序输出。

9、一维前缀和数组

1、前缀和数组：对于原数组 $a[N]=[a1,a2,a3,a4,...,aN]$ 有前缀和数组 $b[N]=[b1,b2,b3,b4,b5,...,bN],b_i={\sum }_{k=1}^{k=i}{a}_k$

2、作用：能快速地求出某一段区间的和

3、递推公式：$b[i]=b[i-1]+a[i]$ 或者直接把数组a变成自己的前缀和数组：$a[i]+=a[i-1]$

4、a数组在区间 $[l,r]$ 的和为：$b[r]-b[l-1]$

5、代码注意点：

（1）存储数组从下标1开始！

10、二维前缀和数组

1、概念与作用和一维前缀和数组雷同。

2、代码注意点：

（1）千万注意最开始定义数组长度N的时候不能超过太多，否则会报错。

11、一维差分数组

1、概念：求差分数组是求前缀和数组的逆运算。对于原数组 $a[N]=[a1,a2,a3,a4,...,aN]$ ，构造差分数组 $b[N]=[b1,b2,b3,b4,b5,...,bN],a_i={\sum }_{k=1}^{k=i}{b}_k$

2、作用：在原数组的某一段区间加上一个数

3、构造思想：
$$\begin{gathered} b1=a1 \\ b2=a2-a1 \\ b3=a3-a2 \\ . \\ . \\ . \end{gathered}$$
4、核心操作：只要 $b_i+c$ 则从$a_i$ 开始往后的所有数都加上了c

12、二维差分数组

1、思想：和一维差分数组雷同。

在A点增加C的影响就是整个ACIG都被加了C，但是我们只希望ABDE被加C所以应该让BCIH和DFIG减去C，由于EFIG被减了两次所以再让它加上C。公式：$$\begin{gathered} s[x1][y1]+=c \\ s[x2+1][y1]-=c \\ s[x1][y2+1]-=c \\ s[x2+1][y2+1]+=c \end{gathered}$$

13、双指针算法

1、精髓：优化暴力枚举，两个指针分别最多只遍历一边数组

14、离散化

1、概念：将N个在数轴上分布很稀疏的数映射到一个N维数组

2、作用：降低空间复杂度

3、基本步骤：

首先创建一个空的vector，把数据一次放入，完成映射

查找时，采用二分法即可。

4、代码注意点：

（1）离散化是保序的，记得映射完了之后要进行排序，否则很难查找。

15、区间合并

1、代码注意点：

（1）不要忘记合并最后的一个区间！！！