AcWing 算法基础课 笔记

目录

• 第一章 基础算法
• • 一、排序
  • • 快速排序
    • 归并排序
  • 二、二分
  • • 整数二分
    • 浮点数二分
  • 三、高精度
  • • 高精度加法
    • 高精度减法
    • 高精度乘法
    • 高精度除法

第一章 基础算法

背算法模板，并且理解代码的思想和流程，背的不是代码，不是单词，而是思路。

针对不同模板做相应的模板题，课下做模板题，针对做过的题，课下把代码删除后再做3~5次。

数据结构与算法可视化网站：https://visualgo.net/zh

一、排序 快速排序

基于分治思想

1. 确定分界点：q[l]、q[r]、q[l+r/2]、随机值
2. 调整区间：却保左边都小于等于 分界点值 x，右边大于等于分界点值 x，分界点值不一定是中间值，可能是一个奇怪的值**——重点**
3. 递归处理 左 右 两段

（暴力方法：定义两个数组，分别存储左右区间，最后合并）

优美方法：定义两个指针，i、j，分别位于数组两端，向中间移动，直到i、j顺序都不对时，交换i、j的值

void quick_sort(vector<int>&q, int l, int r)
{
    if (l >= r) return;  //注意这里是>=
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        while (q[++i] < x);  //注意这里无论结果如何i都会+1，故初始化时i=l-1，且才能跳出循环
        while (q[--j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

快排为不稳定排序，但也可以变为稳定排序，只要将每一个数变为不同就可以，如：将 a[i]，变为 < a[i]，i >，变为一个二元组，进行双关键字排序即可。

时间复杂度
每一次划分，期望都是 n/2，每次递归的层数，期望是log n。

归并排序

思路：基于分治思想

1. 确定分界点: 中间点 mid = l+r >> 1
2. 递归排序 - 分界点左右
3. 归并——合二为一

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;  //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;  //将i，j分别指向两数组第一个元素
    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];
}

时间复杂度：
n 除了 log n 次可以除到 1，每一层的时间复杂度都是O(n)，最后的时间复杂度是：n log n

二、二分

数据有单调性，一定可以二分，可以二分的题目，并不一定有单调性。

所以二分的本质并不是单调性

二分的本质是：边界，可以划分为满足某种性质与不满足某种性质的两个区间，用二分法可以找到两区间边界的左右两个点。

数据可以划分为红色和绿色两个部分，如果判断不在红色部分，那一定在绿色部分。

1、以红色为边界点

2、以绿色为边界点

一般不需要考虑这么细。

如找到一个数的左右边界，检查的就是是否为当前数，不为则是false

整数二分

int bsearch_1(int l, int r)  //寻找右边界
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;  //右边界需+1
        if (q[mid]>k) r = mid-1;  //mid不满足<=，直接将右边界置mid左边
        else l = mid;  //左边界一点点贴近右边界
    }
    return l;
}
int bsearch_2(int l, int r)  //寻找左边界，同理
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (q[mid]<k) l = mid+1;
        else r = mid;
    }
    return l;
}

浮点数二分

void bsearch_3(double l, double r)  //所有可能的范围如[-10000,10000]
{
    const double eps = 1e-8;  //要求精度多两位
    while (abs(r - l) > eps)
    {
        double mid = (l + r) / 2;
        if (n-pow(mid,3)<eps) r = mid;  //两者不断接近
        else l = mid;
    }
    printf("%lf",r);
}

三、高精度

分为：A + B、A - B、A * a、A / a

高精度加法

1. 大整数存储，将大整数的每一位转为整数，倒叙存入数组

void add(vector<int>&a,vector<int>&b){
    if(a.size()<b.size()) return add(b,a);  //确保a>b，由于都是正整数，所以可以这么 *** 作
    int c=0;
    for(int i=0;i<a.size();i++){
        a[i]+=c;  //a+b+c（进位符）
        if(i<b.size()) a[i]+=b[i];  //注意a还有，b没了
        c=a[i]/10;
        a[i]%=10;
    }
    if(c) a.push_back(1);  //注意最后一位进位
    for(int i=a.size()-1;i>=0;i--) printf("%d",a[i]);
}

高精度减法

void sub(vector<int>&a,vector<int>&b){
    int c=0;
    for(int i=0;i<a.size();i++){  //同理变成减
        a[i]-=c;
        if(i<b.size()) a[i]-=b[i];
        if(a[i]<0) c=1;
        else c=0;
        a[i]=(a[i]+10)%10;
    }
    while(a.size()!=1&&a[a.size()-1]==0) a.pop_back();  //注意是while不是if，如果高位为0要一直减
    for(int i=a.size()-1;i>=0;i--) printf("%d",a[i]);
}

高精度乘法

乘法与加法类似，但由长整数乘以短整数，故不是一位乘一位，是以长整数的一位乘整个短整数。

void mult(vector<int>&a,int b){
    int c=0;
    for(int i=0;i<a.size();i++){
        a[i]=b*a[i];  //同理，注意先乘后加
        a[i]+=c;
        c=a[i]/10;
        a[i]%=10;
    }
    while(c!=0){  //若用新数组保存值每次push_back，for循环条件可以为a.size()||c，减少这个while语句
        a.push_back(c%10);
        c/=10;
    }
    while(a.size()!=1&&a.back()==0) a.pop_back();
    for(int i=a.size()-1;i>=0;i--) printf("%d",a[i]);
}

高精度除法

模拟除法，从高位开始，（余数*10+高位）除以除数得商的高位，%除数得新的余数，循环。

void div(vector<int>&a,int b){
    int t=0;
    vector<int> c;
    for(int i=0;i<a.size();i++){
        t=t*10+a[i];
        if(c.size()!=0||t/b!=0) c.push_back(t/b);  //用if去除高位的0，可以用reverse函数倒置去0同理
        t%=b;
    }
    if(c.size()==0) c.push_back(0);
    for(int i=0;i<c.size();i++) printf("%d",c[i]);
}