算法基础课(持续更新中)

发表于 2025-02-14 更新于 2026-02-15 分类于算法题阅读次数：

| 置顶

本文字数： 43k 阅读时长 ≈ 1:18

算法基础课

基础算法（一）

快速排序

1.很久没刷算法题后重新开始刷，发现了容易遗忘的一些点：

（1）const int N=多少是依据题目给出的范围去推断，比如这里快排题要求数组中数字范围是1-100000，那就写成1-100010（多开10防止爆数组），然后再接上对数组的定义int q[N]，这样就可以保证开的数组位置是一定管够的。

（2）对于这种功能是处理xxx的函数通常定义为void。

（3）写代码时可以先把int main也就是有关输入、函数调用和输出的部分先写好，再去写具体函数的内容，这样可以减轻处理题目的逻辑容量。

2.关于quick_sort与分治：

（1）分治通常就是按下面这种形式写：

void function(xxx)
{
    //1.处理边界
    if(边界条件)return xxx;//比如这里就是不能使左边界大于右边界所以直接return
    
    //3.写具体处理逻辑
    xxx;
    
    //2.写递归调用
    function(xxx);
    function(xxx);
}

（2）quick_sort具体处理逻辑部分

int x=q[(l+r)>>1],i=l-1,j=r+1;//定义分界点pivot以及左右指针，-1/+1是因为每一次对i/j循环时都会先++/--

while(i<j)
{
    do(i++);while(q[i]<x);
    do(j++);while(q[j]>x);
    if(i<j)
        swap(q[i],q[j]);//这一步是指在i<j的前提下当i/j的俩while循环都无法继续工作，说明此时指向的数字分别都不是对应序列的数字，就需要交换位置来使该位置数字回到正确序列中；然后再重新while循环
}

3.完整代码

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N];

void quick_sort(int q[],int l,int r)
{
    if (l>=r)return;
    int x=q[(l+r)>>1],i=l-1,j=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,j);
    quick_sort(q,j+1,r);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++)
    {
        printf("%d ",q[i]);
    }
    return 0;
}

归并排序

1.为什么快排是先处理再递归，而归并是先递归再处理？

归并排序采用的是“后序遍历”思想，必须先通过递归把数组切分到不能再分的单元素状态（此时自然有序），然后在回溯阶段才能将这些有序子序列合并；而快排采用的是“先序遍历”思想，先通过分区逻辑确定一个基准点的位置，再据此划分区间继续向下递归。

2.为什么归并处理边界时必须使用小于等于号？

因为在归并排序的代码逻辑中，mid 和 r 都是闭区间内真实存在的合法下标，如果不加等号，循环就会在处理到最后一个元素之前提前跳出，导致区间边界上的那个数据被遗漏在排序过程之外。如题目要求合并两个只有 1 个元素的区间，左边是 q[0]（此时 mid=0），右边是 q[1]（此时 r=1）。如果你写 i < mid（即 0 < 0），判断条件立刻失效，循环一次都不会执行，这两个数就永远没法被装进结果数组 tmp 里。

3.完整代码

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N],tmp[N];

void merge_sort(int q[],int l,int r)
{
    //1.处理边界
    if(l>=r)return;
    
    
    int mid=(l+r)>>1,i=l,j=mid+1,k=0;
    //2.递归调用归并（和快排不一样）
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    
    //3.具体归并逻辑
    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(int i=l,j=0;i<=r;i++,j++)
        q[i]=tmp[j];
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",q[i]);
    return 0;
}

4.板子

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];
}

5.用归并排序求逆序对

（1）为什么用 long long 而不直接用 int

因为在 $10^{5}$ 的数据规模下，最坏情况（如数组完全逆序）产生的逆序对数量约为 $\frac{n (n - 1)}{2} \approx 5 \times 10^{9}$ ，这已经超过了 int 类型约 $2 \times 10^{9}$ 的最大承载极限。

（2）为什么 res += mid - i + 1

可以理解为merge_sort在执行具体操作之前就已经是一个划分成单个数字组成的有序数列。此时左半区间是有序的，一旦发现 $q [i] > q [j]$ ，就意味着从 $q [i]$ 到 $q [m i d]$ 的所有元素（一共 $m i d - i + 1$ 个）都必然比 $q [j]$ 大，因此 $q [j]$ 与这一整段都能构成逆序对。

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N],tmp[N];

long long merge_sort(int q[],int l,int r)
{
    if(l>=r) return 0;
    
    int mid=(l+r)>>1,i=l,j=mid+1,k=0;
    
    long long res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);//相当于把merge sort改造成输出是数字，然后在
    
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])tmp[k++]=q[i++];
        else 
        {
            res+=mid-i+1;
            tmp[k++]=q[j++];
        }
    }
    
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    
    for(int i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
    
    return res;
}


int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&q[i]);
    printf("%lld",merge_sort(q,0,n-1));
    return 0;
}

二分

整数二分

1.思路

（1）整体思路就是先考虑数组中位数值q[mid]>k再考虑q[mid]<k的判断，据此不停变换左右边界l/r的取值，最终收束得到k的左右边界取值，输出时均以左边界l为取值；

（2）需要注意的是边界一旦涉及mid-1的操作时取mid=(l+r+1)>>1要有这个＋1，不然-1之后mid无法更新就会死循环；此外在跑完k的左边界并输出l后要记得更新l=0,r=n-1这个操作重新计算，不然此时数组边界已经收束就无法再计算k的右边界。

2.题目：789. 数的范围 - AcWing题库

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N];

int main()
{
    int n,m,k;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    while(m--)
    {
        scanf("%d",&k);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(q[mid]<k)l=mid+1;
            else r=mid;
        }
        if(q[l]!=k)printf("-1 -1\n");
        else
        {
            printf("%d ",l);
            int l=0,r=n-1;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(q[mid]>k)r=mid-1;
                else l=mid;
            }
            printf("%d\n",l);
            
        }
        
    }
    
    
    return 0;
    
}

3.板子

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;
}

浮点数二分

1.思路

先看题目保留n位小数，那么精度就要对应是n+2位小数（比如保留六位小数那么范围就是1e-8）；然后取一个必定包含取值范围的左右边界初始值，然后正常取中点计算即可。

2.题目：790. 数的三次方根 - AcWing题库

#include<iostream>
using namespace std;

int main()
{
    double n;
    cin>>n;
    double l=-100,r=100;
    while(r-l>1e-8)
    {
        double mid=(l+r)/2;
        if(mid*mid*mid>n)r=mid;
        else l=mid;
    }
    printf("%.6lf",l);
    
    return 0;
}

3.板子

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;
}

基础算法（二）

高精度

高精度加法

本质上是模拟人进行列竖式加法的过程，即 $a_{1}$ +…+ $a_{n}$ +t，其中当 $a$ 的退一位加起来不超过10则 $t = 0$ 否则 $t = 1$ ，以此类推

1.思路

（1）先加低位还是高位？

先加低位（个位）。在 main 函数里用 for(int i=a.size()-1;i>=0;i--) 把字符串反向存入了 vector，所以 A[0] 存的是个位，A[1] 存的是十位。

（2）为什么在C.push_back(t%10);用 push_back 而不是 C[i]？

因为 C 刚创建时是空的，根本没有下标 i。 在 C++ 中，vector<int> C; 初始长度为 0。如果写 C[i] = ...，程序会因为访问越界而崩溃。push_back 的作用是“动态扩容”，它会在数组末尾新开辟一个空间并把数放进去。

（3）push_back 和 size() 的适用范围

push_back： 适用于动态序列容器，最常用的是 vector、string 和 deque。

size()： 适用于几乎所有 STL 容器。包括 vector、string、list、map、set 等。

2.题目：791. 高精度加法 - AcWing题库

#include<iostream>
#include<vector>

using namespace std;

vector<int>add(vector<int>&A,vector<int>&B)
{
    vector<int>C;
    int t=0;//存储每一位相加后的数，同时完成是否需要进位的考量
    
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        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);//最后一个t代表最高位，因此等for循环运行完后再用判断看看进位情况，是的话就在vector后面再加一个1
    return C;
}

int main()
{
    string a,b;
    vector<int>A,B;
    cin>>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');
//A、B元素进栈都是逆序进栈，比如a='123456',那A=[6.5,4,3,2,1],目的是方便进位多了1的时候整体数组挪动空间不大，否则要是最高位在前边ta进位后面数组所有数字都要往后挪
    
    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    return 0;
}

高精度减法

1.思路

（1）输入的处理逻辑整体与高精度加法一致，变化的在于①需要判别A和B谁大②需要处理前导0（把有效数字外高位的没用的0全部扔掉）

（2）对于判别大小的函数cmp而言，首先比较二者位数，位数大者自然大；其次位数相同的情况下，从高位依次比较具体位数的数值，数值大者自然大；最后一样大了就返回一个true；cmp返回比较时就是返回的布尔值（成立为1不成立就是0，转过弯就行）

（3）判定循环是i=A.size()-1;i>=0;i--还是i=o;i<A.size();i++取决于是从高位还是从低位算起；因为读入时采取了i=a.size()-1;i>=0;i--，则此时vector中A[0]代表低位A[n-1]代表高位，因此cmp的比较中还是要从高位算起，因此i=A.size()-1;...

（4）由于cmp已经隐含A＞B，因此我们默认A位数更大，外层循环管A.size()而里面再用个B.size()管。

2.题目：792. 高精度减法 - AcWing题库

#include<iostream>
#include<vector>

using namespace std;

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

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;
}

int main()
{
    string a,b;
    vector<int> A,B;
    cin>>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');
    
    vector<int> C;
    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.思路

处理逻辑不难，和加减法差不多

2.题目：793. 高精度乘法 - AcWing题库

#include<iostream>
#include<vector>


using namespace std;

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;
        C.push_back(t%10);
        t/=10;
    }
    
    if(t!=0)C.push_back(t);
    while(C.size()>1&&C.back()==0)C.pop_back();
    
    return C;
}

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

高精度除法

1.思路

整体和乘法比较像，但是有三个注意的点：

（1）题目要求输出余数r，因此在写自定义函数的时候一定要记得加引用符&

（2）输出结果对应的是整除，输出余数对应的是取余；由于除法在处理时（也就是div函数内部）和加减乘都不一样，他还是倒序读数，因此最后得reverse把结果再反过来。这么麻烦的目的是使得题目同时高精度加减乘除时都统一；该做的前序0去除也是得有

（3）对于除法，除的交互对象变为b而不是10

2.题目：794. 高精度除法 - AcWing题库

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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;
}


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