基础算法模板

摘要：
详尽地记录了各种基础算法模板，以及一些个人理解。

排序

快速排序

快排最难的地方在于边界问题。边界问题涉及到比较因子的选择以及各种条件判断。建议将模板直接背过。
今天看了闫学灿的快排讲解之后，感悟颇多，特地记录下来供以后复习。
首先上快排模板：

void qSort(int q[], int lo, int hi) 
{
    if (lo >= hi) return; //end of recursion
    int cmp = q[(lo + hi) >> 1];
    int i = lo - 1, j = hi + 1; // 每次指针移动，需要向中间偏移一位，故在这里也初始化设置成lo - 1和hi + 1
    for (;i < j;) 
    {
        for (; q[++ i] < cmp; );
        for (; q[-- j] > cmp; );
        if (i < j) swap(q[i], q[j]);
    }
    qSort(q, lo, j); //                         1
    qSort(q, j + 1, hi); //                     2
}

由于 j 要么等于 i 要么 j 在 i 左边一位，故其中 1 和 2 可以改成：

qSort(q, lo, i - 1); 
qSort(q, i, hi);

但是注意，如果 cmp 设置成 q[lo] 的话，则只能是：

qSort(q, lo, j); 
qSort(q, j + 1, hi);

因为如果换成了

qSort(q, lo, i - 1); 
qSort(q, i, hi);

的话会出现死循环问题。
举个例子：数组{1, 2}排序，lo = 0, hi = 1, i = -1 , j = 2, cmp = 1.
第一轮递归，i = 0, j = 0.
qSort(q, 0, -1); 直接return.
qSort(q, 0, 1); 死循环.

同理，如果 cmp 设置成 q[hi] 的话，使用

qSort(q, lo, j); 
qSort(q, j + 1, hi);

也会发生死循环.

所以：
cmp 设置成 q[lo] 的话，递归调用必须是：

qSort(q, lo, j); 
qSort(q, j + 1, hi);

cmp 设置成 q[hi] 的话，递归调用必须是：

qSort(q, lo, i - 1); 
qSort(q, i, hi);

为了保险起见，建议将 cmp 设置成中间位置。

归并排序

归并排序是将原数组递归地一分为二，在最短子数组处完成排序，在回溯过程中合并子数组，以完成整个数组的排序。
过程感觉很像二叉树的遍历。
以下是归并排序模板：

const int N = 10000010;                                     // test data amount range
int q[N];                                                   // original array
int tmp[N];                                                 // temporary array
void merge_sort(int q[], int lo, int hi)
{
    if (lo >= hi) return;                                   // end of recursion
    int mid = (lo + hi) >> 1;                               
    merge_sort(q, lo, mid), merge_sort(q, mid + 1, hi);     // recursively divides into two
    // backtrack progress
    int i = lo, j = mid + 1;                                 
    int t = 0;                                              // index of temporary array            
    for (;i <= mid && j <= hi;)                             // puts smaller one into tmp[]
        if (q[i] <= q[j]) tmp[t++] = q[i++];
        else tmp[t++] = q[j++]; 
    for (;i <= mid;) tmp[t++] = q[i++];                     // puts remaining array into tmp[]
    for (;j <= hi;) tmp[t++] = q[j++];
    for (int i = lo, j = 0; i <= hi;) q[i++] = tmp[j++];    // overrides original array
}

因为一分为二的过程一共持续 log(N) 次（以2为底）,把数放入 tmp[] 再覆盖原数组需要 O(N)。
故时间复杂度为 ONlog(N)

二分查找

整数二分查找

一般涉及到单调性的问题，查找某个边界，可以使用二分查找。但是二分查找不仅仅只适用于单调性问题。
即：
单调性问题查找一定可以用二分，非单调性问题也有可能可以用二分。
二分查找的本质目的是：
在一个整数区间上，前一段满足某种性质A，后一段满足另一性质B。使用二分查找找到满足性质A的边界点edgeA或者满足性质B的边界点edgeB。
____________Satisfied A______________| |___________Satisfied B________________
整个查找过程围绕 性质 展开，不断更新mid值，从两个方向逼近边界。但是请注意，这个 性质 并非必然和目标值有关。找目标值，在考虑性质的时候，不一定从目标值入手（这一点非常重要，请仔细体会）。

找A的边界，mid从A向右更新
当mid满足条件A时，A的边界至少可以取到mid；
找B的边界，mid从B向左更新
当mid满足条件B时，B的边界最多可以取到mid；

整数二分查找模板：
查找A边界

// finds edge A
bool is_satisfied_A(int x) {/*---*/};
bool is_satisfied_B(int x) {/*---*/};

int binary_search(int lo, int hi)
{
    for (;lo < hi;)
    {
        int mid = (lo + hi) >> 1;                      //  1
        if (is_satisfied_B(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

查找B边界

// finds edge B
bool is_satisfied_A(int x) {/*---*/};
bool is_satisfied_B(int x) {/*---*/};

int binary_search(int lo, int hi)
{
    for (;lo < hi;)
    {
        int mid = (lo + hi + 1) >> 1;                   // 2
        if (is_satisfied_A(mid)) lo = mid;
        else hi =  mid - 1;
    }
    return lo;
}

注意：2处为了防止边界问题，需要在计算mid的时候加一。

题目链接：

数的范围
寻找旋转排序数组中的最小值

浮点数二分查找

根据精度迭代

因为是找浮点数，所以可以不用考虑边界问题。
例子：
求数字x的开方。

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    double x;
    cin >> x;
    double lo = 0, hi = max(1, x);                      // 1
    for (;hi - lo > 1e-8;)
    {
        double mid = (lo + hi) / 2;
        if (mid * mid >= x) hi = mid;
        else lo = mid;
    }
    printf("%lf\n", lo);
    return 0;
}

注意1处当x<1时，右边界是1。因为小于1的数，开方比自己大。x>1时，右边界当然可以取到x。
题目中一般会给出x的取值范围，如 -10000 < x < 10000，那么lo和hi可以分别初始化为-10000和10000。
根据经验，如果题目要求保留n位有效数字，那么一般lo和hi之间判定的精度为1e-(n + 2)。

根据循环次数迭代

这是浮点数二分的另一种写法，直接循环个100次。
如上题：

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    double x;
    cin >> x;
    double lo = 0, hi = max(1, x);
    for (int i = 0; i < 100; i ++)
    {
        double mid = (lo + hi) / 2;
        if (mid * mid >= x) hi = mid;
        else lo = mid;
    }
    printf("%lf\n", lo);
    return 0;
}

这相当于把lo到hi范围缩小2的100次方倍。（100次2分）
因为2的100次幂足够大，所以结果是正确的。

高精度四则运算

高精度加法

两个 超长位数正整数 相加，一般是以 字符串 形式读取整数，再把整数放入 数组 中，进行模拟加法运算。
模板1：

// C = A + B, A >= 0, B >= 0
#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)                             //1
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i++)                      //2
    {
        if (i <= A.size()) t += A[i];
        if (i <= B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);                                                  //3
    return C;
}


int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i-- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i --) cout << C[i];
}

注释：

1. 以数组引用传入参数，可以避免没必要的数组拷贝。
2. A或B至少有一个没有遍历完，都需要继续计算。
3. 注意结束之后进位有可能非0.

该模板可以改写成总是模拟以一个更长的数组加长度较小的数组：
模板2：

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

这样的话，就可以只考虑遍历较长数组，只进行一次长度判断。

题目链接：

高精度加法

高精度减法

两个超长正整数相减。因为结果可能为负数，负数的时候输出需要在最前面补'-'。
A B相减最核心的部分，A总是大于等于B的，这样可以只遍历A，对对应的B有无数字进行判断。
模板：

//C = A - B， A >= 0, B >= 0
#include <iostream>
#include <vector>

using namespace std;

// return if A >= B
bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i -- ) {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true;
}

// A - B while A >= B
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ ) {
        t = A[i] - t;
        // consider if should sub slot of B
        if (i < B.size()) t -= B[i];
        // t might be a negative
        // t will be the right slot whatever its negative or positive
        // t + 10 means it will borrow 10 from next slot
        C.push_back((t + 10) % 10);                                          //1
        // update t
        if (t < 0) t = 1;                    
        else t = 0;
    }
    // there might be some '0' in back of C
    // dont't have to remove while C.size() == 1
    for (; C.size() > 1 && C.back() == 0; ) C.pop_back();                    //2
    return C;
}


int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B, C;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    if (cmp(A, B)) C = sub(A, B);
    else {
        C = sub(B, A);
        printf("-");
    }
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    return 0;
}

1. 此处t有可能被减成了负数（最低可以取到-10，最高可取到9），此时向后一位借10，于是最低取到0；同时由于借10的时候并没有判断正负，所以+10可能会导致结果高于10。也就是说，此时运算过程放入C中的数可能的取值范围是：(0, 19)。这样我对10取模，即可得到正确的放入C中的数了。
   注意，在把“优化”后的（指借位模10）运算结果放入C时，并没有把结果赋值给t，因为后面需要判断t的正负，以更新下一轮的t取值。如果赋值了，则t必然为正，无法更新进位信息。
2. 注意当A与B前几位部分相等时，C后面会存在’0’，如123 - 120结果类似003。但在结果仅为1位时，不用考虑。

题目链接：

高精度减法

高精度乘法

一个超长正整数乘一个普通int正整数。模拟相乘过程把普通int整数看成一个整体。
模板1：

// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )                       //1
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);                                        //2
        t /= 10;                                                    
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

1. 注意1处条件，当A没有遍历完的时候，需要一直和b相乘，更新进位t。当乘完的时候，依然进入处理进位t，只不过此时不需要和b相乘，而是直接模10获得最高位数。
2. 放入slot中的数一直都是对10取模。
3. 当小整数为0，而大数不止一位时，结果会产生多个0.此时需要消除多个0.

当然也可以在遍历完A后再处理最终进位问题，即：
模板2：

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ) {
        t = A[i] * b + t;
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    for (;C.size() >  && C.back() == 0;) C.pop_back();
    return C;
}

注意： 在处理最终进位t的时候，模板1是对t再进入循环处理，这时候如果t < 10的话，只循环一次，但是如果t >= 10的话，需要反复进入循环，依次取模，除10.

题目链接：

高精度乘法

高精度除法

一个超长正整数除以一个短正整数。
和高精度加减乘不一样的是，高精度除法是从大整数高位开始的。在复习了小学二年级下册的相关内容后，我觉得算法基本上就是模拟除法竖式。
高精度加计算过程会产生进位，减计算过程会产生借位，乘计算过程会产生进位，而高精度除法计算过程会产生余数。
余数作为下一位的高位需要乘10进行新一轮的除法运算。
模板：

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

1. 初始化余数raka remain。
2. 对于被除数A的每一位，需要将上一位除法运算产生的余数作为当前数的高位乘10加上当前数。
3. 用当前数作为被除数和除数b进行除法运算，放到结果槽中。
4. 将余数保留给下一位。
5. 首位可能产生0，所以我们将结果数组反转再去除结尾0.

题目链接：

高精度除法

前缀和

对于一个给定数组alls[N]，其前缀和数组s[N]对应着对于alls[N]的每一个元素，其前缀所有元素（包括这一位）之和。
前缀和数组的应用一般伴随着一些查询操作，一个查询操作就是给定一个区间范围，让你求该范围内数的和。
另外，注意构造前缀和数组是从下标1开始构造，整体数目不变。相当于是数组下标向右偏移一位。这是因为构造前缀和数组的每一位需要依赖其前一位。当构造第1位时，需要依赖第0位。
模板：

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

题目链接：

前缀和

双指针

双指针的核心思想，是在暴力求解的基础上，通过已知的某种性质，用两个指针进行优化。
模板：

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}

常见问题分类：

• 对于一个序列，用两个指针维护一段区间
• 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

题目链接：

最长连续不重复子序列

离散化

当有一堆数，总量不多，比如说1e5，不算多，但是每个数可能取到很大值或很小值，比如说最大取到1e10。那么在需要把数值当成数组下标进行操作的时候，比如说计数数组，无法开出如此大空间的数组，这时候就需要离散化操作。
离散化：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
模板：

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
}

• 离散化的映射，主要是将待离散化的数放到容器中，进行排序、去重，再用二分查找找到对应下标，将下标放到一个数组中。
• 排序：一般是通过二分查找的方式进行下标映射，所以需要对原数据排序。
• 去重：因为要将待离散化数映射成各自的下标，所以需要对其去重复。
• 注意离散化操作的重要前提是，原数据本身的值并不重要，我们不感兴趣，重要的是其位置。

题目链接：

区间和

区间合并

现有若干区间，相互之间可能相交。将所有相交的区间合并为一个区间，返回合并后的区间。
模板：

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());                             // 1

    int st = -2e9, ed = -2e9;                                   // 2
    for (auto seg : segs)
        if (ed < seg.first)                                     // 3
        {
            if (st != -2e9) res.push_back({st, ed});            // 4 
            st = seg.first, ed = seg.second;                    // 5
        }
        else ed = max(ed, seg.second);                          // 6

    if (st != -2e9) res.push_back({st, ed});                    // 7

    segs = res;
}

segs存放的是所有区间的左右端点构成的pair。
算法思想是维护一个前置区间，维护一个当前区间。比较两个区间是否相交，不相交就认为前置区间是一个孤立区间。不管是否相交，更新前置区间的左右端点，在更新当前区间左右端点。当最后一个当前区间与其前置区间比较完毕后，不管二者是否相交，最后一次更新前置区间将不会有新的当前区间。此时新的前置区间将必然是一个孤立区间。

• 1. 区间按照左端点排序。sort()用于排序pair类时，默认按照左端点升序排序。
• 2. 初始化区间左右端点，后面会更新它们。这里是初始化为无穷小（相对来说），初始化值在不同题目可以按需调整。
• 3. 比较两个区间是否相交。
• 4. 因为初始化的前置区间是无穷小的一个点，所以当前区间是第一个区间时，必然成立。但我们不能将无穷小点放入res中。只有在前置区间从第一个区间开始时，满足3的条件才可以放入res中。
• 5. 不相交情况下更新前置区间左右端点。
• 6. 相交情况下更新前置区间左右端点。（此时只需更新右端点）
• 7. 处理最后一个前置区间，此时前置区间必然是孤立区间当且仅当区间集合segs非空时（或者说当且仅当前置区间非初始化值时）

题目链接：

区间合并