算法基础（一）

排序

1、快速排序——基于分治

  • 确定分界点x：q[l], q[(l + r) / 2], q[r], 随机

  • 调整区间：划分为两个区间，使得第一个区间内的值都小于等于x；第二个区间内的值都大于等于x（重点在这一部分）

  • 递归：递归处理左右两段，这样左右两边排好序了，整个就排好了

第二步几种实现方法：

  • 比较简单的一种是开两个数组a、b；将小于等于x的加到a，将大于等于x的加到b，然后再将两个数组合并；但是需要消耗额外的空间，时间复杂度为O(n)；
  • 另一种比较优美的做法是用两个指针i、j，两个指针分别从两边开始移动；当i遇到小于x的值时，i继续移动，当遇到大于等于x的值时，i停止移动，开始移动j；当遇到大于x的值时，j继续移动，当遇到小于等于x的值时，j停止移动；此时，交换两个指针所指的值；然后，i和j继续向中间移动，直到i和j相遇为止

快速排序算法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
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); //这里需要注意边界问题，当用j和j+1时，x = q[l]不能用x = q[r];否则会有死循环
}

快排的平均时间复杂度为O(nlogn)

2、归并排序——基与分治

  • 找分界点mid = [l + r] / 2

  • 递归排序左边和右边

  • 进行归并操作——将两个有序的序列合二为一(重点)(双指针算法)

归并排序的算法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
}

二分

二分的本质并不是单调性，有单调性可以二分，但是没有单调性也可能可以二分

假如存在某种性质可以将区间一分为二，则可以用二分来寻找这种性质的边界点

整数二分

微信图片_20250213133716(1)

算法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)    // 这里也可以用for循环直接循环100次
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度

首先要知道大整数在C++中是如何存储的，一般是将其存到一个数组当中，从大整数的个位存到数组的0号位中开始，依次存到数组当中（为了方便进位）

1、高精度加法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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、高精度减法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> A, vector<int> B)
{
    vector <int> C;
    int t = 0;
    
    for(int i = 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、高精度乘法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 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、高精度除法模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 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、一维前缀和

S0 = 0

算法模版

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

2、二维前缀和

微信图片_20250213193822(1)

算法模版

1
2
3
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]

3、一维差分

差分是前缀和的逆操作

微信图片_20250213193831(1)

算法模版

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

4、二维差分

微信图片_20250213193840(1)

算法模版

1
2
给以(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

双指针算法

位运算

  • 求n的二进制表示的第k位数字：n >> k & 1

  • lowbit(树状数组的基本操作)，lowbit(x)，返回一个二进制数，最高位的1为x的最后一位1。

    1
    2
    3
    4
    5
    6
    x = 1010;lowbit(x) = 10;
    x = 101000;lowbit(x) = 1000
    int lowbit(x)
    {
        return x & -x;
    }

    lowbit的实现原理为x & -x = x & (~x + 1)

    有lowbit(x) = x & -x = x & (~x + 1)

离散化

离散化是一种数据处理技巧，常用于处理数据范围较大但数据量相对较少的情况。通过离散化，可以将原本分散的、取值范围很大的数据映射到一个连续的、较小的整数区间，从而减少存储空间的使用，同时也能提高算法的效率。

适用场景

当需要处理的数据范围非常大（例如，数据的取值范围是 [1, 10^9] ），但实际用到的数据量却比较小（例如，只有 10^3 个不同的数据）时，如果直接使用数组来存储这些数据，会造成大量的空间浪费。这时，离散化算法就可以发挥作用，将这些数据映射到一个较小的连续区间，从而节省空间。

步骤

  • 收集数据：将所有需要离散化的数据收集到一个集合中。在实际代码中，通常使用 vector 来存储这些数据。
  • 排序：对收集到的数据进行排序，确保数据按升序排列。排序的目的是为了后续去重和二分查找操作的方便。
  • 去重：去除排序后数据中的重复元素，只保留每个不同值的一个副本。这样可以避免后续映射时出现重复的映射关系。
  • 映射：将去重后的数据依次映射到一个连续的整数区间，通常从 1 开始。可以使用二分查找来实现这个映射过程，即对于每个原始数据，在去重后的有序数组中查找其位置，该位置就是映射后的整数。

模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 离散化函数，返回 x 离散化后的结果
int find(int x, const vector<int>& alls) {
    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;
    }
    // 映射到从 1 开始的连续区间
    return r + 1;
}

int main() {
    // 示例数据
    vector<int> data = {100, 200, 100, 300, 400};

    // 步骤 1: 收集数据
    vector<int> alls = data;

    // 步骤 2: 排序
    sort(alls.begin(), alls.end());

    // 步骤 3: 去重
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 步骤 4: 映射
    for (int num : data) {
        int discrete_num = find(num, alls);
        cout << "原始数据: " << num << ", 离散化后的数据: " << discrete_num << endl;
    }

    return 0;
}

区间合并

区间合并算法是一种用于将多个区间进行合并，以得到一组不重叠区间的算法。下面将详细介绍该算法，包括适用场景、算法步骤、代码实现和复杂度分析。

使用场景

  • 日程安排问题：合并重叠的会议时间段，以得到更清晰的日程安排。
  • 线段覆盖问题：将重叠的线段合并为不重叠的线段集合。
  • 数据处理：对具有重叠范围的数据进行整合。

步骤

  • 排序：将所有区间按照左端点从小到大进行排序。如果左端点相同，则按照右端点从小到大排序。排序的目的是为了方便后续的合并操作，确保在遍历区间时，前面的区间不会被后面的区间所包含。
  • 初始化：一个合并后的区间，初始值为第一个区间（如果存在），并使用两个变量分别记录该区间的左端点和右端点。
  • 遍历区间：从第二个区间开始，依次遍历所有区间。对于每个区间，根据其与当前合并区间的关系进行处理：
    • 如果当前区间的左端点大于当前合并区间的右端点，说明这两个区间不重叠，将当前合并区间加入结果集，并更新当前合并区间为当前遍历到的区间。
    • 如果当前区间的左端点小于等于当前合并区间的右端点，说明这两个区间重叠，更新当前合并区间的右端点为这两个区间右端点的最大值。

模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 将所有存在交集的区间合并
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;
}