acwing算法基础课学习笔记（第一章：基础算法）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

第一章基础算法

前言

所有的模板题都可以在acwing题库中搜到。

一、快速排序

** 思路基于分治思想**

  1. 确定分界点随机取任意一个数为分界点一般取中点
  2. 调整区间把小于x的数移到左边把大于x的数移到右边把区间分为[l, j]、[j + 1, r]
  3. 递归左右。

1. 快速排序算法模板

void quick_sort(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)
    {
        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);
}

2. 快速排序模板题1快速排序

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int q[N];

void quick_sort(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)
    {
        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;
    cin >> n;

    for(int i = 0; i < n; i ++) cin >> q[i];

    quick_sort(q, 0, n - 1);

    for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

3.快速排序算法模板题2第k个数

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int q[N];

int quick_sort(int q[], int l, int r, int k)
{
    if(l >= r) return q[l];

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

    if(j - l + 1 >= k) return quick_sort(q, l, j , k);
    else return quick_sort(q, j + 1, r, k - (j - l + 1));
}

int main()
{
    int n, k;
    cin >> n >> k;

    for(int i = 0; i < n; i ++ ) cin >> q[i];

    cout << quick_sort(q, 0, n - 1, k) << endl;

    return 0;
}

二、归并排序

思路

  1. 取数组的中间数作为分界点
  2. 将分界点左右两边分别排好序
  3. 将左右两边进行合并。

1. 归并排序算法模板

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

2. 归并排序模板题1归并排序

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int q[N], tmp[N];

void memset_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;
    memset_sort(q, l, mid), memset_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(int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i ++ ) cin >> q[i];

    memset_sort(q, 0, n - 1);

    for(int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

3. 归并排序模板题2逆序对的数量

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int q[N], tmp[N];

LL memset_sort(int q[], int l, int r)
{
    if(l >= r) return 0;

    int mid = l + r >> 1;
    LL res = memset_sort(q, l, mid) + memset_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
        {
            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;
    cin >> n;

    for(int i = 0; i < n; i ++) cin >> q[i];

    cout << memset_sort(q, 0, n - 1) << endl;

    return 0;
}

三、二分

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

1. 整数二分算法模板

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

2. 整数二分算法模板题数的范围

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> q[i];

    while(m -- )
    {
        int x;
        cin >> 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;
}

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

4. 浮点数二分算法模板题 数的三次方根

#include <bits/stdc++.h>

using namespace std;

int main()
{
    double x;
    cin >> x;

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

四、高精度

1. 高精度加法模板

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

2. 高精度减法模板

// C = A - B, 满足A >= B, A >= 0, B >= 0
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;
}

3. 高精度乘低精度模板

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 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();

    return C;
}

4. 高精度除以低精度算法

// A / b = C ... r, A >= 0, b > 0
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;
}

五、前缀和与差分

1. 一维前缀和模板

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

一维前缀和模板题前缀和

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];

    while(m -- )
    {
        int l, r;
        cin >> l >> r;
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

2. 二维前缀和模板

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角(x2, y2)为右下角的子矩阵的和为
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

二维前缀和模板题子矩阵的和

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

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

int main()
{
    cin >> n >> m >> q;

    for(int i = 1; i <= n; i ++ )
        for(int j  = 1; j <= m; j ++ )
            cin >> 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];

    while(q -- )
    {
       int x1, y1, x2, y2;
       cin >> x1 >> y1 >> x2 >> y2;
       printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 -1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}

3. 一维差分模板

给区间[l, r]中的每个数加上cB[l] += c, B[r + 1] -= c

一维差分模板题差分

#include <bits/stdc++.h>

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()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    for(int i = 1; i <= n; i ++ ) insert(i, i, a[i]);

    while(m -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    for(int i = 1; i <= n; i ++ ) b[i] += b[i - 1];


    for(int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;
}

4. 二维差分模板

给以(x1, y1)为左上角(x2, y2)为右下角的子矩阵中的所有元素加上c
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

二维差分模板题差分矩阵

#include <bits/stdc++.h>

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()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            cin >> a[i][j];

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);

    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]);
        puts("");
    }
    return 0;
}

六、双指针

常见问题分类

  1. 对于一个序列用两个指针维护一段区间
  2. 对于两个序列维护某种次序比如归并排序中合并两个有序序列的操作

1. 双指针算法模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

2. 双指针算法模板题1最长连续不重复子序列

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

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

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ ) cin >> q[i];

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

3. 双指针算法模板题2数组元素的目标和

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

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

int main()
{
    cin >> n >> m >> x;
    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(j >= 0 && a[i] + b[j] > x) j --;
        if(j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }
    return 0;
}

4. 双指针算法模板题3判断子序列

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

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

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    for(int i = 0; i < m; i ++ ) cin >> 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. 位运算算法模板

求n的第k位数字: n >> k & 1
返回n的最后一位1lowbit(n) = n & -n如101000得1000

2. 位运算模板题二进制中1的个数

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    while(n -- )
    {
        int x, s = 0;
        cin >> x;

        for(int i = x; i; i -= i & -i) s ++;
        printf("%d ", s);
    }
    return 0;
}

八、离散化

**场景**目标数据稀疏的分散在大数组空间中大部分元素为0。
思路

  1. 首先取操作涉及的下标即将要存数字的下标与求和范围两端的下标存入小数组q中;
  2. 对数组q排序;
  3. 重新创建一个大小与q相同的数组s从数组q中找到对应大数组要存入数据的位置映射在s相同位置存入数据q中找映射可以用二分法;
  4. 找大数组求和范围两端点在q中的映射位置在数组s对应映射位置求和即可可用前缀和.

1. 离散化算法模板

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
}

2. 离散化算法模板题区间和

#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()
{
   cin >> n >> m;
   for (int i = 0; i < n; i ++ )
   {
       int x, c;
       cin >> x >> c;
       add.push_back({x, c});

       alls.push_back(x);
   }

   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 (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. 按区间的左端点排序
  2. 从左到右扫描维护一个当前区间随着遍历若相交则区间变长
  3. 每次遍历的区间和当前区间有三种情况分类讨论
    1右端点小于当前区间右端点当前区间不变
    2右端点大于当前区间右端点当前区间变长
    3左端点大于当前区间右端点将该区间置为当前区间

1. 区间合并模板

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

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

2. 区间合并模板题区间合并

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

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    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()
{
    int n;
    scanf("%d", &n);

    vector<PII> segs;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}

内容持续更新中,关注博主不迷路。

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：主成分分析（最小二乘法回归，主成分回归模型）代码分享

下一篇：火爆的超级人工智能ChatGPT，唯独鄙视中国人

“acwing算法基础课学习笔记（第一章：基础算法）” 的相关文章

HTML1年前 (2023-02-02)
使用vscode调试PHP底层C源码1年前 (2023-02-02)
一看就会！超详细【ChatGPT】注册与使用教程1年前 (2023-02-02)
【Docker系列】容器环境配置_容器环境1年前 (2023-02-02)
适配器模式1年前 (2023-02-02)
OpenAI ChatGPT微信接入教程1年前 (2023-02-02)
微机原理与系统设计笔记2 | 8086CPU结构与功能1年前 (2023-02-02)
BurpSuite安装和基础使用教程(已破解)1年前 (2023-02-02)
基于JAVA的企业信息员工管理系统的设计与实现（附：源码 论文 sql文件）1年前 (2023-02-02)
Azure Terraform（十二）利用 Terraform 将文件上传到 Azure Blob Storage1年前 (2023-02-02)

阿里云国际版