基础算法模板总结

admin • • C/C++

文章目录

前言

  • ?欢迎大家来到OpenAll_Zzz的博客，在这里我们一起努力，共同进步！
  • ?这一期分享的内容有点庞大——算法，主要分享目前十分稳定的算法模板，主要帮助笔者复习使用。
  • ?如果大家对某个算法模板有疑惑，欢迎在评论区发表你的问题。
  • ?本文内容为OpenAll_Zzz原创，转载的小伙伴还请标注一下来源。
  • ?本文章于2021年12月4日开篇，最近一次更新为2021年12月12日。
  • ?欢迎大家评论?、转发?、关注?，如果文章对你有帮助的话，希望能得到你的一个大大的赞?。

第一章 基础算法

1.1 快速排序

快排是众多排序中整体性能最优的排序。

C++模板

#include <iostream>

using namespace std;

const int N = 10e6 + 10; // 对一百万的数据量进行测试，Accepted。

int n;
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()
{
    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.1.1 相关练习 第k个数

#include <iostream>

using namespace std;

const int N = 100010;

int n, k;
int q[N];

int quick_select(int l, int r, int k) // 快选算法借助了快排的思想
{
    if(l == r) return q[l];
    
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    
    while(i < j)
    {
        while(q[ ++ i] < x);
        while(q[ -- j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    
    int sl = j - l + 1;
    if(k <= sl) return quick_select(l, j, k);
    
    return quick_select(j + 1, r, k - sl);
}

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

1.2 归并排序

C++模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10e6 + 10;

int n;
int q[N], tmp[N];

void meger_sort(int* q, int l, int r)
{
    if(l >= r) return;
    
    int mid = l + r >> 1;
    meger_sort(q, l, mid), meger_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];
}
int main()
{
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    meger_sort(q, 0, n - 1);
    
    for(int i = 0; i < n; i++) printf("%d ", q[i]);
    
    return 0;
    
}

1.2.1 相关练习：逆序对的数量

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long LL;
using namespace std;

const int N = 100010;

int n;
int q[N], tmp[N];

LL meger_sort(int l, int r)
{
   if(l == r) return 0;
   
   int mid = l + r >> 1; // + 号优先级高于 >> 
   LL res = meger_sort(l, mid) + meger_sort(mid + 1, r);
   
   // 归并的过程  （[l , mid] 和 [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 ++];
           // 在归并的过程中前半部分的某个数x大于后半部分的某个数y,则x后面所有的数均大于y,则有关y的逆序对为
           // mid - i + 1   (mid为前半部分的右端点)
           res += mid - i + 1; 
       }
   }
   // 扫尾
   while(i <= mid) tmp[k ++] = q[i ++];
   while(j <= r) tmp[k ++] = q[j ++];
   // tmp数组返还到原数组q，使其在区间[l, r]有序
   for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
   
   return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    
    cout << meger_sort(0, n - 1) << endl;
    return 0;
}

1.3 二分

1.3.1 整数二分

C++模板

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; // l为mid时需要将mid设置为l + r + 1 / 2,否则会死循环（在l=r-1时）
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

1.3.1.1 相关练习：数的范围

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10e6 + 10;

int n, T, x;
int q[N];

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

1.3.2 浮点数二分

C++模板

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

1.3.2.1 相关练习：数的三次方根

C++代码

#include <iostream>

using namespace std;

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

1.4 高精度模拟

1.4.1 高精度加法

C++模板

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int>& A, vector<int>& B)
{
    vector<int> C;

    int t = 0; // 定义进位变量，初始时为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(t);

    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 --) cout << C[i];
    return 0;
}

// 1. 高精度加法讲究的是将大数转化为数组表示
// 2. 利用数组的每一位为数的位数进行模拟手动加法
// 3. 考虑每一位的进位以及最后的边界情况，边界情况即最后一位可能需要进位

1.4.2 高精度减法

C++模板

#include <iostream>
#include <vector>

using namespace std;

// 判断是否有 A >= B 
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) // A >= 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(); // 消除前导0
    return C;
}

int main()
{
    string a, b;
    cin >> a >> b;

    vector<int> 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-- )  cout << C[i];

    return 0;
}

1.4.3 高精度乘法

C++模板

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b) // A * b A为大数，b比较小
{
    vector<int> C;

    for(int i = 0, t = 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(); // 除去前导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;
}

1.4.4 高精度除法

C++模板

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

using namespace std;

vector<int> div(vector<int>& A, int b, int& r) // A / b : C是商，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()); // 保持形式一致，同时便于除去前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back(); // 除去前导0
    
    return C;
}

int main()
{
    string a;
    int b;
    
    vector<int> A;
    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 --) cout << C[i];
    cout << endl << r;
    
    return 0;
}

1.5 前缀和与差分

前缀和与差分 ，是一组互逆的关系
例如数组a = {1, 3, 4, 6, 8}，其前缀和数组为s = {1, 4, 8, 14, 22}
此时有a的前缀和数组为s，s的差分数组(第二项起，每一项减去前一项的值)是a

1.5.1 相关练习：前缀和（一维前缀和）

C++代码

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int s[N]; // 直接在原数组上进行修改即可，减少数组a的内存开销

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%d", &s[i]);
     
    for(int i = 1; i <= n; i ++) s[i] += s[i - 1];  // 计算前缀和  原始--s[i] = s[i - 1] + a[i]
     
    while(m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        
        printf("%dn", s[r] - s[l - 1]);
    }
    
    return 0;
}

1.5.2 相关练习：子矩阵的和（二维前缀和）

C++代码

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int s[N][N];

int main()
{
    scanf("%d%d%d", &n,&m,&q);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d",&s[i][j]);
            
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) // 原始--s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[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;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        
        printf("%dn", s[x2][y2] - s[x2][y1 - 1] - s[x1 -1][y2] + s[x1 -1][y1 - 1]); // 计算部分和
    }
    return 0;
}

1.5.3 相关练习：差分（一维差分）

差分的核心就是：插入原数组来构造差分数组
对差分数组进行增加变换即可对应到原数组上

C++代码

#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

void insert(int l, int r, int c) // 在一维差分数组中插入
{
    b[l] += c;
    b[r + 1] -= c;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i ++) insert(i, i, a[i]);
    
    int l, r, c;
    while(m --){
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    
    for(int i = 1; i <= n; i ++){
        b[i] += b[i - 1]; // 计算前缀和，a数组其实可以不用
    }
    
    for(int i = 1; i <= n; i ++) cout << b[i] << ' ';
    return 0;
}

1.5.4 相关练习：差分矩阵（二维差分）

C++代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1010;

int n, m, 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[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    
    // for(int i = 1; i <= n; i ++)
    //     for(int j = 1; j <= m; j ++)
    //         scanf("%d", &b[i][j]); // 其实不用a数组，原地操作差分数组b即可
          
    int x = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            cin >> x;
            insert(i, j, i, j, x); // 在差分数组b中进行插入操作
        }
            
            
    while(q --)
    {
        int x1, y1, x2, y2, c;
        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 ++)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; // 计算自身的前缀和就是成为原数组
            
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++) printf("%d ", b[i][j]); // 此时b数组就是原数组
        puts("");// puts函数自动换行
    }
    return 0;
}

1.6 双指针

双指针是一种优化思想，通过降低问题的维数来优化时间复杂度。
通常借助问题的单调性、唯一性、可证性来优化成双指针算法

1.6.1 相关练习 最长连续不重复子序列

C++代码

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    scanf("%d", &n);
    
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    
    // 如果是加进来的数a[i]导致重复，我们只能
    // 通过减少区间中数的个数来去除这个重复的数a[i]
    // 即j ++，同时减少计数数组中a[j]的个数
    int res = 0;
    for(int i = 0, j = 0; i < n; i ++)
    {
        s[a[i]] ++; // 只会是加进来的a[i]导致重复
        while(s[a[i]] > 1)
        {
            s[a[j]] --; 
            j ++; // 当i == j 时，区间中只有一个数，循环结束，不会出现越界
        }
        
        res = max(res, i - j + 1);
    }
    
    cout << res << endl;
    
    return 0;
}

1.6.2 相关练习 数组元素的目标和

C++代码

#include <iostream>

using namespace std;

const int N = 100010;
int n, m, x;
int A[N], B[N];

int main()
{
    scanf("%d%d%d", &n, &m, &x);
    
    for(int i = 0; i < n; i ++) scanf("%d", &A[i]);
    for(int i = 0; i < m; i ++) scanf("%d", &B[i]);
    
    for(int i = 0, j = m - 1; i < n; i ++) // 第二个指针指向数组的最后，保持单调性
    {
        while(j >= 0 && A[i] + B[j] > x) j --;
        if(A[i] + B[j] == x)
        {
            printf("%d %dn", i, j);
            break;
        }
    }
    
    return 0;
}

1.6.3 相关练习 判断子序列

C++代码

#include <iostream>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i ++) scanf("%d", &b[i]);
    
    int i = 0, j = 0;
    while(i < n && j < m) // 可证性，双指针所找出的数匹配时，不会影响到后序的数是否被匹配到
    {
        if(a[i] == b[j])  i ++;
        j ++;
    }
    
    if(i == n) puts("Yes");
    else puts("No");
    
    return 0;
}

1.7 位运算

位运算内容比较单一，核心操作只有两个。
?1. 获取一个二进制位中第k位是多少：x>> k & 1
?2. 返回二进制中最后一个以1开头的二进制位（lowbit函数）：x & -x。
Ps: -x == ~x + 1(一个数的负数等于其按位取反后加一)
在?2中，x取反加上1后，x中最后一个1的左边的二进制位与原来相反，x中最后一个1右边的二进制位全为0，与（&）运算后，即可得到结果。

1.7.1 相关练习 二进制中1的个数

C++代码

#include <iostream>

using namespace std;

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

int main()
{
    int n;
    cin >> n;
    
    while(n --)
    {
        int x;
        scanf("%d", &x);
        
        int res = 0;
        while(x) res ++, x -= lowbit(x);
        
        cout << res << ' ';
    }
    
    return 0;
}

1.8 离散化

?离散化指的：操作一组在数轴上数据范围特别特别大的数据，但是操作它们的个数与它们的范围比起来小很多很多。
?即我们需要操作的这组数据数量很大（当然和它们的数据范围比起来要小很多），我们需要用数组来存储它们，这个时
?候我们需要来想办法存储这一组数据，这个办法的思想就是离散化。（类似哈希映射的思想）

1.8.1 相关练习 区间和

C++代码

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

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N]; // 离散化后的数组、及其前缀和

vector<int> alls; // 在数轴上所有需要离散化的点
vector<PII> 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()
{
    scanf("%d%d", &n, &m);
    
    // 读入需要增加的点和增加的值
    for(int i = 0; i < n; i ++)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        alls.push_back(x);
        add.push_back({x, c});
    }
    
    // 读入查询的区间
    for(int i = 0; i < m; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        alls.push_back(l);
        alls.push_back(r);
        query.push_back({l, 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;
}

1.9 区间合并

区间合并算是一个特殊的算法思想，总体上是模拟的同时来维护一个区间

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

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs; // 区间段 segment

// C++排序pair时先排序第一个后排序第二个，可以不用写cmp
// int cmp(PII a, PII b)
// {
//     return a.first < b.first;
// }

void meger(vector<PII> &segs)
{
    vector<PII> res;
    
    int st = -2e9, ed = -2e9; // 定义边界来比较
    for(auto seg : segs)
    {
        if(ed < seg.first)
        {
            if(st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else 
        {
            ed = max(ed, seg.second);
        }
    }
    if(st != -2e9) res.push_back({st, ed}); //精髓所在
    
    segs = res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }
    
    sort(segs.begin(), segs.end()); 
    meger(segs);
    
    cout << segs.size() << endl;
    return 0;
}

第二章 数据结构

第三章 搜索与图论

第四章 数学知识

第五章 动态规划

第六章 贪心

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>