基础算法

发表于 2024-02-21 分类于 Algorithm 本文字数： 3.1k 阅读时长 ≈ 11 分钟

学习基础算法

排序

快排

找一个基准x，然后将小于x的拉到其左侧，大于x的拉到其右侧，然后递归。其核心思想是分治。

#include<iostream>

using namespace std;

const int N = 1e6 +10;
int n;
int q[N];

void quick_sort(int q[],int l,int r)
{
    if(l>=r)return ;
    
    int x = q[(l+r)/2],i=l-1,j=r+1; // -1和+1是细节
    
    while(i<j){
        while(x>q[++i]);// 先加，后比较
        while(x<q[--j]); if(i<j)swap(q[i],q[j]);
    }
    
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    
}

int main(){
    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]);
}

归并排序

核心也是分治，不过和快排不同的是自低向上排序。

代码如下：

#include<iostream>
using namespace std;

const unsigned maxn = 100010;

int temp[maxn];
int arr[maxn];

void gsort(int arr[],int l,int r){
    if( l>=r)return;
    

    int mid = l+r >> 1;
    
    gsort(arr,l,mid);
    gsort(arr,mid+1,r);
    
    int i=l,j=mid+1,k=l;
    while(i <= mid && j <= r){
        if(arr[i]<arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    
    while(i <= mid )temp[k++]=arr[i++];
    while(j <=r )temp[k++] = arr[j++];
    
    // for(int i=0;i >= 0 && i<= r; i++) printf("%d",arr[i]);
    // //printf("\t");
    // // for(int i=0;i >= 0 && i<= r; i++) printf("%d",temp[i]);
    
    
    
    // printf("\tl=%d",l);
    // printf("\n");
    
    i = l;
    while(i <= r){
        arr[i]=temp[i];
        i++;
    }
}



int main(){
    int n;
    scanf("%d",&n);

    for(int i=0; i<n; i++)scanf("%d",&arr[i]);
    
    gsort(arr,0,n-1);
    
    
    for(int i=0; i<n; i++)
        cout<< arr[i] << ' ' ;
    
}

练习

逆序对数量 https://www.acwing.com/solution/content/5508/
两个元素分别在左和右比较难想。

查找算法

二分

重点是找到区分条件。整数二分还要注意边界问题。

#include<iostream>

using namespace std;
const int N = 1e5 + 10;
int arr[N];

int main(){
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0; i<n; i++) scanf("%d",&arr[i]);
    
    while(q--){
        int x;
        scanf("%d",&x);
        
        int l = 0,r = n-1;
        while(l < r){
            int mid = l+r >> 1;
            if(arr[mid] < x)l = mid + 1;
            else r = mid;
        }
        if(arr[l] != x)cout << "-1 -1" << endl;
        else {
            cout << l;
            l = 0, r = n-1;
            while (l < r){
                int mid = l+r+1 >> 1;
                if(arr[mid] > x) r = mid - 1;
                else l = mid;
            }
            cout << ' ' << l << endl; 
        }
    }
    
    
    return 0;
}

# 高精度

加法

用数组表示一个大数：最低位放在数组的0位置，次低位放在数组的1位置，其他位以此类推。这样从低位向高位摆放的原因是，便于进位，否则进位到新位时要移动n次。由于加减乘除通常混合，所以加减乘除的数都采用这种方法进行存储。

每一位数字 $C_{i}$ 和数组A的数字 $A_{i}$ , 数组B的数字 $B_{i}$ 和进位 $r_{i - 1}$ 的关系如下:
$C_{i} = (A_{i} + B_{i} + r_{i - 1})$ $r_{i} = (A_{i} + B_{i} + r_{i - 1}) / 10$

代码如下：

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


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(1);
    return C;
}

int main(){
    vector<int> A,B;
    string 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');
    
    auto C = add(A,B);
    
    for(int i=C.size()-1; i>=0; i--)printf("%d",C[i]);
    
    return 0;
}

## 减法

借位 $r_{i - 1}$ ,结果数组C的数字 $C_{i}$ ,被减数的数字 $A_{i}$ 和减数的数字 $B_{i}$ 的关系如下：
$C_{i} = (A_{i} + r_{i - 1} - B_{i} + 10)$ $r_{i} = {\begin{array}{rcl} 0 & A_{i} + r_{i - 1} - B_{i} >= 0 \\ 1 & A_{i} + r_{i - 1} - B_{i} < 0 \end{array}$ 代码如下：

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

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

// 判断 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;
}

int main(){
    vector<int> A,B;
    string 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');
    
    if(cmp(A,B)){
        auto C = sub(A,B);
        for(int i=C.size() - 1; i>=0; i--) printf("%d",C[i]);
    }else{
        auto C = sub(B,A);
        printf("-");
        for(int i=C.size() - 1; i>=0; i--) printf("%d",C[i]);
    }
    return 0;
}

## 乘法将一个高精度数A乘以另一个较小数b，方法是将高精度数的每一位乘以b，然后进位，类似加法。

代码如下：

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

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

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

除法

将一个高精度数A除以另一个较小数b,方法是将高精度数从最高位开始，取第一位，除以b，得到的商写入结果数组C。将刚刚得到余数乘以10加上第二位，将得到的和除以b…

代码如下：

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

vector<int> div(vector<int> &A, int b,int &r){
    vector<int> C;
    
    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(){
    vector<int> A;
    string a;
    int b;
    cin >> a >> b;
    
    for(int i=a.size()-1; i>=0; i--)A.push_back(a[i]-'0');
    
    int r=0;
    auto C = div(A,b,r);
    
    for(int i=C.size()-1; i>=0; i--)printf("%d",C[i]);
    cout << endl << r << endl;
    
    return 0;
}

# 前缀和差分 ## 前缀和将前数组中前j(j=1,2,…,n)位数字相加，得到前缀和。然后可以算任意区间内的和。

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int sum[N];

int main(){
    int m,n;
    cin >> n >> m;
    
    int num;
    for(int i=0; i<n; i++)
    {
        cin >> num;
        sum[i+1] = sum[i] + num;
    }
    
    int l,r;
    while(m--){
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << endl;
    }
    
}

## 子矩阵的和和前缀和类似，算出每个以第一个节点为顶点的子矩阵的和sum[i,j]。然后算出以指定定点的子矩阵的和。

#include<iostream>

using namespace std;
const int N = 1000 + 10;

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

## 差分

差分是前缀和的逆运算。a为原数组,同时也是前缀和，b为差分数组。先把原数组还原为差分的数组，即令b[i] += a[i] ,b[i+1] -= a[i]。然后再输入q个操作，在l上+m，在r+1减m。

#include<iostream>
using namespace std;

const int N = 100010;

int a [N],b[N];

void insert(int l,int r,int i){
    b[l] += i;
    b[r+1] -= i;
}

int main(){
    int n,m;
    cin >> n >> m;
    
    int x;
    for(int i = 1;i<=n; i++){ cin >> x;insert(i,i,x);}
    
    int l,r,c;
    for(int i=1; i<=m; i++){cin >> l >> r >> c;insert(l,r,c);}
    
    for(int i=1; i<=n; i++){a[i] = a[i-1] + b[i]; cout << a[i] << ' ';}
    
    return 0;
}

差分矩阵

与一维差分类似。差分矩阵，也是用这种方法，根据子矩阵的和、差分也可以得出结论。a为前缀和矩阵，b为差分数组。把原始数组差分到b中，然后在b上进行q个操作，再对b前缀和得到结果a

#include<iostream>
using namespace std;

const int N = 1010;

int m,n,q;
int a[N][N],b[N][N];

void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1] += c;
    b[x1][y2+1] -= c;
    b[x2+1][y1] -= c;
    b[x2+1][y2+1] += c;
}

int main(){
    cin >> n>> m >> q;
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
        }
        
    // 将原有数据当做是后来插入的，面积为1
    for(int i=1; i<=n ; i++)
        for(int j=1; j<= m; j++)
            insert(i,j,i,j,a[i][j]);
    
    int x1,y1,x2,y2,c;
    while(q--){
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1,y1,x2,y2,c);
    }
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m ; j++)
            a[i][j] = b[i][j] -a[i-1][j-1]+a[i-1][j] + a[i][j-1];
            
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m ; j++)
            cout << a[i][j] << ' '; 
		cout << endl;
	}

    
    return 0;
}

# 双指针算法第一种在两个指针分别在两个序列中，第二种两个指针均在一个序列中。

模版

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

核心思想 优化普通算法O(n^2) 为O(n)。

连续最长不重复子序列

先思考暴力解法，然后换成双指针算法。发现j始终小于i,且j不会回退。

朴素做法


for (int i=0; i< n; i++){
	for(int j=0; j<=i; j++){
		if(check(j,i))
			res = max(res,j-i+1);
	}
}

双指针算法

for(int i=0,j=0; i< n; i++){
	while(j<=i && check(j,i)) j++;
	res = max(res,j-i+1);
}

代码：

#include<iostream>

using namespace std;

const int N = 100010;

int a[N],s[N];

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    
    int res=0;
    for(int i=0,j=0; i<n; i++){
        s[a[i]] ++;
        while(s[a[i] > 1){
            s[a[j]] --;
            j++;
        }
        res = max(res,i-j+1);
    }
    
    cout << res << endl;
}

数组元素目标和

类似

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N],b[N];

int main(){
    int i,j;
    int n,m,x;
    cin >> n >> m >> x;
    
    for(i=0; i<n; i++) cin >> a[i];
    for(i=0; i<m; i++) cin >> b[i];
    
    for(i=0,j=m-1; i<n ; i++)
    {
        while(a[i] + b[j] > x )
        {
            j--;
        }
        if(a[i] + b[j] == x) cout << i << ' '<< j-- << endl;
    }
    
    return 0;
}

## 判断子序列思想相同，代码也是很简洁。

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int A[N],B[N];

int main(){
    int n,m,i,j;
    cin >> n >> m;
    for(i = 0; i<n; i++) cin >> A[i];
    for(i = 0; i<m; i++) cin >> B[i];
    
    i = 0,j = 0;
    while(i < n && j <m ){
        if(A[i] == B[j]) i++;
        j++;
    }
    if(i == n) cout << "Yes" << endl;
    else cout << "No" << endl;
}

# 位运算二进制第k位数字：

Misplaced &

二进制返回n的最后一位数字1 ： lowbit(n) = n & (~n + 1)
## 二进制中1的个数

#include<iostream>

using namespace std;

int lowbit(int n){
    return n & (~n+1);
}

int main(){
    int n;
    cin >> n;
    
    // 暴力
    /*
    int x;
    while(n--){
        int y = 0;
        cin >> x;
        while(x){
            y += x % 2;
            x /= 2;
        }
        cout << y << ' ';
    }
    */
    // lowbit
    while(n--){
        int x;
        cin >> x;
        int res=0;
        while(x) x -= lowbit(x),res ++;
        
        cout << res << ' ' ;
    }
    
    return 0;

}

# 离散化

解释：https://zh.wikipedia.org/wiki/%E7%A6%BB%E6%95%A3%E5%8C%96 适用于值域跨度很大，但是用到的值很少。
## 区间和这道题综合性强。用到二分，前缀和，离散化。

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

using namespace std;

const int N = 3e5 + 10;
typedef pair<int,int> PII;

int a[N],b[N];
vector<int> alls;
vector<PII> adds,query;
// 查找离散化后的坐标
int find(int x){
    int l=0,r = alls.size()-1;
    
    while(l < r){
        int mid = l+r >> 1;
        if(x > alls[mid]) l = mid+1;
        else r = mid ;
    }
    
    return r+1;
}
// 
int main(){
    int n,m;
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        int x,v;
        cin >> x >> v;
        alls.push_back(x);
        adds.push_back({x,v});
    }
    
    for(int i=0; i<m; i++){
        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(int i=0; i<n; i++){
        int x = find(adds[i].first);
        a[x] += adds[i].second;
    }

    //前缀和
    for(int i=1; i<=alls.size(); i++){
        b[i] = b[i-1] + a[i];
    }
    
    //数字和
    for(int i=0; i<m; i++){
        int l = find(query[i].first);
        int r = find(query[i].second);
        
        cout << b[r] - b[l-1] << endl;
    }
    
    return 0;
}

# 贪心算法

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。https://zh.wikipedia.org/wiki/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95
## 区间选点两个区间没有交集时需要加两个点，否则只用一个，也可能出现多个区间公用一个点。先通过右端点进行排序（也可以左端点），然后如果l_{i+1} < r_{i} 就不用加点，否则需要加点。
证明：设最终结果为ans,上述的结果为cnt。由于结果为ans，所以 ans <= cnt; 根据cnt的定义，有cnt个互无交集的区间，所以至少有答案至少有cnt个点,所以ans >= cnt; 综上，ans==cnt;

代码如下：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5+10;

struct Range{
    int l,r;
    bool operator < (const Range &r) const{
        return this->r < r.r;
    }
}range[N];

int main(){
    // cout << "aaaaaaaaa" << endl;
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> range[i].l >> range[i].r;
    
    sort(range,range+n);
    
    int min = -1e9 - 10;
    int res=0;
    for(int i=0; i<n; i++){
        if(range[i].l > min){
            res++;
            min = range[i].r;
        }
    }
    
    cout << res << endl;
    return 0;
}