第一章 基础算法（一）

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing

前言

这里是我的刷题记录以及模板仓库，在这里我将记录我这个月的算法学习

好友也推荐了leetcode上面大佬的刷题方式，如下：

[高效刷题方法] https://leetcode-cn.com/circle/discuss/jq9Zke/

他把刷题总结成如下四点：

1. 始终保持匀速前进，既不松懈倦怠，亦不急于求成
2. 定时归纳总结, 按类训练
3. 深度理解人的记忆规律，高频率高效复习
4. 拥抱孤独, 过滤外界杂音, 平稳心态

也在他的启发下，这里我将使用整个5月把y总的算法基础课程学完，并写一些自己的刷题记录，以便自己更好的学习算法。

欲速则不达，所以每天不贪多，白天看视频，晚上写总结，第二天复习，周而复始即可。

这里我直接按照模板学习，并在学习完模板之后在进行刷题环节。

学习方式

主要学习方法：

理解算法思想 + 反复学习加深记忆

1. 代码模板背下来（主要提高部分）
2. 根据模板题目检验（重复5次）

排序

快速排序——分治

1. 确定分界点：q[1], q[(1+r)/2], q[r]，随机
2. 调整区间，左边（小于等于x）右边（大于等于x） 【核心难点】
3. 递归处理左右两段

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;//判断边界和退出条件

    int i = l - 1, j = r + 1, x = q[l + r >> 1]; //这里把中间值作为flag[这里可以写l和l+r]
    while (i < j)
    {
        do i ++ ; while (q[i] < x);//比x小的跳过
        do j -- ; while (q[j] > x);//比x大的跳过
        if (i < j) swap(q[i], q[j]);//确保在i<j前提下进行交换因为j会移动到i的左边
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);//这里根据递归重新拆分成两部分，这里用的j
}
// 如果写j的话区间一定不能取到q[r]也是一个道理

特别强调一下这j的问题为什么在最后一部分的时候使用j，使用i不行吗？

其实是可以的，但是区别在于i 也要随之变化，从 j 变成i-1；同理 j+1 变成i

主要原因是涉及边界的问题，要是取到l 就会发生死循环，例如下面这个例子可以说明

# 样例如下
2
1 2

上面的就会造成死循环，比如说递归的结果是[0,-1],[0,1]，这个[0, 1]就会一直死循环

或者使用下面的模板，推荐使用上面的

void quick_sort(int q[], int l, int r){
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = q[l+r+1 >> 1];//这里有边界问题要进行上取整，可以写r和l+r+1
    while(i < j){
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, i-1), quick_sort(q, i, r);//这里就可以使用i了
}

归并排序——双指针算法（稳定的）

1. 确定分界点mid = L+ (R - L) >> 1；
2. 递归排序left 和right
3. 归并——合二为一【核心难点】

一共logn层，每层On复杂度，所以时间复杂度是nlogn

void merge_sort(int q[], int l, int r)//整体思想是先拆分后合并
{
    if (l >= r) return; //直接退出

    int mid = l + r >> 1; //临界点
    merge_sort(q, l, mid);//先进性递归拆分
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;//在进行合并
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
//转移剩下的部分
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//从临时数组中转移到原数组中
}

二分

整数二分

只要有单调性一定可以二分，可以使用二分的题目不一定有单调性

二分本质：根据性质进行找，一半满足该性质，一半不满足该性质

所以根据性质就能把边界点二分出来，两个边界点就是两个不同的模板

二分模板介绍 https://www.acwing.com/blog/content/31/

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分算法模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度

更多因为C++的特性，所以这里涉及到高精度的问题

高精度模板

高精度加法

//高精度加法
// 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;
}

高精度减法

//高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0
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;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘低精度

//高精度乘低精度
// 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 ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度除以低精度

//高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

未完待续