基础算法 | 小样与我

type

status

date

slug

summary

排序

直接插入排序

直接插入排序就是，将整个数组看成前后两部分，前面一部分是已经排好序的，后面一部分是待排序的

每次拿出待排序部分的第一个，从排好序部分的最后一个从后往前比较，如果待排序的更小，则继续往前面去比

直到找到第一个比待排序的数更小的数，则将待排序的数放在这个数的后面

在最开始，默认第一个元素已经排好序

希尔排序

希尔排序是对直接插入排序的优化

直接插入排序所耗费的时间很大程度上取决于各个大小元素的相对位置，如果邻近的元素大小都差不多，则直接插入排序所耗费的时间将大幅度降低

希尔排序时，先将原数组进行分组，然后对每一组进行直接插入排序

分组的标准是：将数组长度，循环除2，就是分组的间隔和个数

对比：
通过类比可知，直接插入排序和希尔排序的排序部分，代码都一致，唯一的区别就在于直接插入排序的间隔是1，而希尔排序的间隔是gap，即分组的间隔
经过这种优化，希尔排序就不会超时了

简单选择排序

选择排序，第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

以此类推，直到全部待排序的数据元素的个数为零。

快速排序

找到一个标准值，通常取第一个数/中间数/随机值

双指针从两边向里面逐个比较，将小于标准值的放左边，大于标准值的放右边

递归对左右两边进行快排

冒泡排序

实现思想

通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

实现步骤

比较两个相邻的数，如果前面的数大于后面的数，则将这两个数交换位置。第一次遍历后，最大的数会被放到数组的最后位置，即array[length - 1]。

第二次遍历时跳过最后一个元素，因为该元素通过第一次遍历已经确定是最大值。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

📌

注意for循环的边界条件，只需要循环比较n-1次

归并排序

归并排序的思想是分治

实现步骤：

找到数组中点

左边、右边分别排序

左右两边合并

新开一个辅助数组
使用快慢指针
谁小谁放到新数组，相等时放左边数组的数
将新数组拷贝到原数组

📌

注意：

拷贝数组的代码需要特别注意

用vector会比用普通数组的代码，速度更慢

小和问题

问题描述：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：

[1,3,4,2,5]1左边比1小的数：没有

3左边比3小的数：1

4左边比4小的数：1,3

2左边比2小的数：1

5左边比5小的数：1,3,4,2

所以小和为1+1+3+1+1+3+4+2=16

思路：

如果使用两层循环，事件复杂度为O(N^2)

使用归并排序的思想，时间复杂度可降为O(NlogN)

将值问题，转换为个数的问题-----左边比当前数小的，就相当于，右边比当前数大的

📌

注意：

和模板代码的区别在于：

这里是比较小于，不是小于等于

模板代码中，是为了保证算法的稳定性，是小于等于

小和问题中，如果是小于等于，可能会造成右边比它大的数的个数少算

逆序对

思路：与小和问题一样，在双指针比较时，同时记录逆序对的数量即可

堆排序

如果要求排序为升序，一般采用大顶堆，每次将堆顶元素与未排序的最后一个元素交换，再调整堆。

如果要求排序为降序，一般采用小顶堆，每次将堆顶元素与未排序的最后一个元素交换，再调整堆。

桶排序

概述

桶排序又称为箱排序，是一种比较常用的排序算法

算法原理

将数组分到有限数量的桶中（主要），再对每个桶分别排好序（可以使用桶排序，也可以使用其它排序方法或库函数），最后依次将每个桶中排好序的数输出。

实现步骤

确定桶的个数：最好将数据均匀分散在各个桶中

找出所有数据中的最大值mx和最小值mn
每个桶中所装数据范围：size = (mx - mn) / n + 1;
桶的个数：cnt = (mx - mn) / size + 1;

求得了size和cnt后，即可知第一个桶装的数据范围为 [mn, mn + size)，第二个桶为 [mn + size, mn + 2 * size)，…，以此类推因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中

对各个桶中的数据进行排序，可以使用其他的排序算法排序，例如快速排序；也可以递归使用桶排序进行排序

将各个桶中排好序的数据依次输出，最后得到的数据即为最终有序。(同样可以依次放入原数组中，再对原数组进行输出)

基数排序

计数排序

二分

最好的模板（下标从1开始）

最大化查找：查找最后一个≤q的数的下标(可行区在左边）

最小化查找：查找第一个≥q的数的下标（可行区在右边）

📌

满足条件的区域称为可行区

指针的跳跃次数logn

l + 1 = r时结束

可行区的指针最后一定指向答案

开区间可以正确处理边界

二分查找

一元三次方程求解

最好的套路

解答此类二分问题：

先确定x的最大化答案还是最小化答案

再确定x,y的关系（增函数还是减函数）

最后确定c以及check的条件

📌

此题与前面的题目有所不同

此题的y只有真和假两个值，而不是一个连续的变量

可以暴力枚举，但O(mn)会超时

涉及了差分与前缀和，时间优化为O(m + n)

高精度

前缀和

一维前缀和--区间和

暴力：时间复杂度为O(nm),会TLE

外层循环枚举

内层循环枚举区间求和

📌

前缀和可以优化内层循环

前缀和

区间和

📌

二维前缀和--激光炸弹

暴力：时间复杂度为O(m^4),会TLE

外两层循环枚举正方形的位置

内两层循环枚举区间求和

📌

二维前缀和可以优化内层循环

二维前缀和：

二维区间和：

树状前缀和—求和

📌

题目多次询问树上的一些路径的权值和，就要烤炉树上前缀和了

点前缀和：

边前缀和：

差分

一维差分

定义：

📌

b是a的差分序列，a是b的前缀和序列，由此可以看出差分与前缀和是一对互逆运算

差分思想：

把序列a的区间[l, r]加d，等价于其差分序列b的点b[l]加d，点b[r + 1]减d，其它位置不变。

把原序列的“区间操作”转换为差分序列的“两点操作”。多次区间操作完成后，再利用前缀和进行还原。从而可以将时间复杂度从O(n^2)降为O(n).

模板题：IncDex Sequence

这道题如果暴力求解，最大数与最小数之间的范围是0~2.1 * 10^9（2^20大约是10^6),逐个加1枚举，会TLE。

解题思路：

先求出a的差分序列b

将对a的区间操作，转化为对b的两点操作，最终的目的就是将b2,b3……，bn全变为0

在差分序列中的操作一共有如下四种可能：

对上面四种情况进行下图分析，可知：最终最少操作次数为max(p,q)次,可能序列有abs(p - q) + 1种

二维差分--地毯

📌

二维差分：

逐行做差分

逐行进行还原

树状差分--Max Flow P

多次对树上的一些路径做加法操作，然后询问某个点或某条边经过操作后的值，就要考虑树上差分了。

树上点差分

树上边差分

📌

如果初始各点的点权不为0，怎么做？

先计算出各点点权的差分值：

叶子节点的差分值 = 自己的点权
其它节点的差分值 = 父权 - 子权和

然后做多次的差分操作

最后计算节点差分值的子树和

双指针

严格的来说，双指针只能说是是算法中的一种技巧。

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

📌

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。

在使用双指针法时，要注意快慢指针的具体含义

最常见的双指针算法有两种

在一个序列里边，用两个指针维护一段区间

在两个序列里边，一个指针指向其中一个序列，另外一个指针指向另外一个序列，来维护某种次序。

双指针算法的核心思想（作用）：优化

在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法对暴力算法进行优化.

由于具有某种单调性，朴素算法往往能优化为双指针算法。
区别：
朴素算法每次在第二层遍历的时候，是会从新开始（j会回溯到初始位置），然后再遍历下去。（假设i是终点，j是起点）双指针算法：由于具有某种单调性，每次在第二层遍历的时候，不需要回溯到初始位置（单调性），而是在满足要求的位置继续走下去或者更新掉。

经典题

📌

上面算法的思路是：用vector数组来记录每一个数字出现的次数，如果出现的次数大于一次，就让慢指针不断向前，直到那个数字出现的次数为一次，最后让之前的res与现在的长度进行对比，选择更长的那个。因为可能会出现：两个相同数字相邻的情况，也正因如此，这种方法不方便记录最长字串