算法基础（以acwing报告次序为主，讲的很简单（有点不清不楚），主要用作看完视频复习，各人照旧去看视频好一点）

算法的界说

这是我从百度上面搜的界说
算法（Algorithm）是指解题方案的精确而完备的形貌，是一系列办理题目标清晰指令，算法代表着用体系的方法形貌办理题目标战略机制。也就是说，可以或许对肯定规范的输入，在有限时间内得到所要求的输出。如果一个算法有缺陷，或不得当于某个题目，实行这个算法将不会办理这个题目。差异的算法大概用差异的时间，空间或服从来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
空间复杂度： 实在也就相当于我们用了多少的内存空间
时间复杂度： 也就是实行我们这个算法所要泯灭的时间
在算法题中，会有对时间和空间（但是空间对我们的限定不大，每每轻易卡在时间上面）的要求，所以我们学习算法，必须要相识这个算法对应的时间和空间复杂度，我们写题目标时间每每都是被时间卡了，导致超时
一、基础算法

排序

排序我们知道有许多种排序，但是最常见的实在就十大排序，分别为插入排序，选择排序，冒泡排序，希尔排序，归并排序，快速排序，堆排序，计数排序，基数排序，桶排序.
由于本人现在学习算法只学习了快速排序和归并排序，所以先讲这两个，平常用的多的也是这两个（后续有时间再补上去）
快速排序： 快速排序的根本思绪是在我们给定的数组中，随机选择数组中的某个元素，将大于这个元素的别的元素排到它的右边，小于的排到它的左边，然后递归的举行这个过程，这个递归的过程实在也用到了分治的头脑，末了得到的就是我们排好序的数组
下面是代码

1. void sort(int q[], int l, int r)
2. {
3.     if (l >= r) return;
5.     int i = l - 1, j = r + 1, x = q[(l + r) / 2];
6.     while (i < j)
7.     {
8.         while (q[++i] < x);
9.         while (q[--j] > x);
10.         if (i < j) swap(q[i], q[j]);
11.     }
12.     sort(q, l, j), sort(q, j + 1, r);
13. }

复制代码

下面我来讲解一下这段代码，由于我们要用到递归所以我们要设置返回条件，也就是当l>=r的时间就返回，由于这个时间两者都指向的是一个雷同的值，分析我们已经将这个数组分到最小的环境，也就是只有一个元素的环境，那么这一个元素也就是已经排好序的环境，我们直接返回就行了
我先来讲一下这个while循环的思绪，再讲一下为什么用的是l-1而不是l，我们的思绪实在很简单，就是我们不断让i向中央靠拢，直到遇到一个大于x的数，就停下来，由于大于x的数应该是在x的右边而不是左边，同理也让j不断向中央靠拢，末了我们互换两个数的位置就可以了，那么这个循环竣事后，x的左边都是小于即是它的，右边都是大于即是它的
那为什么这里用的是l-1呢，由于当我们互换完后，我们必要让 i 指向下一个元素，让j指向它前面的一个元素，所以互换完后要先让 i 举行加一操纵，j 举行减一操纵，由于我们必要从第一个元素开始比力，所以要让 i 酿成 l-1，如许加1后就指向的是我们数组的第一个元素位置
末了举行递归的操纵就可以得到我们排好序的数组了
快速排序它由于用到了递归的过程，而我们知道递归好坏常占用内存的，所以当数据输入量很大的时间，大概会出现内存不敷的环境，而且快速排序在某些环境下时间复杂度是O（n的平方），最优的时间复杂度是（nlogn），这取决于我们函数里的中央值怎么取（也就是x变量），如果取的不好，时间复杂度也很高
那么接下来我就来先容一个时间复杂度稳固的排序，那就是归并排序
归并排序： 归并排序的时间复杂度是O（nlogn），很稳固，由于在递归的过程，每次都将数组分为两个子块（岂论什么环境），但是归并排序必要额外开一个和数据大小雷同的数组用来作为中央变量存放我们排好序的值。
归并排序的根本思绪：起首就是二分，不断的举行二分，直到分到只剩一个元素的时间，那么一个元素分析已经排好序了，就直接返回（也就是l==r），更前面的快速排序返回条件一样，只不外快速排序是先排序后递归，归并排序是先递归后排序，下面是代码

1. void sort(int q[],int tmp[], int l, int r)
2. {
3.     if (l >= r) return;
5.     int mid = (l + r) / 2;
6.     sort(q, tmp, l, mid),sort(q, tmp, mid + 1, r);
8.     int k = 0, i = l, j = mid + 1;
9.     while (i <= mid && j <= r)
10.         if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
11.         else tmp[k ++ ] = q[j ++ ];
13.     while (i <= mid) tmp[k ++ ] = q[i ++ ];
14.     while (j <= r) tmp[k ++ ] = q[j ++ ];
16.     for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
17. }

复制代码

由于用到了递归，所以一开始我们就要设置返回条件，之后算出我们的中央位置，也就是mid的值，之后举行分治，将数组分别为更小的子数组，我照旧重点讲一下这个循环
这个循环就是将我们分别的左边数组的值与右边数组的值举行比力，效果小的就放入我们的中央数组tmp内里，当我们左边的数组大概右边的数组的值都放完的时间就竣事了循环，这时由于我们有一边的值肯定没有放完，但是我们不确定是哪一边的值，所以利用了两次while循环，将剩下的元素放进我们的tmp数组里，将值放进tmp数组里的过程也就是归并操纵，末了将tmp数组的里的值赋值到原来数组的位置，我举个例子各人应该能更加轻易明白
假设一开始原始数组的值为1 5 6 2 4，那么当我们举行归并的时间，这时我们中央值mid为2（假设数组的下标从0开始），i为0，j为3对应的值为3，那么我们就开始举行比力，第一次循环后tmp数组里的值为1，第二次循环后的值为 1 2，第三次为 1 2 4，这时我们看到mid右边值都已经放进我们的tmp数组里了，j为5，这时i为1，左边数组的值并没有放完，那么我们就举行while循环，直接将值放进tmp数组里（这里有些人大概会问了，那会不会出现左边的值并没有排好序的环境呢，不会，由于我们是一开始就举行递归，递归到只剩一个元素时才返回，那么每次返回后将排好序的举行归并，那么就包管了返回后我们的子数组肯定是排好序的），我们末了得到的tmp数组就是1 2 4 5 6，末了将值重新返回我们原来的数组里，得到的就是我们排好序的数组了
二分

二分的核心思绪就是每一次讲区间分为一半，检察谁人中央点是否符合我们的要求，如果不符合，根据条件将左端点和右端点分别举行修改，二分常常用来举行差值，由于二分查找的服从很快，时间复杂度是logn
下面是伪代码

1. int 函数名(int l, int r)
2. {
3.     while (l < r)
4.     {
5.         int mid = l + r >> 1;
6.         if (check(mid)) r = mid;    // check()判断mid是否满足性质
7.         else l = mid + 1;
8.     }
9.     return l;
10. }

复制代码

我们要注意的是这只是二分的此中一种模板，我们可以根据这个模板举行修改，但是要注意我们的核心就是将区间分为一半
高精度

什么是高精度，就是当我们数非常非常大的时间，好比说上百位，上千位，那么这时间我们要想举行加减乘除的运算就不能用我们常规的a+b操纵了，而是要用高精度来举行运算，高精度运算也有加减乘除，下面先讲加法

1. vector<int> add(vector<int> &A, vector<int> &B)
2. {
3.     if (A.size() < B.size()) return add(B, A);
5.     vector<int> C;
6.     int t = 0;
7.     for (int i = 0; i < A.size(); i ++ )
8.     {
9.         t += A[i];
10.         if (i < B.size()) t += B[i];
11.         C.push_back(t % 10);
12.         t /= 10;
13.     }
15.     if (t) C.push_back(t);
16.     return C;
17. }

复制代码

在这里我们要注意传进来的A数组和B数组是反向放置的，好比说一开始我们输入的是123，应该要将A数组的元素酿成321，如许方便盘算，由于我们大概会产生进位，反向放置可以让我们的进位直接放在A数组的末端而不是A数组的开头
在这里我们要注意如果说A的位数小于B的位数，那么我们就必要再次调用这个函数add(B,A),为什么呢，由于我们的加法操纵默认A的位数要大于B的位数，否则会出现错误
在这里我们用t来表示是否产生进位，每次都加上这个进位
那么怎样举行输入，可以如许做

1. string a,b;
2. vector<int> A,B;
3. cin>>a>>b;
4. for(int i=a.size()-1;i>=0;i++) A.push_back(a[i]-'0');
5. for(int i=b.size()-1;i>=0;i++) B.push_back(b[i]-'0');

复制代码

再讲减法

1. vector<int> sub(vector<int> &A, vector<int> &B)
2. {
3.     vector<int> C;
4.     for (int i = 0, t = 0; i < A.size(); i ++ )
5.     {
6.         t = A[i] - t;
7.         if (i < B.size()) t -= B[i];
8.         C.push_back((t + 10) % 10);
9.         if (t < 0) t = 1;
10.         else t = 0;
11.     }
13.     while (C.size() > 1 && C.back() == 0) C.pop_back();
14.     return C;
15. }

复制代码

在函数的末了我们必要去除多余的0，好比说123-123，如果不去除，那么末了的效果就会是000
其余的跟加法差不多
再讲乘法

1. vector<int> mul(vector<int> &A, int b)
2. {
3.     vector<int> C;
4.     int t = 0;
5.     for (int i = 0; i < A.size() || t; i ++ )
6.     {
7.         if (i < A.size()) t += A[i] * b;
8.         C.push_back(t % 10);
9.         t /= 10;
10.     }
12.     return C;
13. }

复制代码

乘法最关键的就是一个点，那就是进位，所以我们这里利用了t来保存我们的进位，其余的也比力好明白
末了是除法

1. vector<int> div(vector<int> &A, int b, int &r)
2. {
3.     vector<int> C;
4.     r = 0;
5.     for (int i = A.size() - 1; i >= 0; i -- )
6.     {
7.         r = r * 10 + A[i];
8.         C.push_back(r / b);
9.         r %= b;
10.     }
11.     reverse(C.begin(), C.end());
12.     while (C.size() > 1 && C.back() == 0) C.pop_back();
13.     return C;
14. }

复制代码

除法和乘法差异，除法我们要从最高位开始除
r实在是我们每次除外之后的余数，由于借位原则，每次我们必要乘以10再加上A的值，在循环竣事后我们要举行翻转（为什么要翻转，由于我们要同一格式，只管不翻转也能正常输出，但是由于之前的加减乘除都是倒序输出的，所以我们这里也采用倒叙输出，同一格式，好比我们在面临某些题目标时间大概加减乘除都必要用上，这时格式的同一方便我们操纵），在末了我们依然要清晰多余的0
前缀和与差分

前缀和用于处理什么题目呢，那就是累加，假设我们面临如许一个题目，给我们一个已有数据的数组，要我们依次求数组前1个元素的和，前2个元素的和，前3个元素的和，前4个元素的和，直到前n个元素的和，那么如果我们还像从前那样用双层循环累加那么时间复杂度有点高，我们可以用一个数组来依次存储前n个元素的和，而且时间复杂度很低

1. for(int i=1;i<=n;i++){
2.     S[i]=S[i-1]+a[i];
3. }

复制代码

如许我们只必要一重循环就可以得到我们想要的效果了
二维前缀和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：

1. S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

复制代码

为何是如许，请看下图（本身画的有点貌寝）

假设我们是五行五列，如果我们想要求某个区域的值，就要减去S[x1-1,y2]和S[x2,y1-1]，由于有一个区域我们减了两次，所以我们要加上来，如果我们想要求前缀和，那么就要将式子酿成s[x2-1,y2]+s[x2,y2-1]+s[x2-1,y2-1]+a[x2,y2]，至于为什么就不多表明了，分析过程跟图中差不多
讲完了前缀和，那么我们再来讲讲差分，为什么要利用差分呢，我们思量下面这个题目，假设给我们一个有数据的数组，要我们对区间[l,r]间的元素加a大概减a，然后求其前缀和，我们固然会用暴力的做法去做，固然没错，但是我们可以更加简化
先想想我们的前缀和，如果我们将数组 l 的值加上了a，那么在求前缀和时，l背面的值都会加上a，这显然不符合我们的预期，那么我们可以在r+1处减去a，那么一加一减对r背面的前缀和没有影响，代码也很简单

1. B[l] += c, B[r + 1] -= c

复制代码

二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的全部元素加上c：

1. S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

复制代码

这个分析各人可以本身去分析为什么是如许
双指针算法

双指针常见题目分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种序次，好比归并排序中归并两个有序序列的操纵
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体题目
双指针算法实在模板很简单，实在最难的是我们要怎样找到题目中的双指针逻辑，怎样看出这是一个双指针题目
位运算

这个实在很简单，照旧看具体题目具体分析，我们要把握语法中根本的运算符（好比与，或，非）

1. 求n的第k位数字: n >> k & 1

复制代码

离散化

离散化用于办理我们题目呢，就是当我们数的范围很大但是个数却很小时，就好比数的范围是10的负9次方到10的9次方，但是我们的数据个数大概只有几十个，好比下面的题目

对于这种题目我们就要对其举行离散化处理

1. vector<int> alls; // 存储所有待离散化的值
2. sort(alls.begin(), alls.end()); // 将所有值排序
3. alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

复制代码

最核心的步调就是去重
区间归并