凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

算法学习笔记_如果枢轴归位位置的左侧区间至少有2个元素,则对左侧小数序列进行递归划分

作者：凡人多烦事01 | 2024-02-14 22:08:15

踩

如果枢轴归位位置的左侧区间至少有2个元素,则对左侧小数序列进行递归划分

刷算法

排序

快速排序

主要思想

快速排序是一种分治算法，它通过从数组中选择一个**“枢轴”元素并根据它们是否小于或大于枢轴将其他元素分成两个子数组**。然后递归地对子数组进行排序。快速排序算法的平均时间复杂度为 $O (n l o g n)$ ，最坏时间复杂度为 $O(n^2)$ 。

解决过程

确定分界点

分界点即为主要思想中提到的“枢纽”元素，一般选择中点对应的数为分界点。

调整范围

使用两个指针 i ，j分别指向数组的左右两端，然后向中间靠拢。如果指针对应的数小于分界点，则移到左部，反之移到右部。当两个指针相遇的时候，则停止移动指针，开始对左右两部分继续前序操作。当一开始两个指针的位置相同时，则表明这部分只有一个数，就返回。

代码

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; // 先移动 再判断
    while(i < j){
        while(q[++i] < x); // 先移动 保证第一个/最后一个数能被考察
        while(q[--j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    
    quick_sort(q,l,j);
    quick_sort(q,j + 1, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

快速选择（第k小数）

主要思想

运用快速排序算法，但不对整个数组进行排序，仅排序第k个小的数所在的数组。因为快速排序算法将数组分为较小和较大的两部分，所以仅需比较分开位置与k的大小，就能确定下次排序的数组。其时间复杂度为 $O (n)$ 。

解决过程

首先利用快速排序算法将数组分为两部分，计算左侧部分的元素数量(sl)，并将其与k进行比较。如果k小于或等于sl，则意味着第k小的元素在左侧部分，因此它会递归该部分。否则，它意味着第k小的元素在右侧部分，因此它会递归该部分，并通过减去sl来调整k。当它在子数组中找到第k小的元素时，该函数返回。

代码

int quick_select(int l , int r, int k) // 快速选择
{
    if(l >= r) return q[l];
    
    int x = q[(l + r) / 2], 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);
    else return quick_select(j + 1, r, k - sl);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

归并排序

主要思想

采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。其时间复杂度为 $O (n l o g n)$ 。该算法为稳定的算法，也就是说值相同的元素不会被交换位置。

解决过程

首先将序列分成左右两部分，然后再将各部分继续分解，直到序列只有一个数，然后开始向上合并。合并两序列时，使用双指针，再使用一个临时数组存储当前合并的序列，当某指针指向的值更小时，则将其放入临时数组中，指针向后移动，重复指到两个指针均指向子序列尾部。

代码

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 i = l, j = mid + 1, k = 0;
    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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

逆序对数量

主要思想

归并排序归并阶段是将两个有序的子序列合并成一个完整序列。也就是说，当在左部序列中找到比右部序列当前指向的值大的数之后，左部序列之后所有的元素都会与之形成逆序对。所以只需在归并阶段加上对逆序对数量的增加，即可算出总的逆序对数量。

解决过程

分为三种情况，假设分为 Left 和 Right 两部分，左右两边指针分别为 i 和 j。

如果逆序对两元素**均在 Left **，进行左部的归并排序。
如果逆序对两元素**均在 Right **，进行右部的归并排序。
如果逆序对两元素在两侧，归并排序时在左部找到比右部元素大的元素，其后所有的元素都与右部元素组成逆序对。个数为mid-i+1。
最后返回个数。

代码

LL merge_sort(int q[], int l, int r)
{
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL res = 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 ++];
            res += mid - i + 1;
        }
    }
    
    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];
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二分

数的范围

主要思想

通过二分分别查找左边界和右边界，但左右边界的临界情况不同，需要分开讨论。

解决过程

查找左边界：左边界的右边可能存在值相等的情况，所以判断时用>=进行判断中点情况。如果此时中点满足，则表明左边界在中点左侧，则需更新右部的值，反之更新左部的值。
**没有条件满足：**如果在查找左边界后，现在的值与输入元素值不等，则表明不存在。
查找右边界：右边界的左边可能存在值相等的情况，所以判断时用<=进行判断中点情况。如果此时中点满足，则表明右边界在中点右侧，则需更新左部的值，反之更新右部的值。

代码

#include <iostream>
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;
        // 寻找左边界 模板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;
        // 寻找右边界 模板2 注意求中点+1是防止进入死循环
        else
        {
            cout << l << " ";
            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
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
40
41
42
43
44
45

高精度

主要思想

对高精度的数使用两个数组存储每一位的值，再在每一位上分别进行运算。

加法

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

减法

减法时需要注意借位情况，可以设置一个t表示借位。每次进行运算时先减去这个借位，然后再进行减法运算。减法运算完后，将t进行加10再取模就能保证为非负数。最后比较一下t是否为负数，如果为负数就表明需要借位，将t设置为1，方便下次运算时先进行-1。需要注意的是，在进行运算前需要对两数进行大小判断，如果是小-大就要额外加上负号。

// 已经比较过大小 A为更大的数
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;
    }
    // 消去前导0 如“002”
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

乘法

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 + t;
        C.push_back(t % 10);
        t /= 10;
    }
    if(t != 0) C.push_back(t);
    // 消去前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

除法

进行除法时，模拟人的运算方法，从高位开始。如果该数小于除数，那么将该数（可以看成余数）乘10，然后和之后的数相加，再进行相除。

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); // 不够除C会在后面加上0
        r = r % B;
    }
    // 因为从高位开始，并且输出时数组相反，所以需要翻转
    reverse(C.begin(), C.end());
    // 消去前导0
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return C;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

前缀和、差分

一维前缀和

令第i个数 $a_i$ 的前缀和为 $S_i$ ，那么 $S_i = a_1 + a_2 + ... + a_i$ 。

作用

利用前缀和可以快速求出一个区间的和。例如求 $[l, r]$ 区间的和，那么 $S_{l,r} = S_r - S_{l-1}$ 。

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

const int N = 1e5 + 10;

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

int main()
{
    cin >> n >> m;
    q[0] = 0, s[0] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> q[i];
        s[i] = s[i - 1] + q[i];
    }
    
    while (m -- )
    {
        int l,r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }
    
    return 0;
}
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

二维前缀和

二维数组的前缀和如下图所示， $（ i, j ）$ 点的前缀和为橙色部分。

若要求 $S_{i,j}$ ，黄色部分已知，那么 $S_{i,j} = S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} + a_{i,j}$ 。

代码

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

const int N = 1010;

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

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

一维差分

差分相当于前缀和的逆运算。令数组 $a, b$ ，若 $b$ 是 $a$ 的差分数组，则满足 $a_i = b_1 + b_2 + ... +b_i$ 。

求一个序列在区间内进行操作后得到的新序列

假设在 $a$ 的 $[l, r]$ 区间内，将每个数都加上c。那么只需要进行 $b_l +c$ 与 $b_{r+1} - c$ 两个操作，前者保证 $l$ 之后的每个 $a_i$ 都加上c，后者保证 $r$ 之后的每个 $a_i$ 都保持不变。

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

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    
    while (m -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c;
        b[r + 1] -= c;
    }
    
    for(int i = 1 ; i <= n; i++) a[i] = a[i - 1] + b[i];
    for(int i = 1 ; i <= n; i++) cout << a[i] << " ";
    
    return 0;
}
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

二维差分

同二维前缀和，二维差分中 $a$ 数组为 $b$ 数组的前缀和。

矩阵中一个区间内进行操作后得到新的矩阵

$a, b$ 数组的转换同前缀和理，主要讨论对区间的操作。令两个元素坐标分别为 $x_1,y_1)$ 和 $x_2,y_2)$ ，将以这两元素形成的矩阵中，每个元素加上c。那么可以对 $b$ 数组进行操作。假设为图中黄色填充部分为需要操作的部分，那么对 $(x 1, y 1)$ 加上c，会导致红框部分都会加上，那么需要减去蓝色线条与绿色线条部分，并加上多减去的相交部分。

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

const int N = 1010;

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

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
        }
        
    while(q --)
    {
        int x1,y1,x2,y2,c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        b[x1][y1] += c;
        b[x1][y2+1] -= c;
        b[x2+1][y1] -= c;
        b[x2+1][y2+1] += c;
    }
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}
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
40
41
42

双指针

最长连续不重复子序列

额外使用一个数组记录数出现的次数，如果在这个连续子序列里出现了一次以上，就说明需要移动左端指针，调整子序列。在移动左指针的同时对子序列中数的出现次数也需要进行调整，当这个子序列中没有重复的数后，再次移动右端指针。

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

const int N = 1e5 + 10;

int n;
int q[N],r[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++)
    {
        r[q[i]]++;
        while (r[q[i]] > 1) r[q[j++]]--;
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    
    return 0;
}
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

数组元素的目标和

暴力搜索可以得出两个元素都有单调性，即可降维使用双指针。因为两个数组都是单增序列，所以一个数组指向前端，一个指向后端。当两数和大于目标值时，移动指向后端的指针。否则移动前端指针。

#include <iostream>
#include <cstring>
#include <algorithm>
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(a[i] + b[j] == x)
        {
            cout << i << " " << j;
            break;
        }
    }
    
    return 0;
}
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

离散化

离散化是指将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。如同区间和一题（原题链接），数组范围太大，而需要用到的数据范围很小，就使用离散化存储在一小段数组中。

在这道题中存储的是需要用到的点的坐标，包括需要增加的点和查询的点。因为可能有多个相同的点，所以需要将其进行去重，并排序。然后再使用前缀和的方式求出查询的和。

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

typedef pair<int, int> PII;
// 增加需要10w,查询需要2*10w，共30w
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; // 前缀和下标从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);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

区间合并

原题链接

将所有区间按照从小到大排序，从最小的区间开始逐一遍历。定义一个 start 和 end，如果较大区间的开始在 start - end 之内，就更新区间，反之将前一个区间加入到合并完成的数组中，从当前区间继续遍历。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs; // 存储区间

vector<PII> merge(vector<PII> &segs)
{
    vector<PII> res;
    
    sort(segs.begin(), segs.end());
    // 先将端点设置极限值
    int st = -2e9, ed = -2e9;
    for (auto item : segs)
        if (ed < item.first)
        {
            if (ed != -2e9) res.push_back({st, ed}); 
            st = item.first, ed = item.second;
        }
        else ed = max(ed, item.second); // 更新区间end
    
    if (st != -2e9) res.push_back({st, ed}); // 遍历完成后还需要加入一次
    
    segs = res;
    
    return segs;
} 

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    
    merge(segs);
    
    cout << segs.size() << endl;
    
    return 0;
}
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
40
41
42
43
44
45
46
47
48
49

链表

使用数组模拟链表，会比指针更快，因为 C++ 的 new 方法效率太低，但不太能考虑内存的情况。

单链表

head 变量存储头节点的下标，idx 变量存储目前添加到的下标，e[] 数组存储链表的值，ne[] 数组存储当前下标对应的节点指向的节点下标。

// 头插法
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++;
}

// 删除下标为 k 的节点指向的节点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

// 在下标为 k 的节点之后插入值为 x 的节点
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

双链表

l[] 数组存储当前节点左侧的节点下标，r[] 数组存储当前节点右侧的节点下标。

void init()
{
    // 0下标为head，1下标为tail
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 在第 k 个插入的数右边插入
// 链表左侧插入时 k = 0
// 链表右侧插入时 k = l[1]
// 如果表示在第 k 个插入的数左边插入 那么 k = l[k]
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}

void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
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

栈

模拟栈

使用数组模拟栈，如果起始下标为0，那么栈顶指针就要从-1开始。

**栈空：**栈顶指针小于0。

**查询：**输出栈顶指针所指的值。

push：栈顶指针先+1，再赋当前位置的值。

**pop：**栈顶指针-1。

int tt = -1; // 栈顶下标
int stk[N];

void push(int x)
{
    stk[++ tt] = x;
}

void pop()
{
    tt --;
}

void query()
{
    cout << stk[tt] << endl;
}

void empty()
{
    if (tt < 0) cout << "YES" << endl;
    else cout << "NO" << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

中缀表达式求值

使用一个运算符栈和一个数字栈。扫描表达式，是数字就入栈。是运算符：左括号直接入栈；是右括号就进行计算，直到运算符栈的栈顶为左括号；是加减乘除就进行判断，如果当前运算符优先级<=栈顶运算符优先级，则先计算，直到当前运算符优先级更高，否则直接入栈。

#include <iostream>
#include <cstring>
#include <stack>
#include <unordered_map>
#include <algorithm>
using namespace std;

const int N = 10010;

stack<int> num;
stack<char> op;

void eval()
{
    // 靠后的数会先出栈
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    
    char opt = op.top(); op.pop();
    
    int res = 0;
    if(opt == '+') res = a + b;
    if(opt == '-') res = a - b;
    if(opt == '*') res = a * b;
    if(opt == '/') res = a / b;

    num.push(res);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++)
    {
        char c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++] - '0';
            num.push(x);
            i = j - 1;
        }
        // 左括号无优先级 直接入栈
        else if (c == '(') op.push(c);
        // 有括号直接开始计算 直到出现左括号
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        // 其他运算符 如果栈顶优先级大于此时 则运算
        // 如果栈顶优先级小于此时 直接入栈
        else
        {
            while (!op.empty() && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    // 如果栈中还有 则计算
    while (!op.empty()) eval();
    cout << num.top() << endl; // 结果存储在栈顶
    
    return 0;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

队列

模拟队列

使用数组模拟队列。需要一个队首指针fr和队尾指针bc。

**队列空：**fr = bc。

**查询：**输出fr指向的值。

**push：**先赋bc指向的值，再将bc+1。

**pop：**fr+1。

int q[N];
int fr = 0,bc = 0; // fr 队首，bc 队尾

void push(int x)
{
    q[bc ++] = x;
}

void pop()
{
    fr ++;
}

void query()
{
    cout << q[fr] << endl;
}

void empty()
{
    if (fr == bc) cout << "YES" << endl;
    else cout << "NO" <<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

单调

单调栈

找到数组每个元素左侧离它最近的比它小的元素。组成一个单调栈，如果都没有比其小的，说明之后所有元素都不可能找到在其之前的元素位置了。

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

const int N = 10010;

int stk[N];
int n,tt = 0;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        // 如果栈顶元素更大 则pop
        while (tt && stk[tt] >= x) tt --;
        // 如果栈不空 则找到比当前元素小的 输出当前栈顶元素
        if (tt) cout << stk[tt] << " ";
        // 如果栈空 则左侧均比他大 输出-1
        else cout << -1 << " ";
        // 当前元素入栈
        stk[++ tt] = x;
    }
    
    return 0;
}
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

单调队列

滑动窗口

原题链接

滑动窗口使用单调队列构建递增的序列。因为存在先进先出的性质，所以队首总是指向最小/大的值。每次循环（一次滑动）需要解决四件事：

**队首是否滑出窗口：**所以队列存储的是元素的下标
队尾元素是否小/大于等于当前元素：如果是，则不满足单调，队尾元素出队列，进行循环判断
将当前元素入队：如果不满足2，说明队空或者现在已经单调
输出具体元素：当指针到窗口的阈值时开始输出

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

const int N = 1000010;

int a[N], q[N];
int n, k;

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++) cin >> a[i];
    
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++) // 输出窗口内最小值
    {
        if (i - k + 1 > q[hh]) hh ++; // 队首已出窗口
        while (hh <= tt && a[i] <= a[q[tt]]) tt --; // 当前元素小于等于队尾元素
        q[++ tt] = i; // 将当前元素坐标加入队列
        if(i + 1 >= k) cout << a[q[hh]] << " ";
    }
    cout << endl;
    return 0;
}
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

KMP

主要思想是，找出串中相同的两段，在后续字符匹配不上时，直接将串移至前序相同串的末尾，这样可以减少循环次数。

next数组：1-j这段区间的串中，前缀和后缀相同的最大长度。例如abcab这组串中，当指针指向最后的5时，前缀为：{a,ab,abc,abca},后缀为：{b,ab,cab,bcab}，故 next[5] = 2。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];
int ne[N];

int main()
{
    cin >> n;
    cin >> p + 1; // 从下标1开始
    // 构造next数组
    for (int i = 2, j = 0; i <= n; i ++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }
    cin >> m;
    cin >> s + 1; // 从下标1开始
    // 进行字符串匹配
    for (int i = 1, j = 0; i <= m; i ++)
    {
        // 当后续匹配不上时，直接转向前序相同序列的
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++;
        if (j == n) // 匹配完成
        {
            cout << i - n << " ";
            j = ne[j];
        }
    }
    
    return 0;
}
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

Trie树

主要思想是利用树，将仅含一种数据类型的字符串进行存储（例如全为小写字母，全为数字）。

字符串统计

原题链接

存储：利用树对每个字符进行存储，每个字符串完成后，对最后一个字符进行标识（即存储以它结尾的字符串的个数）。

匹配：逐一字符进行查找，如果当前字符没有的话直接返回 0 。如果全部匹配完成后，返回标识数据。

void insert(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx; // 如果当前位置没有存储东西
        p = son[p][u];
    }
    cnt[p] ++; // 对字符串末尾进行标识
}

int query(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i ++)
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最大异或对

原题链接
将数字以二进制形式从高位开始存储，整型二进制最多31位，故从 i=30 开始递减，将每位二进制放进Trie树中。从高位开始存储利于找到最大值。查找时，将给定的从高位开始，向高位取反的方向进行查找。

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1; // 获取第i位的二进制
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if (son[p][!u]) // 最优情况向取反方向走
        {
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else // 否则往另一方向走
        {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}
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

*并查集

**解决：**将两个集合合并；询问两个元素是否在一个集合中

基本原理：将每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点。

问题：

如何判断树根: if (p[x] == x)
如何求x的集合编号: while (p[x] != x) x = p[x]; 这一步用路径压缩优化，查询某个点的集合时，将其父节点均直接指向树根。
如何合并两个集合: p_x是x的集合编号，p_y是y的集合编号。p_x = y，即将一个树根直接连接另一个树根。

堆

堆本质是一棵完全二叉树（除叶结点外，其余结点均非空，叶结点从左至右排列）。以小根堆为例，每个结点均小于等于其左右儿子，故根节点为最小值。

存储：使用一维数组存储，从下标 $1$ 开始。每个结点的左儿子下标为 $2 x$ ，右儿子下标为 $2 x + 1$ 。

操作：

down(x)：某元素值变大，就将其往下移。需与左右儿子找最小值交换。
up(x)：与down操作相反。只需与父节点比较大小。

解决问题：

插入：在数组尾部插入元素，然后使用up。
求最小：数组首部。
删除最小：用数组尾部覆盖首部元素，然后使用down。
删除任意元素：用数组尾部覆盖被删除元素，然后使用down+up。
修改任意元素：修改后使用down+up。
初始化堆：若 $s i ze = n$ ，那么只需在 $1\backsim 2/n$ 范围内进行down操作。因为下标在 $2/ n$ 内的均不是叶结点，而叶结点不需要down操作。此时的时间复杂度为 $O (n)$ 。

排序

思路是每次输出数组首部，然后删除。循环规定的m次。

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

const int N = 100010;

int n, m;
int h[N], size1;

void down(int x)
{
    int t = x;
    if (x * 2 <= size1 && h[x * 2] < h[t]) t = x * 2; // 判断左儿子
    if (x * 2 + 1 <= size1 && h[x * 2 + 1] < h[t]) t = x * 2 + 1; // 判断右儿子
    if (t != x) // 不是down的下标 则交换
    {
        swap(h[x], h[t]);
        down(t);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    size1 = n;
    
    for (int i = n/2; i; i --) down(i);
    
    while (m --)
    {
        cout << h[1] << " ";
        h[1] = h[size1];
        size1 --;
        down(1);
    }
    
    return 0;
}
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

模拟堆

原题链接

题目需要的求的是第 $k$ 个插入的数，所以添加两个指针数组hp，ph。hp为h指向p，ph为p指向h。ph[k]表示第 $k$ 个插入元素目前在堆中的下标。hp[k]表示堆中下标为 $k$ 的元素，是第几个插入的元素，主要用来定位ph数组的位置。

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

const int N = 100010;

int n, m; // m表示第m个插入的数
int h[N], ph[N], hp[N], sz;

void heapswap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void up(int x)
{
    while (x/2 && h[x/2] > h[x])
    {
        heapswap(x/2, x);
        x >>= 1;
    }
}

void down(int x)
{
    int t = x;
    if (x * 2 <= sz && h[x * 2] < h[t]) t = x * 2;
    if (x * 2 + 1 <= sz && h[x * 2 + 1] < h[t]) t = x * 2 + 1;
    if (t != x)
    {
        heapswap(t, x);
        down(t);
    }
}

int main()
{
    cin >> n;
    m = 0;
    while (n --)
    {
        string op;
        int k, x;
        cin >> op;
        
        if (op == "I")
        {
            cin >> x;
            sz ++;
            m ++;
            h[sz] = x;
            ph[m] = sz, hp[sz] = m;
            up(sz);
        }
        else if (op == "PM") cout << h[1] << endl;
        else if (op == "DM")
        {
            heapswap(1, sz); // 需要将指针也进行交换，否则会指向错误
            sz --;
            down(1);
        }
        else if (op == "D")
        {
            cin >> k;
            k = ph[k];
            heapswap(sz, k);
            sz --;
            up(k);
            down(k);
        }
        else
        {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }
    
    return 0;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

二叉树遍历（动画图源：YuXi_0520）

先序遍历

根-左-右，相当于沿着树的外围跑一圈，最后回到根节点。
在这里插入图片描述

中序遍历

左-根-右，相当于垂直投影，即可得到答案。
在这里插入图片描述

后序遍历

左-右-根，相当于葡萄剪枝，一颗颗剪下则需先剪叶子结点。
在这里插入图片描述

层序遍历

相当于广度优先搜索，把一层从左到右依次遍历完成后，再转到下一层。

在这里插入图片描述

01/完全背包问题

在这里插入图片描述

问题分析

这两个问题的区别为：01背包每个背包只能使用一次，完全背包每个背包可以使用无数次。

两个问题都可以确定的一个规则是：该背包选或不选。再确定是否可以多次选择。

那么使用动态规划可以进行求解，他们分别的状态转换方程则为：

01背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
完全背包:dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])
1
2

01背包与完全背包的前一项均相同，代表着不选择该背包。后一项唯一区别是选择之后是否忽略该背包，01背包中减一操作代表着，当前考察的背包不再选择，而完全背包则不需要进行该操作。

代码

01背包

二维数组

#include <bits/stdc++.h>
using namespace std;
int n, v;

int main()
{
    cin >> n >> v;
    int size[n + 1], worth[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> size[i] >> worth[i];
    int dp[n + 1][v + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= v; j++)
        {
            if (j >= size[i])
                dp[i][j] = max(dp[i - 1][j], dp[i-1][j - size[i]] + worth[i]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][v] << endl;

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

一维数组

利用滚动数组，结合状态转换方程可知，需要逆序考察，因为还未更新过的dp数组值可能会被使用

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
    cin >> n >> m;
    int v[n + 1], w[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    int dp[m + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= 0; j--)
        {
            if (j >= v[i])
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

完全背包

二维数组

#include <bits/stdc++.h>
using namespace std;
int n, v;

int main()
{
    cin >> n >> v;
    int size[n + 1], worth[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> size[i] >> worth[i];
    int dp[n + 1][v + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= v; j++)
        {
            if (j >= size[i])
                dp[i][j] = max(dp[i - 1][j], dp[i][j - size[i]] + worth[i]); // 这里有变化
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][v] << endl;

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

一维数组

因为未更新的数据不需要使用，所以直接正向进行循环

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
    cin >> n >> m;
    int v[n + 1], w[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    int dp[m + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= 0; j--) // 这里有变化
        {
            if (j >= v[i])
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

完全背包

二维数组

#include <bits/stdc++.h>
using namespace std;
int n, v;

int main()
{
    cin >> n >> v;
    int size[n + 1], worth[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> size[i] >> worth[i];
    int dp[n + 1][v + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= v; j++)
        {
            if (j >= size[i])
                dp[i][j] = max(dp[i - 1][j], dp[i][j - size[i]] + worth[i]); // 这里有变化
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][v] << endl;

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

一维数组

因为未更新的数据不需要使用，所以直接正向进行循环

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
    cin >> n >> m;
    int v[n + 1], w[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    int dp[m + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= 0; j--) // 这里有变化
        {
            if (j >= v[i])
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/82027

算法学习笔记_如果枢轴归位位置的左侧区间至少有2个元素,则对左侧小数序列进行递归划分

刷算法

排序

快速排序

主要思想

解决过程

确定分界点

调整范围

代码

快速选择（第k小数）

主要思想

解决过程

代码

归并排序

主要思想

解决过程

代码

逆序对数量

主要思想

解决过程

代码

二分

数的范围

主要思想

解决过程

代码

高精度

主要思想

加法

减法

乘法

除法

前缀和、差分

一维前缀和

作用

二维前缀和

代码

一维差分

求一个序列在区间内进行操作后得到的新序列

二维差分

矩阵中一个区间内进行操作后得到新的矩阵

双指针

最长连续不重复子序列

数组元素的目标和

离散化

区间合并

链表

单链表

双链表

栈

模拟栈

中缀表达式求值

队列

模拟队列

单调

单调栈

单调队列

滑动窗口

KMP

Trie树

字符串统计

最大异或对

*并查集

堆

排序

模拟堆

二叉树遍历（动画图源：YuXi_0520）

先序遍历

中序遍历

后序遍历

层序遍历

相关题目

问题分析

代码

常规解法

DFS解法

01/完全背包问题

问题分析

代码

01背包