第二章 数据结构

一、数组模拟链表、栈、队列

单链表基本操作

详见： https://www.acwing.com/problem/content/828/

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
#include<iostream>
using namespace std;
const int N=100010;

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int e[N],ne[N],head,idx;

// 初始化
void init()
{
    head=-1;
}

// 将x插到头结点
void add_head(int x)
{
    e[idx]=x;ne[idx]=head;head=idx++;
}

// 将x插到下标是k的点后面
void add_k(int k,int x)
{
    e[idx]=x;ne[idx]=ne[k];ne[k]=idx++;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k]=ne[ne[k]];
}

int main()
{
    int n;
    cin>>n;
    init();
    while(n--)
    {
        char op;
        int k,x;
        cin>>op;
        if(op=='I')
        {
            cin>>k>>x;
            add_k(k-1,x);
        }
        else if(op=='H')
        {
            cin>>x;
            add_head(x);
        }
        else
        {
            cin>>k;
            if(!k) head=ne[head];
            else remove(k-1);
        }
    }
    for(int i=head;i!=-1;i=ne[i])  cout<<e[i]<<' ';
    return 0;
}

双链表基本操作

详见： https://www.acwing.com/problem/content/829/

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
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

int main()
{
    cin >> m;

    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;

    while (m -- )
    {
        string op;
        cin >> op;
        int k, x;
        if (op == "L")
        {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R")
        {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 队尾的值
q[tt];

// 判断队列是否为空
if (hh <= tt)
{

}

二、单调栈 & 单调队列

单调栈 O(n)：

应用1：求左边第一个比当前数小的数

1
2
3
4
5
6
7
8
9
10
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
    while(tt && stk[tt]>=a[i]) tt--;
    if(!tt) printf("-1 ");
    else printf("%d ",stk[tt]);
    stk[++tt]=a[i];
}

应用2：求左边第一个比当前数大的数

1
2
3
4
5
6
7
8
9
10
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
    while(tt && stk[tt]<=a[i]) tt--;
    if(!tt) printf("-1 ");
    else printf("%d ",stk[tt]);
    stk[++tt]=a[i];
}

应用3：求右边第一个比当前数小的数

1
2
3
4
5
6
7
8
9
10
11
12
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
reverse(a,a+n);
for(int i=0;i<n;i++)
{
    while(tt && stk[tt]>=a[i]) tt--;
    if(!tt) b[i]=-1;
    else b[i]=stk[tt];
    stk[++tt]=a[i];
}
for(int i=n-1;i>=0;i--) printf("%d ",b[i]);

应用4：求右边第一个比当前数大的数

1
2
3
4
5
6
7
8
9
10
11
12
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
reverse(a,a+n);
for(int i=0;i<n;i++)
{
    while(tt && stk[tt]<=a[i]) tt--;
    if(!tt) b[i]=-1;
    else b[i]=stk[tt];
    stk[++tt]=a[i];
}
for(int i=n-1;i>=0;i--) printf("%d ",b[i]);

单调队列（滑动窗口）

详见：https://www.acwing.com/problem/content/156/

思路：最小值和最大值分开来做，两个for循环完全类似（四步走战略）

  • 解决队首已经出窗口问题；

  • 解决队尾与当前元素a[i]不满足单调性问题；

  • 将当前元素下标加入队尾；

  • 如果满足条件则输出

注意：上面四个步骤中，一定要先3后4，因为有可能输出的正是新加入的那个元素；队列中存的是原数组的下标，取值时要在套一层，a[q[]]; 算最大值前注意将hh 和 tt重置；hh从0开始，数组下标也要从0开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n,k;
   cin>>n>>k;
   for(int i=0;i<n;i++) cin>>a[i];
   // 求最小值
   for(int i=0;i<n;i++)
   {
       if(hh<=tt && i-q[hh]+1>k) hh++;
       while(hh<=tt && a[q[tt]]>=a[i]) tt--;
       q[++tt]=i;
       if(i-k+1>=0)  cout<<a[q[hh]]<<' ';
   }
   
   cout<<endl;
   
   //求最大值
   hh=0,tt=-1;
   for(int i=0;i<n;i++)
   {
       if(hh<=tt && i-q[hh]+1>k) hh++;
       while(hh<=tt && a[q[tt]]<=a[i]) tt--;
       q[++tt]=i;
       if(i-k+1>=0)  cout<<a[q[hh]]<<' ';
   }

三、KMP (字符串匹配问题)

全称：Knuth-Morris-Pratt算法

通俗易懂："字符串A是否为字符串B的子串?如果是的话出现在B的哪些位置?字符串A称为模板串，字符串B称为模式串。

详见：https://www.acwing.com/problem/content/833/

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
   char p[N],S[M];

cin>>n>>p+1>>m>>S+1;    
   // 求next数组
   for(int i=2,j=0;i<=n;i++)    // 注意此处i=2，如果从1开始会TLE
   {
       // 关心的是j最多能走到哪里
       while(j && p[i]!=p[j+1]) j=ne[j]; // 失配，右移p串
       if(p[i]==p[j+1]) j++;   
       ne[i]=j;    
   }
   
   // kmp匹配过程
   for(int i=1,j=0;i<=m;i++)
   {
       // 关心的是j能不能走完
       while(j && S[i]!=p[j+1]) j=ne[j];
       if(S[i]==p[j+1]) j++;
       if(j==n)
       {
           // 匹配成功
           cout<<i-n<<' ';   // 注意下标是从1开始，答案需要往前退一
           j=ne[j];          // 必要的操作，不然会越界
       }
   }

四、Trie 树

概念：高效地存储和查找字符串集合的数据结构。Trie树也叫做字典树，它是一个树形结构。是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串。

性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
  3. 每个节点的所有子节点包含的字符都不相同

image-20240313165739441

详见：https://www.acwing.com/problem/content/837/

代码：

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
#include<iostream>
using namespace std;
const int N=100010;
int son[N][26];  // son数组第一维类比单链表的ne[]，第二维是用来做映射的，即存储的是哪一个字符
int cnt[N],idx;  // cnt[]可以理解为标记数组，由于不同字符串结尾标记不同（是由于每个字符的idx不同），所以可以用来进行查询次数的操作
char str[N];

void insert(char *str)
{
    int p=0;  // 相当于是一个指针，从根结点开始
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';   // 映射到son[][]数组的第二维
        if(!son[p][u]) son[p][u]=++idx;  // 没有路则创建路
        p=son[p][u];        // 更新p
    }
    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];
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char op;
        cin>>op>>str;
        if(op=='I') insert(str);
        else cout<<query(str)<<endl;
    }        
    return 0;
}

应用：son[][] 不仅能存字符串也能存二进制数，也能存整数

最大异或对：

详情：https://www.acwing.com/problem/content/145/

暴力算法：O(n^2)

Trie：O(n)

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100010,M=31*N;  // 最多有N个数，一个数需要31个Node
int son[M][2],idx;
int a[N];
void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=(x>>i)&1;   
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
}

int query(int x)
{
    // 在查找的同时就计算 x 的最大异或值
    int res=0,p=0;   
    for(int i=30;i>=0;i--)
    {
        int u=(x>>i)&1;
        if(son[p][!u])   // 表示p节点有两个子节点，根据贪心，我们走和u相反的那条路
        {
            p=son[p][!u];
            res = res*2+1;   // 根据移位和异或的原理
        }
        else            // 表示p节点只有一个子节点，选无可选
        {
            p=son[p][u];
            res = res*2+0;
        }
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) 
    {
        cin>>a[i];
        insert(a[i]);   // 输入的同时进行插入
    }
    
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=max(res,query(a[i]));
    }
    cout<<res<<endl;
    return 0;
}

五、并查集

功能：

  • 将两个集合合并
  • 询问两个元素是否在一个集合当中

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

问题：

  • 如何判断树根：if (p[x] == x)
  • 如何求x的集合编号：while (p[x] != x) x = p[x]
  • 如何合并两个集合 ：p[x] 是 x 的集合编号 p[y] 是 y 的集合编号 p[x] = y

由于每次求x的集合编号 每次需要遍历到根节点，复杂度与树的高度成正比，于是就有了并查集路径压缩优化

详见：https://www.acwing.com/problem/content/838/

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
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int p[N];
int find(int x)  // 寻找 x 的祖宗节点 + 路径压缩优化
{
    if(p[x]!=x) p[x]=find(p[x]);  // 若 x 不是根节点 则让其父亲的成为其父亲的祖宗
    return p[x];
}

int main()
{
    cin>>n>>m;
    string op;
    for(int i=1;i<=n;i++) p[i]=i;   // 初始化为 n 个不同的集合
    while(m--)
    {
        int x,y;
        cin>>op>>x>>y;
        if(op[0]=='M') p[find(x)]=find(y);  // 合并集合
        else				// 查询两个元素是否属于同一集合
        {
            if(find(x)==find(y)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

应用：

  • 维护一个集合中元素个数，增加一个cnt[] 数组即可，注意初始化为 1 ，只维护根节点的cnt[]，在合并集合时更新cnt[]
  • 维护一个集合中每个元素到根结点的距离

六、堆（数组模拟）

本质：一颗完全二叉树

小根堆：每一个点都是小于等于左右儿子，根节点是最小值

大跟堆：每一个点都是大于等于左右儿子，根节点是最大值

堆的存储：一个一维数组

​ x 的左儿子是2x

​ x的右儿子是2x+1

功能（以小顶堆为例）：

  • 插入一个数： 插入到最后一个位置，不断上移 heap[ ++ size] = x; up(size) O(longn)
  • 求集合当中的最小值： 取出堆顶 heap[1] O(1)
  • 删除最小值 ：将最后一个元素赋给堆顶，然后不断下移 heap[1] = heap[size--]; down(1) O(longn)
  • -------------（以下stl中的堆实现不了）
  • 删除任意一个元素：将最后一个元素赋给该元素，然后不断移动 heap[k] = heap[size--]; down(k); up(k); O(longn)
  • 修改任意一个元素：heap[k] = x; down(k); up(x) O(longn)

两个基本操作：（上述五个功能可全部由这两个基本操作来实现）

down(x) ：将一个数变大，应该下移

1
2
3
4
5
6
7
8
9
10
11
void down(int u)
{
    int t = u;
    if(u*2 <= n && h[u*2] < h[t]) t = 2*u;
    if(u*2+1 <= n && h[u*2+1] < h[t]) t = 2*u + 1;
    if(u!=t) // 看是否发生了交换操作
    {
        swap(h[t],h[u]);
        down(t);
    }
}

up(x) ：将一个数变小，应该上移

1
2
3
4
5
6
7
8
void up(int x)
{
    while(u/2 && h[u/2] > h[u])  
    {
        swap(h[u/2],h[u]);
        u >>= 1;
    }
}

堆排序

详见：https://www.acwing.com/problem/content/840/

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int h[N];
int n,m;

void down(int u)
{
    int t = u;
    if(u*2<=n && h[u*2] < h[t]) t = u*2;
    if(u*2+1<=n && h[u*2+1] < h[t]) t= u*2+1;
    if(t!=u)
    {
        swap(h[u],h[t]);
        down(t);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>h[i];
    
    for(int i=n/2;i>=1;i--) down(i);  // 创建小顶堆 从 n/2 开始有很大考究……
    
    while(m--)
    {
        cout<<h[1]<<' ';
        h[1] = h[n--];   // 相当于删除堆顶元素
        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
// 交换两个点，及其映射关系
//ph[k]： 第k个插入堆里面的点在堆里的的下标是什么
//hp[k]：堆里面下标为k的点是第几个插入的点
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

详见：https://www.acwing.com/problem/content/841/

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N],ph[N],hp[N],cnt;

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

void down(int u)
{
    int t=u;
    if(2*u<=cnt && h[u*2]<h[t])  t=u*2;
    if(2*u+1<=cnt && h[u*2+1]<h[t]) t=u*2+1;
    if(t!=u)
    {
        heap_swap(u,t);
        down(t);
    }
}

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

int main()
{
    int n;
    cin>>n;
    char op[5];
    int m=0;
    while(n--)
    {
        int k,x;
        cin>>op;
        if(!strcmp(op,"I"))
        {
            cin>>x;
            cnt++;
            ph[++m]=cnt;
            hp[cnt]=m;
            h[cnt]=x;
            up(cnt);
        }
        else if(!strcmp(op,"PM")) cout<<h[1]<<endl;
        else if(!strcmp(op,"DM")) 
        {
            heap_swap(1,cnt);
            cnt--;
            down(1);
        }
        else if(!strcmp(op,"D"))
        {
            cin>>k;
            k=ph[k];
            heap_swap(k,cnt);
            cnt--;
            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
int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

  • 拉链法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 我宣你！！！

// 向哈希表中插入一个数
void insert(int x)
{
    int k = (x%N+N)%N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

// 在哈希表中查询某个数是否存在
bool query(int x)
{
    int k = (x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])
    {
        if(e[i]==x) return true;
    }
    return false;
}

注：哈希时取模一定要质数吗：

​ 假如关键字是随机分布的，那么无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题

字符串哈希（kmp算法的劲敌）

核心：全称字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字

功能：快速判断两个字符串是否相等时，使用字符串哈希

1
2
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

板子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

详见：https://www.acwing.com/problem/content/843/

参考题解：https://www.acwing.com/solution/content/24738/

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010,P = 131;
ULL h[N],p[N];
char str[N];
int n,m;

ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r - l + 1];
}

int main()
{
    cin>>n>>m;
    scanf("%s",str+1);
    p[0]=1;
    // 预处理前缀和
    for(int i=1;i<=n;i++)
    {
        p[i] = p[i-1]*P;
        h[i] = h[i-1]*P + str[i];
    }
    
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)!=get(l2,r2)) puts("No");
        else puts("Yes");
    }
    
    return 0;
}