1.快速排序

算法思想：分治

  1. 确定分界点 x = v[l]或v[l+r>>1]等均可
  2. 调整区间：让第一个区间里的数小于等于x， 让第二个区间的数大于等于x
  3. 递归处理左右两边 
    void quickSort(vector<int>& v,int start,int end){
    if(start>=end) return;//排序区间为空或只有一个元素->直接退出
    int x=v[start],i=start-1,j=end+1;
    while(i<j){
        do i++;while(v[i]<x);
        do j--;while(v[j]>x);
        if(i<j) swap(v[i],v[j]);
    }
    quickSort(v,start,j); //递归排两边
    quickSort(v,j+1,end);
}

    需要注意的是，递归排两边时，边界没确定好容易导致死循环，以下是两种常见的递归死循环：

    void quickSort(vector<int>& v,int start,int end){
    if(start>=end) return;
    int x=v[start],i=start-1,j=end+1;
    while(i<j){
        do i++;while(v[i]<x);
        do j--;while(v[j]>x);
        if(i<j) swap(v[i],v[j]);
    }
    quickSort(v,start,i-1);
    quickSort(v,i,end);
}
//0 1
//ij=0
[0,-1];
[0,1];//一直【0，1】死循环递归下去

void quickSort(vector<int>& v,int start,int end){
    if(start>=end) return;
    int x=v[end],i=start-1,j=end+1;
    while(i<j){
        do i++;while(v[i]<x);
        do j--;while(v[j]>x);
        if(i<j) swap(v[i],v[j]);
    }
    quickSort(v,start,j);
    quickSort(v,j+1,end);
}

    快排应用-快速选择排序-第k小

#include<iostream>
#include<vector>
using namespace std;
//快速选择排序->对快排进行改造
int quickSelect(vector<int>&v,int start,int end,int k){
    if(start==end) return v[start];
    int x=v[start],i=start-1,j=end+1;
    while(i<j){
        do i++;while(v[i]<x);
        do j--;while(v[j]>x);
        if(i<j) swap(v[i],v[j]);
    }
    int n=j-start+1;//计算左边区间长度
    if(k<=n) return quickSelect(v,start,j,k); //k<=n左边找
    return quickSelect(v,j+1,end,k-n);//右边找
}

int main(){
    int n,k;cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    cout<<quickSelect(v,0,n-1,k);
    return 0;
}

2.归并排序

算法思想：分治

  1. 确定分界点 mid = r + l >> 1
  2. 递归处理左右两边
  3. 归并，将两个区间合二为一（从递归后的最底层开始合并，每次回溯后达到排序的效果） 
    #include<iostream>
#include<vector>
using namespace std;

void merge(vector<int>&v,int l,int mid,int r){
    int n=r-l+1;
    int i=l,j=mid+1,index=0;
    vector<int> temp(n);//辅助数组
    //以下操作：合并两个有序区间(重要思想)
    while(i<=mid&&j<=r){
        if(v[i]<=v[j]) temp[index++]=v[i++];
        else temp[index++]=v[j++];
    }
    while(i<=mid) temp[index++]=v[i++];
    while(j<=r) temp[index++]=v[j++];
    //将合并后的数据恢复到对应原数组的区间
    i=l;
    for(index=0;index<n;index++) v[i++]=temp[index];
}

void merge_sort( vector<int>&v,int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;
    merge_sort(v,l,mid); //划分两半
    merge_sort(v,mid+1,r);
    merge(v,l,mid,r);
}

int main(){
    int n;cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    merge_sort(v,0,n-1);
    for(int i=0;i<n;i++) cout<<v[i]<< " ";
    return 0;
}

归并排序应用- 求逆序对的数目（LeetCode困难题）

解决：只需在归并排序中加一行代码，即两有序数组合并时对逆序对进行判断和累加。

#include<iostream>
#include<vector>
#define  int long long //10^6个数据，逆序对最多(10^6)*(10^6-1)/2超int。
using namespace std;
int cnt=0;
void merge(vector<int>&v,int l,int mid,int r){
    int n=r-l+1;
    vector<int> temp(n);
    int i=l,j=mid+1,index=0;
    while(i<=mid&&j<=r){
        if(v[i]<=v[j]) temp[index++]=v[i++];
        else {
            cnt+=(mid-i+1);//只需加这行(即v[i]>v[j]时，其v[i+1,...,mid]也都大于v[j],即mid-i+1组逆序对)
            temp[index++]=v[j++];
        }
    }
    while(i<=mid) temp[index++]=v[i++];
    while(j<=r) temp[index++]=v[j++];
    index=l;
    for(int i=0;i<n;i++) v[index++]=temp[i];
}

void mergeSort(vector<int>& v,int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;
    mergeSort(v,l,mid);
    mergeSort(v,mid+1,r);
    merge(v,l,mid,r);
}

signed main(){
    int n;cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    mergeSort(v,0,n-1);
    cout<<cnt;
    return 0;
}

3.整数二分

两个模板，能解决一切整数二分问题。注意观察mid=l+r>>1和l+r+1>>1,不注意会出现边界问题。使用这两个目标的好处是一定能找到一个解(算法的解，不一定是问题的解)，能够很好地求边界。

整数二分典型应用-数的范围

刚好就把两个模板给用上了。 

数的范围

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n,q;cin>>n>>q;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    while(q--){
        int k;cin>>k;
        int l=0,r=n-1;
        int mid;
        while(l<r){
            mid=l+r>>1;
            if(v[mid]>=k) r=mid;//找左边界(找第一个>=k的位置)
            else l=mid+1;
        }
        if(v[l]!=k) cout<<"-1 -1"<<endl;
        else{
            cout<<l<<" ";
            l=0,r=n-1;
            while(l<r){
                mid=l+r+1>>1;
                if(v[mid]<=k) l=mid;//找右边界(找最后一个<=k的位置)
                else r=mid-1;
            }
            cout<<r<<endl;
        }
    }
    
    return 0;
}

4.浮点二分 

算法思想：

算法原理与整数二分相似，在区间划分的时候没有整数二分的各种边界情况，一般用左右端点的差值是否小于某个值(精度)来判定是否需要继续循环。

数的三次方根

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main(){
    double x;cin>>x;
    double l=-22,r=22,mid;
    while(r-l>1e-8){
        mid=(l+r)/2;
        if(mid*mid*mid>=x) r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(6)<<l;
    return 0;
}

5.高精度算法

模拟人工计算过程，这里不过多介绍，感兴趣的可自行研究。

高精度加法

#include<iostream>
#include<vector>
using namespace std;

//C=A+B
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);
    return C;
}

int main(){
    string a,b;
    vector<int> A,B;
    cin>>a>>b; //a=123456;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//A=[6,5,4,3,2,1]
    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--) printf("%d",C[i]);
    
    return 0;
}

高精度减法

#include<iostream>
#include<vector>
using namespace std;

bool cmp(vector<int>& A,vector<int>& B){ //A>=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;
}

//C=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;
        if(i<B.size()) t-=B[i];
        C.push_back((t+10)%10);
        if(t<0) t=1;//说明有借位
        else t=0; //无借位
    }
    //去除前导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; //a=123456;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//A=[6,5,4,3,2,1]
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    
    if(cmp(A,B)){
        vector<int> C=sub(A,B);
        for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }
    else{
        vector<int> C=sub(B,A);
        printf("-");
        for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }
    
    return 0;
}

高精度乘法

#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=t/10;
    }
    if(t) C.push_back(t);
    while(C.size()>1&&C.back()==0) C.pop_back(); //去前导0
    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--) cout<<C[i];
    return 0;
}

高精度除法

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

6.前缀和

一维前缀和

算法思想：

在输入时，顺便记录前i项的和，i从1 ~ n，记为:s[i] ，当需要求第i个数到第j 个数的和时，直接使用s[j] - s[i - 1]，时间复杂度为O(1)，相比于重新遍历一更快。用于求解区间和更为方便和快速。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    vector<int> v(n+1);
    for(int i=1;i<=n;i++) {
        cin>>v[i];
        v[i]+=v[i-1];
    }
    while(m--){
        int l,r;cin>>l>>r;
        cout<<v[r]-v[l-1]<<endl;
    }
    return 0;
}

二维前缀和

算法思想：

二维前缀和思想类似于一维前缀和，用s[i][j]表示以(i,j)为右下角，(0,0)为左上角的子矩阵中所有数之和。可用于求解以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为。（该算法有容斥原理的思想）

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n,m,q;cin>>n>>m>>q;
    vector<vector<int>> s(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    while(q--){
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
    }
    return 0;
}

7.差分

一维差分

一维差分

算法思想：
实际上，差分与前缀和互为逆运算，例如，如果s[i]为a[i]的前缀和，那么a[i]则称为s[i]的差分数组，即a[i] = s[i] - s[i - 1]，差分数组的作用在于，如果需要对一个数组中的l ~ r区间的k个数字均加上c，则时间复杂度与k相关，而对其差分数组进行操作，则只需在其差分数组的第l项加c，再对第r + 1项减去c，时间复杂度降为O(1)。并且，差分数组的求解过程正好与对差分数组的"+ c"、"- c"操作相似，具体操作见代码实现。

#include<iostream>
#include<vector>
using namespace std;

void insert(vector<int> &v,int l,int r,int c){
    v[l]+=c;
    if(r+1<v.size()) v[r+1]-=c;
}

int main(){
    int n,m;cin>>n>>m;
    vector<int> v1(n+1);//原数组（即差分数组的前缀和数组）
    vector<int> v2(n+1);//差分数组
    for(int i=1;i<=n;i++) cin>>v1[i];
    //构造差分数组(很巧妙)：
    for(int i=1;i<=n;i++) insert(v2,i,i,v1[i]);
    while(m--){
        int l,r,c;cin>>l>>r>>c;
        insert(v2,l,r,c);
    }
    //恢复原来数组（求前缀和）
    for(int i=1;i<=n;i++){
        v2[i]+=v2[i-1];
        cout<<v2[i]<<" ";
    }
    return 0;
}

二维差分

算法思想：
类似于一维差分，二维差分与二维前缀和互为逆运算，例如，s[i][j]是b[i][j]的前缀和，那么b[i][j]就称为s[i][j]差分数组。二维差分数组的作用在于，如果需要对二维矩阵中以(x1, y1)为左上角，(x2, y2)为右下角的区域内每个数加上c，那么可以对差分矩阵中b[x1][y1]加上c，对b[x2 + 1][y1]与b[x1][y2 + 1]减去c，再对b[x2 + 1][y2 + 1]减去c。因为对b[x1][y1]，将会导致求前缀和后，s[x1][y1]到右下角这部分区域每个数都加上c，因此，根据容斥原理，需对其他部分进行如上处理。同时，与一维差分类似，二维差分也不用去想如何构造差分数组，也可以利用插入操作完成。

差分矩阵

#include<iostream>
#include<vector>
using namespace std;

void insert(vector<vector<int>>&v,int x1,int y1,int x2,int y2,int c){
    v[x1][y1]+=c;
    if(x2+1<v.size()) v[x2+1][y1]-=c;
    if(y2+1<v[0].size()) v[x1][y2+1]-=c;
    if(x2+1<v.size()&&y2+1<v[0].size())v[x2+1][y2+1]+=c;
}

int main(){
    int n,m,q;cin>>n>>m>>q;
    vector<vector<int>> v1(n+1,vector<int>(m+1));
    vector<vector<int>> v2(n+1,vector<int>(m+1));//差分数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>v1[i][j];
        }
    }
    //构造差分数组；
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            insert(v2,i,j,i,j,v1[i][j]);
        }
    }

    while(q--){
        int x1,y1,x2,y2,c;cin>>x1>>y1>>x2>>y2>>c;
        insert(v2,x1,y1,x2,y2,c);
    }
    //求差分数组前缀和：
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v2[i][j]+=v2[i-1][j]+v2[i][j-1]-v2[i-1][j-1];
            cout<<v2[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

8.双指针算法

算法思想： 双指针算法是优化枚举最常用的算法，其核心思想在于通过找到单调性，将O(n²)的暴力枚举转变成O(n)的双指针算法。该算法有两类，第一类为类似于归并排序中，在两个区间上归并的操作。第二类则在一个区间上动态维护一个小区间。

算法应用-最长连续不重复子序列

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

const int N=1e5+10;
int a[N],b[N];

int main(){
    int n;cin>>n;
    int res=0;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0,j=0;i<n;i++){
        b[a[i]]++;//记录j-i范围内重复元素的个数
        while(b[a[i]]>1){//只要出现重复，将j指针往后移直到区间内无重复
            b[a[j]]--;
            j++;
        }
        res=max(res,i-j+1);//记录区间最长值
    }
    cout<<res;
    return 0;
}

算法应用-数组元素的目标和

#include<iostream>
#include<vector>
using namespace std;
//暴力枚举，两重循环，部分超时
// int main(){
//     int n,m,x;cin>>n>>m>>x;
//     vector<int>a(n),b(m);
//     for(int i=0;i<n;i++) cin>>a[i];
//     for(int i=0;i<m;i++) cin>>b[i];
//     for(int i=0;i<n;i++){
//         for(int j=0;j<n;j++){
//             if(a[i]+b[j]==x){
//                 cout<<i<<" "<<j;
//                 return 0;
//             }
//         }
//     }

//     return 0;
// }
//双指针优化，i+j的步长最多为n+m；
//1 2 4 7
//3 4 6 8 9
//i从前往后走，j从后往前走。
//只要a[i]+b[j]>x，说明i往后的+b[j]>x.这种情况只能前移j。
//若移动后，a[i]+b[j]<x，则这种情况只能后移i，因为后移j不可能=。
int main(){
    int n,m,x;cin>>n>>m>>x;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    for(int i=0,j=m-1;i<n;i++){
        while(a[i]+b[j]>x) j--;
        if(a[i]+b[j]==x){
            cout<<i<<" "<<j;
            return 0;
        }
    }
}

9.位运算

十进制数对应二进制的第k位（k从0开始）

lowbit- 返回x的最后一位1

应用-二进制中1的个数 

#include<iostream>
using namespace std;

int lowbit(int x){
    return x&-x;
}

int main(){
    int n;cin>>n;
    while(n--){
        int x;cin>>x;
        //基本思想：每次减去二进制最后一位1，看减了几次
        int cnt=0;
        while(x){
            x-=lowbit(x);
            cnt++;
        }
        cout<<cnt<<" ";
    }
    return 0;
}

10.离散化

离散化模板

vector<int> v;//存储所有待离散化的值
sort(v.begin(),v.end());//将所有值排序
v.erase(unique(v.begin(),v.end()),v.end());//去除重复元素
//二分求出x对应的离散化的值
int find(x){//找到第一个大于等于x的位置
    int l=0,r=v.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(v[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1; //映射到1，2,...,n
}

应用-区间和

常规做法：平移区间(空间太大，提交运行失败->内存分配失败)

#include<iostream>
#include<vector>
using namespace std;

const int N=2e9+10;
vector<int> v(N);
const int M=1e9;
//映射到[0,2e9]。本地行，提交空间分配失败
int main(){
    int n,m;cin>>n>>m;
    while(n--){
        int x,c;cin>>x>>c;
        v[x+M]+=c;
    }
    while(m--){
        int l,r;cin>>l>>r;
        long long sum=0;
        for(int i=l;i<=r;i++){
            sum+=v[i+M];
        }
        cout<<sum<<endl;
    }
    return 0;
}

离散化做法：观察可发现[-1e9,1e9]区间中实际上用到的坐标数目仅仅最多只有3e5，因此可以将用到的坐标值进行离散化处理，大大减少空间的利用。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//分析,2e9个坐标最多用到3e5个
const int N=3e5+10;
int n,m;
int a[N],s[N];

vector<int> alls;//待离散化
vector<pair<int,int>> add,query;

int find(int 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;
}

int main(){
    cin>>n>>m;
    while(n--){
        int x,c;cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    while(m--){
        int l,r;cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    //处理插入
    for(auto item:add){
        int x=find(item.first);
        a[x]+=item.second;
    }
    //预处理前缀和
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
    //处理询问
    for(auto item:query){
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}

11.区间合并

算法思想：
区间合并是将数轴上所有有交集的区间进行合并，得到没有交集的区间。例如将区间[0, 2], [3, 7], [4, 5], [7, 10], [13, 15]合并后的区间为[0, 2], [3, 10], [13, 15]。其思想类似于贪心，先将所有区间按照左端点进行排序，每次维护一个区间，如果枚举的区间与当前区间无交集，则将维护的区间放入答案中去，再将维护的区间更新为枚举的区间，否则将维护的区间的右端点更新为维护区间与枚举区间右端点的最大值。

区间合并

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<pair<int,int>> segs;

void merg(vector<pair<int,int>>& segs){
    sort(segs.begin(),segs.end());
    vector<pair<int,int>> res;
    int st=-2e9,ed=-2e9;
    for(auto seg:segs){
        if(seg.first>ed){
            if(st!=-2e9) res.push_back({st,ed});
            st=seg.first;
            ed=seg.second;
        }else{
            ed=max(ed,seg.second);
        }
    }
    // 最后那个区间还没有加入, 也保证了segs里面什么都没有情况下的正确性
    if(st!=2e9) res.push_back({st,ed});
    segs=res;
}

int main(){
    int n;cin>>n;
    while(n--){
        int l,r;cin>>l>>r;
        segs.push_back({l,r});
    }
    merg(segs);
    cout<<segs.size();
    return 0;
}

# 算法
Logo
乐奇 Rokid 开放社区

更多推荐

cover

AR 智能眼镜并不是简单地在眼前放一块屏幕，而是把**摄像头、传感器、计算机视觉、空间定位、语音交互和云端服务**连接起来

avatar 乐奇 Rokid 开放社区
cover

让界面替我“摇“一次：一个AR祈愿智能体的AIUI实践

avatar 乐奇 Rokid 开放社区

智能眼镜市场全景解析：从技术演进到产业格局

本文系统梳理智能眼镜市场，涵盖产品形态、技术演进、市场规模、产业链结构及竞争格局。指出智能眼镜正从音频交互向AR显示与空间计算演进，受AI大模型、供应链成熟与生态延伸驱动，呈现分层发展态势。虽面临场景刚需不足、续航重量矛盾与隐私挑战，但B端应用先行、AI原生设计与标准完善将推动行业迈向规模化渗透，未来需关注核心技术突破与真实使用数据。

avatar 乐奇 Rokid 开放社区