单链表

邻接表：n个链表，用于存储图和树

image-20230329145817796

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// e和ne通过下标关联在一起

// 初始化
void init(){
    head = -1; // -1标记空节点
    idx = 0; 
}

// 在链表头插入一个数a
void inset(int a){
    e[idx] = a, ne[idx] = head, head = idx ++;
}

// 将头结点删除，需要保证头结点存在
void remove(){
    head = ne[head];
}

1. AcWing 826. 单链表

C++

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
#include <iostream>

using namespace std;

const int N = 100010;

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

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

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

// 将x插到下标是k的点后面
void insert(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;
    scanf("%d", &n);
    init();
    while (n --){
        int k, x;
        char op;
        cin >> op;
        if (op == 'H'){
            cin >> x;
            insert(x);
        }
        else if (op == 'D'){
            cin >> k;
            if (k)
                remove(k - 1); // 注意存储从0开始，而题目从1开始
            else // 特判删除头结点
                head = ne[head];
        }
        else{
            cin >> k >> x;
            insert(k - 1, x);
        }
    }
    
    for (int i = head; i != -1; i = ne[i])
        cout << e[i] << ' ';
    puts("");
    return 0;
}

Python

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
def main():
    N = 100010
    head = - 1
    e = [0] * N
    ne = [0] * N
    idx = 0
    
    def insert_head(x):
        nonlocal idx, head
        e[idx] = x
        ne[idx] = head
        head = idx
        idx += 1
        
    def insert(k, x):
        nonlocal idx
        e[idx] = x
        ne[idx] = ne[k]
        ne[k] = idx
        idx += 1
        
    def remove(k):
        ne[k] = ne[ne[k]]
        
    m = int(input())
    while m:
        data = input().split()
        if data[0] == "H":
            x = int(data[1])
            insert_head(x)
        elif data[0] == "D":
            k = int(data[1])
            if k:
                remove(k - 1) # 注意存储从0开始，而题目从1开始
            else: # 特判删除头结点
                head = ne[head]
        else:
            k, x = int(data[1]), int(data[2])
            insert(k - 1, x)
        m -= 1
    
    i = head
    res = []
    while i != -1:
        res.append(e[i])
        i = ne[i]
    print(" ".join(map(str, res)))
    
if __name__ == "__main__":
    main()

双链表

用于优化某些问题

模板

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

int m;
int e[N], l[N], r[N], idx;

// 初始化
void init(){
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;// 需要注意左端点只有右邻接点，右端点只有左邻接点
    // 初始时左右端点互为邻接点
    idx = 2; 
}

// 在节点a的右边插入一个数x
// 在节点a的左边插入一个数相当于在l[a]右边插入一个数
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];
}

1. AcWing 827. 双链表 - AcWing

C++

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int e[N], l[N], r[N], idx;

void init(){
    // 注意初始时，下标0位置设为头结点，下标1位置设为尾节点
    r[0] = 1, l[1] = 0; 
    idx = 2;
}

// 在节点a的右边插入一个数x
// 在节点a的左边插入一个数x等价于在节点l[a]的右边插入一个数x
// 在最左端插入即在0右侧插入，在最右端插入即在1左侧插入
void insert(int k, int x){
    e[idx] = x;
    l[idx] = k, r[idx] = r[k];
    l[r[k]] = idx, r[k] = idx ++;
}

void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(){
    scanf("%d", &n);
    init();
    while (n -- ){
        int k, x;
        string op;
        cin >> op;
        if (op == "L"){
            cin >> x;
            insert(0, x);
        }
        else if (op == "R"){
            cin >> x;
            insert(l[1], x); // 在节点a的左边插入一个数x等价于在节点l[a]的右边插入一个数x
        }
        else if (op == "D"){
            cin >> k;
            // 注意下标0和1表示存储头和尾，元素从下标2开始存储，而题目从1开始
            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;
}

Python

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
def main():
    N = 100010
    e = [0] * N
    l = [0] * N
    r = [0] * N
    r[0], l[1] = 1, 0
    idx = 2
    
    def insert(k, x):
        nonlocal idx
        e[idx] = x
        l[idx], r[idx] = k, r[k]
        l[r[k]] = idx 
        r[k] = idx
        idx += 1
        
    def remove(k):
        l[r[k]] = l[k]
        r[l[k]] = r[k]
        
    m = int(input())
    while m:
        data = input().split()
        if data[0] == "L":
            x = int(data[1])
            insert(0, x)
        elif data[0] == "R":
            x = int(data[1])
            insert(l[1], x)
        elif data[0] == "D":
            k = int(data[1])
            remove(k + 1)
        elif data[0] == "IL":
            k, x = int(data[1]), int(data[2])
            insert(l[k + 1], x)
        else:
            k, x = int(data[1]), int(data[2])
            insert(k + 1, x)
        m -= 1
        
    i = r[0] # 注意0和1都不存储元素，只标记头和尾，取值从r[0]开始
    res = []
    while i != 1:
        res.append(e[i])
        i = r[i]
    print(" ".join(map(str, res)))
    
if __name__ == "__main__":
    main()

栈

模板

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

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

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

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0){

}

1. AcWing 828. 模拟栈

C++

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 <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int m;
int stk[N], tt;

int main(){
    cin >> m;
    while (m --){
        int x;
        string op;
        cin >> op;
        if (op == "push"){
            cin >> x;
            stk[++ tt] =x;
        }
        else if (op == "query")
            cout << stk[tt] << endl;
        else if (op == "pop") tt --;
        else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 直接使用列表的方法即可模拟栈
def main():
    n = int(input())
    stk = []
    while n:
        q = input().split()
        if q[0] == "push":
            stk.append(int(q[1]))
        elif q[0] == "pop":
            stk.pop() # list的pop()方法默认弹出最后元素
        elif q[0] == "empty":
            print("YES" if len(stk) == 0 else "NO")
        elif q[0] == "query":
            print(stk[-1])
        n -= 1
        
if __name__ == "__main__":
    main()

2. AcWing 3302. 表达式求值

一. 问题分析

1. 信息提取

+ 和 - 等价, * 和 / 等价

所以只需分析 + 和 *

  • * 优先级比 + 大

    $2 + 3 * 2$ 对应的树为

  • 同优先级左边大于右边

    $2 + 3 + 2$ 对应的树为

  • 括号优先级大于其他

    $(2 + 3) * 2$ 对应的树为

    看起来是 + 的优先级比 * 大, 其实是因为括号的优先级比 * 大

2. 总结特点

  • 优先级大的运算符在下面, 优先级小的运算符在上面

  • 叶节点都是数字, 内部节点都是运算符, 括号不作为节点, 但会作为一个运算符参与运算符优先级的比较

二. 问题建模

1. 中序遍历表达式树的计算过程

  • 任意一个表达式树

    叶节点是数字, 内部节点是运算符

  • 计算过程

  • 遍历节点 1 2 3 后, 则 4 的左子树遍历完, 则计算 4 的左子树的结果, 新节点作为 4 的左孩子节点

  • 继续遍历节点 5 6 7, 则 8 的左子树遍历完, 则计算 8 的左子树的结果, 新节点作为 8 的左孩子节点

  • 同理, 遍历节点 12 的时候计算其左子树的结果, 新节点作为 12 的左孩子

  • 当整棵树遍历完后, 再次逆序计算各运算符的结果, 最后只剩一个节点就是表达式的最终结果

    注意计算 8 的左子树时先计算运算符 6, 然后结果作为运算符 4 的右孩子, 然后计算运算符 4, 其结果作为运算符 8 的左孩子

2. 计算过程分析

如何判断某棵子树被遍历完 ?

  • 中序遍历往上走时, 子树遍历完

    例如过程 1 中遍历节点 4 时, 说明 1 2 3 的子树遍历完

  • 中序遍历往下走时, 子树未遍历完

    例如过程 2 中遍历节点 6 时, 相对于 4 是往下走的, 此时 8 的左子树未遍历完

如何判断往上走还是往下走 ?

  • 注意到运算符优先级大的在下面, 运算符优先级小的在上面

  • 所以当目前运算符的优先级比上一运算符优先级小时, 说明是往上走

  • 当目前运算符的优先级比上一运算符优先级大是, 说明是往下走

什么时候进行计算 ?

  • 往上走时, 因为此时子树遍历完, 需要计算子树的结果, 并将结果作为一个新的节点代替原来的子树

    例如遍历节点 8 时, 计算 8 的左子树, 然后将计算结果作为新的节点代替原来的左子树

三. 问题解法

1. 数据结构

由于是模拟中序遍历树的过程, 所以要用栈数据结构

由于是有运算符和数字两个对象, 所以要用两个栈来存储

2. 算法

遇到各节点后的处理

  1. 数字

    数字并不会产生计算过程, 所以只需提取数字, 将数字压栈

  2. 括号

    括号分为两个运算符 ( 和 )

    遇到 ( 说明会往下走, 所以只需将 ( 压栈

    遇到 ) 说明会往上走, 所以要计算括号表示的子树的结果, 所以要逆向计算运算符直至遇到 (

  3. 普通二元运算符

    如果当前运算符优先级比上一运算符高, 说明是往下走, 则只需将运算符压栈

    如果当前运算符优先级比上一运算符低, 说明是往上走, 则需要一直计算上一运算符直至当前运算符优先级比上一运算符高

3. 核心代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i = 0; i < s.size(); i++)
{
    char c = s[i];              // c 是当前字符
    if(isdigit(c))              // 如果 c 是数字, 就提取数字
    {
        int x = 0, j = i;
        while(j < s.size() && isdigit(s[j])) x = x * 10 + s[j++] - '0';
        i = j - 1;
        num.push(x);
    }
    else if(c == '(') op.push(c);       // 如果 c 是 '(', 就压栈
    else if(c == ')')                   // 如果 c 是 ')', 就一直计算到 '(' 
    {
        while(op.top() != '(') eval();  // eval 函数的功能是计算上一运算符
        op.pop();                       // '(' 出栈
    }
    else                                // 如果 c 是普通运算符, 就一直计算到 c 的优先级比上一运算符高
    {
        while(op.size() && pr[op.top()] >= pr[c]) eval();
        op.push(c);                     // c 入栈
    }
}


四. 算法证明

循环不变式

当前运算符及之前所有运算符的左子树都是形如下图的形状

前五个例子, 后面的形状以此类推

证明

初始化

当 i = 0 时, 当前运算符为空, 循环不变式显然成立

保持

假定在某轮循环前, 循环不变式成立

执行该轮 for 循环

c 为当前字符

当 c 为数字时

会提取数字, 然后将数字压栈

则前面的所有子树形状不变, 循环不变式成立

当 c 为 ( 时

会将 ( 压栈

则前面的所有子树形状不变, 循环不变式成立

当 c 为 ) 时

会一直逆序计算运算符直到遇到 (

根据假定, ) 前面的左子树, 即 () 表示的整棵子树是形如下图的形状

则一直逆序计算运算符直到遇到 ( 会计算 () 表示的整棵子树, 然后将计算结果作为新的节点代替原来的子树

则 () 表示的整棵子树被一个节点代替, 该节点会使得左子树的形状保持循环不变式的形状

例 1 当 () 表示的整棵子树是上图的第一棵子树时

如 2 + (3) , (3) 就是上图的第一棵子树

计算结果是 2 + 3, 对应的子树保持循环不变式的形状

例 2 当 () 表示的整棵子树是上图的第一棵子树时

如 2 * (3 + 2), (3 + 2) 就是上图的第二棵子树

计算结果是 2 * 5, 对应的子树保持循环不变式的形状

例 3 当 () 表示的整棵子树是上图的第三棵子树时

如 1 + 2 * (3 + 2 * 3) * 3, (3 + 2 * 3) 就是上图的第三棵子树

计算结果是 1 + 2 * 9 * 3, 对应的子树保持循环不变式的形状

注: 此处 “对应的子树” 意为 ‘)’ 运算符前面的运算符的左子树, 即 1 + 2 * 9

当 c 为普通运算符时

会一直逆序计算优先级比自己高的运算符

根据假定, 当前运算符前面的左子树都是形如下图的形状

整棵树的形状可以为下图

一直逆序计算优先级比自己高的运算符会计算当前运算符的左子树, 并将计算结果作为当前运算符的左孩子

过程如下所示

所以当前循环结束后, 循环不变式保持成立

终止

当 for 循环结束后, 整棵树的形状也是循环不变式的形状

总结

所以在 for 循环结束后, 需要逆序计算运算符直至没有运算符为止, 最终整棵树计算为一个节点, 该节点就是表达式的计算结果

队列

模板

普通队列

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

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

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

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt){

}

循环队列

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

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt){

}

1. AcWing 829. 模拟队列

C++

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 <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int m;
int q[N], hh = 0, tt = -1;

int main(){
    cin >> m;
    
    while (m --){
        int x;
        string op;
        cin >> op;
        if (op == "push"){
            cin >> x;
            q[++ tt] = x;
        }
        else if (op == "pop") hh ++;
        else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl;
        else if (op == "query") cout << q[hh] << endl;
    }
    return 0;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 直接用list的方法，复杂度为O(n^2), 因为pop(0)的话是O(n)的
def main():
    n = int(input())
    q = []
    
    while n:
        data = input().split()
        if data[0] == "push":
            q.append(data[1])
        elif data[0] == "pop":
            q.pop(0) 
        elif data[0] == "empty":
            print("NO" if len(q) else "YES")
        elif data[0] == "query":
            print(q[0])
        n -= 1

if __name__ == "__main__":
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 数组模拟栈，复杂度为O(n),通过下标移动可以减少时间复杂度
def main():
    n = int(input())
    q = []
    hh, tt = 0, -1
    
    while n:
        data = input().split()
        if data[0] == "push":
            q.append(data[1]) 
            tt += 1
            # 也可以一次性开好数组，用下标tt添加元素
            # tt += 1
            # q[tt] = data[1]
        elif data[0] == "pop":
            hh += 1
        elif data[0] == "empty":
            print("NO" if hh <= tt else "YES")
        elif data[0] == "query":
            print(q[hh])
        n -= 1

if __name__ == "__main__":
    main()
Deque简介

双向队列deque是栈和队列的一种广义实现，是类似于list的容器，可以快速的在队列头部和尾部添加、删除元素，deque是python的collections中的一个类。

  • append()就是默认从尾部即右侧添加数据

  • appendleft()方法从deque队列的左侧添加数据

  • pop() 方法弹出元素，从尾部弹出，并且返回弹出的这个元素

  • popleft() 方法弹出元素，从头部弹出，并且返回弹出的这个元素、

在队列两端插入或删除元素时间复杂度都是 O(1) ，而在列表的开头插入或删除元 素的时间复杂度为 O(N) 。

deuqe与list的区别相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。list实现出队（pop）和插入（insert）时的空间复杂度大约为O(n)，deque在出队（pop）和入队（append）时的时间复杂度是O(1)。

使用q=deque()代替q=list()，因为q.popleft()效率比q.pop(0)高这是因为：列表实现是基于数组的。pop(0)从列表中删除第一个项，它需要左移len(lst) - 1个项来填补空白。 deque()实现使用双向链表。因此无论deque有多大，deque.popleft()都需要一个常量的操作数。即deque.popleft()：T(n)=O(1)，而list.pop(0)：T(n)=O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 使用python库双端队列
from collections import deque
def main():
    n = int(input())
    q = deque([])
    
    while n:
        data = input().split()
        if data[0] == "push":
            q.append(data[1])
        elif data[0] == "pop":
            q.popleft()
        elif data[0] == "empty":
            print("NO" if q else "YES")
        elif data[0] == "query":
            print(q[0])
        n -= 1

if __name__ == "__main__":
    main()

单调栈

类似于双指针算法，使用单调栈进行优化时可以首先写出暴力算法，然后研究状态之间的关系，挖掘出某些性质，使我们可以聚焦在比较少的状态中，排除冗余和非法元素/状态，得到单调性并利用单调性得到极值用于求解，实现实现从$O(k)$到$O(1)$的优化。

单调栈的定义

单调栈是栈的一中特殊形式，在栈中的元素必须满足单调性（一定是单调上升或单调下降等等的规律）。

单调栈的思想是利用不断迭代的方式，将当前的元素x与栈顶元素进行比较，按照单调性性质来决定是对栈顶元素做出栈操作还是将当前元素压栈来保证栈的单调性。

单调栈的维护

既然我们必须让元素满足单调性，那么每次插入就和栈顶作比较。如果不满足某些性质，直接弹出栈顶，直到栈为空或满足该性质插入这个元素。

  • 单调递增栈：在保持栈内元素单调递增的前提下（如果栈顶元素大于要入栈的元素，则将其弹出），将新元素入栈。

  • 单调递减栈：在保持栈内元素单调递减的前提下（如果栈顶元素小于要入栈的元素，则将其弹出），将新元素入栈。

单调栈的性质

单调栈的时间复杂度是 $O(n)$

单调栈1

对于将要入栈的元素来说，在对栈进行更新后（即弹出了所有比自己大的元素），此时栈顶元素就是数组中左侧第一个比自己小的元素；

单调栈2

对于将要入栈的元素来说，在对栈进行更新后（即弹出了所有比自己小的元素），此时栈顶元素就是数组中左侧第一个比自己大的元素；

单调栈的应用

给定一个序列，求序列中的每一个数左边或右边第一个比他大或比他小的数在什么地方

模板

1
2
3
4
5
6
// 常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ ){
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

1. AcWing 830. 单调栈

1
2
3
for (int i = 0; i < n; i ++)
    for (int j = i - 1; j >= 0; j --)
        // compare and select

接下来可以思考，在遍历过程中，哪些状态是非法或冗余的：

在数组中，如果i < j且a[i] > a[j]，则在j之后时，显然a[j]一定能完全替换掉a[i]（更偏左且更小），a[i]永远不会被用到，是冗余的。

为了去除冗余，显然我们需要维护一个单调序列，从而保证每个状态都不是冗余的。下面考虑如何维护，这需要考虑题目要求。由于我们找的是最左的一个小于当前数的值，即对于小于当前数的值，最左的优先，而不是最小的优先。因此除了需要维护单调序列之外，还需要保证序列中每个数的相对位置是从左到右排的，且优先取后加入的数作为答案，这显然是可以使用单调栈进行维护。

不妨考虑当前数a[i]小于s[end]，则需要用a[i]替换掉s[end]。然而这没有结束，还要继续和s中其他数进行比较，直到整个序列都是单调的。只不过，由于必须保证相对位置是从左到右排的，就必须从右往左单向逐个比较，这即单调栈的出栈入栈过程。

55289_7a61998ec0-20201211221031165

注意要先进行所有出栈操作，再得到当前答案，最后再将当前数入栈。栈为空说明无解。

C++

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int tt;
int stk[N];

int main(){
    scanf("%d", &n);
    while (n --){
        int x;
        scanf("%d", &x);
        // 求的是左边第一个最近最小的数，如果栈顶元素大于等于x，
        // 那么就说明栈顶这个数明显没有x好，所以就把stk[tt]弹出了
        // 使栈中序列保持单调
        // 注意特判栈空的情况
        while (tt && stk[tt] >= x)
            tt --;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        // 最后将x插入栈顶；
        stk[++ tt] = x;
    }
    return 0;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def main():
    n = int(input())
    nums = map(int, input().split())
    stk = []
    res = []
    for x in nums:
        while stk and x <= stk[-1]:
            stk.pop()
        if not stk:
            res.append("-1")
        else:
            res.append(str(stk[-1]))
        stk.append(x)
    print(" ".join(res))
    
if __name__ == "__main__":
    main()

单调队列

模板

1
2
3
4
5
6
7
// 常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ){
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

1. AcWing 154. 滑动窗口

滑动窗口中的最值。

思路也是先写暴力算法，然后研究状态之间的关系，挖掘出某些性质，使我们可以聚焦在比较少的状态中，排除冗余和非法元素/状态，是序列始终是单调的，并利用单调性优化问题。求最值的话直接取端点即可，如果查找一个值的话，可以用二分。

窗口由于元素有进有出，且始终在一侧进另一侧出，因此可以用队列来维护。

研究队列中元素的关系，可以发现由于出队的顺序为先进先出，所以，如果后入队的元素优于先进的元素，在其入队后就完全替代了先入队的元素。本题求的是队列/窗口中的最小值，因此如果a[i] >= a[j]，且 i < j（a[i]会先出队)，则a[j]入队后就替代a[i]。因此可以直接使冗余元素在a[j]入队同时出队，从而使队列中序列始终是单调递增的。从而最小值答案就在队头。

image-20230330211529667

C++

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
// AcWing 154. 滑动窗口——单调队列
#include <iostream>

using namespace std;
const int N = 1000010;

int a[N], q[N];
// q[N]为单调队列，存储下标

int main(){
  int n, k;
  scanf("%d%d", &n, &k);

  for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);

  // 单调队列
  int hh = 0, tt = -1; 
  // hh和tt用于维护滑动窗口
  // hh 表示滑动窗口开头的位置
  // tt 表示当前要存储处的前一个位置，也是滑动窗口尾端的位置（已存储的最后一个位置）

  for (int i = 0; i < n; ++ i){
    // i为当前滑动窗口最后一个元素的位置，窗口范围为i - k + 1到i
    // 需要保证滑动窗口中至少有一个元素，所以hh <= tt
    // 另外要保证在滑动窗口范围内，所以i - k + 1 <= q[hh]
    // 这样从hh到tt即为当前窗口的合法元素
    // 维护窗口大小
    if (hh <= tt && i - k + 1 > q[hh]) hh ++;

    // 这里利用单调性对队列进行优化
    // 由于求的是窗口中的最小值，所以只要新加入的元素比前面的元素还小，前面的元素即可删掉
    // 所以新加入的元素要从后往前和窗口中元素比较大小，存入最后一个比它小的元素后面
    // 这样就导致队列中存储的元素始终保持单调递增，最小的元素也就始终是窗口开头的元素，即a[q[hh]]
    // 维护序列单调性
    while (hh <= tt && a[q[tt]] >= a[i]) tt --;
    // 一定会入队
    q[++ tt] = i;

    // 刚开始窗口内元素不足k时，不输出
    if (i >= k - 1) printf("%d ", a[q[hh]]);
  }
  puts("");

  hh = 0, tt = -1;
  for (int i = 0; i < n; ++ i){
    if (hh <= tt && i - k + 1 > q[hh]) hh ++;

    // 反过来，队列单调递减，开头元素最大
    while (hh <= tt && a[q[tt]] <= a[i]) tt --;
    q[++ tt] = i;

    if (i >= k - 1) printf("%d ", a[q[hh]]); 
  }
  puts("");
  return 0;
}

Python

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
def main():
    N = 1000010
    hh, tt = 0, - 1
    q = [0] * N
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    
    for i in range(n):
        # 维护窗口大小
        while hh <= tt and i - k + 1 > q[hh]:
            hh += 1
        # 维护队列单调性
        while hh <= tt and nums[q[tt]] >= nums[i]:
            tt -= 1
        tt += 1
        q[tt] = i
        if i >= k - 1:
            print(nums[q[hh]], end=" ")
    print()
    
    hh, tt = 0, -1
    for i in range(n):
        while hh <= tt and i - k + 1 > q[hh]:
            hh += 1
        while hh <= tt and nums[q[tt]] <= nums[i]:
            tt -= 1
        tt += 1
        q[tt] = i
        if i >= k - 1:
            print(nums[q[hh]], end=" ")
    print()
    
if __name__ == "__main__":
    main()
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
# 使用deque
from collections import deque
def main():
    q= deque([])
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    
    for i in range(n):
        # 维护窗口大小
        while q and i - k + 1 > q[0]:
            q.popleft()
        # 维护队列单调性
        while q and nums[q[-1]] >= nums[i]:
            q.pop()
        q.append(i)
        if i >= k - 1:
            print(nums[q[0]], end=" ")
    print()
    
    q.clear()
    hh, tt = 0, -1
    for i in range(n):
        while q and i - k + 1 > q[0]:
            q.popleft()
        while q and nums[q[-1]] <= nums[i]:
            q.pop()
        q.append(i)
        if i >= k - 1:
            print(nums[q[0]], end=" ")
    print()
    
if __name__ == "__main__":
    main()

KMP算法

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
// 求模式串的Next数组，只与模式串有关
// Next[i]存储以p[i]为结尾且与前缀匹配的最长后缀
// i为待匹配的后缀结尾字符，j为已匹配的前缀的结尾，j + 1表示待匹配的前缀字符
for (int i = 2, j = 0; i <= m; i ++ ){
    while (j && p[i] != p[j + 1]) j = ne[j];  // 如果出现不匹配，就回退到上一次匹配的前缀位置
    if (p[i] == p[j + 1]) j ++ ; // 如果匹配了，则前缀后移继续匹配，求出最长的匹配
    ne[i] = j; // 记录匹配的位置（不匹配的话会退到0）
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ ){
    while (j && s[i] != p[j + 1]) j = ne[j]; // 如果出现不匹配，就回退到上一次匹配的前缀位置
    if (s[i] == p[j + 1]) j ++ ;// 如果匹配了，则后移继续匹配
    // 匹配成功
    if (j == m){
        j = ne[j]; // 回退到下一轮继续匹配的位置
        // 匹配成功后的逻辑
    }
}

1. AcWing 831. KMP字符串

C++

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
#include <iostream>
using namespase std;

const int N = 10010, M = 100010;
int n, m;
char p[N], s[M];
int ne[N];

int main(){
    cin.tie(0);
    cin >> n >> p + 1 >> m >> s + 1;// 读入字符串和其长度，注意这里数组从1开始
    // s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
    // 求模式串的next数组的过程；注意这里从1开始
    ne[1] = 0;//第一个匹配失败则一定重新开始
    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;
    }

    // kmp匹配过程
    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){
            printf("%d ", i - n);
            j = ne[j]; // 方便下一次查找
        }
    }
    return 0;
}

Python

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
def main():
    n = int(input())
    p = ' ' + input()
    m = int(input())
    s = ' ' + input()
    ne = [0] * (n + 1)

    j = 0
    for i in range(2, n + 1):
        while j and p[i] != p[j + 1]:
            j = ne[j]
        if p[i] == p[j + 1]:
            j += 1
        ne[i] = j
    
    j = 0
    for i in range(1, m + 1):
        while j and s[i] != p[j + 1]:
            j = ne[j]
        if s[i] == p[j + 1]:
            j += 1
        if j == n: # j指向p的末尾则匹配成功
            print(i - j, end=" ") # 存储从下标1开始，但本题题目要求从0下标开始
            j = ne[j]

if __name__ == "__main__":
    main()

Tire树

基本用法：高效地存储和查找字符串集合地数据结构

可以查找是否出现过及出现过多少次。字符串末尾符号对应节点要打上标记，说明此字符串存在及出现次数。

利用树形结构共享存储

Tire树一般一定会限制字符范围是26个小写字母或52个大小写字母，或是很小范围内的数字

模板

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
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
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. AcWing 835. Trie字符串统计

C++

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
// AcWing 835. Trie字符串统计
#include <iostream>
using namespace std;

const int N = 100010;
char str[N];
int son[N][26], cnt[N], idx;
// 因为题目字符只能是小写字母，所以每个节点至多26条边
// 下标是0的点，既是根节点又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量，同时cnt以线性顺序表示每个节点
// idx表示当前用到的下标，注意下标是0的节点既是根节点又是空节点

// 插入一个字符串
void insert(char str[]){
    int p = 0;
    // 遍历字符串
    for (int i = 0; str[i]; ++i){
        int u = str[i] - 'a'; // 先求当前字母对应的子节点编号，a-z映射到0-25
        if (!son[p][u]) son[p][u] = ++idx; // 判断是否存在对应子节点，不存在则需创建
        // 注意这里用数组模拟链表，idx起指针作用
        p = son[p][u]; // 走到子节点， p存储子节点对应的cnt中的位置
    }
    ++ 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;
    scanf("%d", &n);
    while(n--){
        char op[2];
        scanf("%s%s", op, str);
        if (op[0] == 'I') insert(str);
        else printf("%d\n",query(str));
    }
    return 0;
}

Python

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
def main():
    N = int(1e5 + 5)
    son = [[0] * 26 for _ in range(N)]
    cnt = [0] * N
    idx = 0
    
    def insert(x):
        nonlocal idx
        p = 0
        for v in x:
            u = ord(v) - ord('a')
            if not son[p][u]:
                idx += 1
                son[p][u] = idx
            p = son[p][u]
        cnt[p] += 1
    
    def query(x):
        p = 0
        for v in x:
            u = ord(v) - ord('a')
            if not son[p][u]:
                return 0
            p = son[p][u]
        return cnt[p]
        
    n = int(input())
    while n:
        n -= 1
        op, s = input().split()
        if op == 'I':
            insert(s)
        else:
            print(query(s))
            
if __name__ == "__main__":
    main()

2. AcWing 143. 最大异或对

C++

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
// AcWing 143. 最大异或对
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 31 * N;

int n;
int a[N], son[M][2], idx;

void insert(int x){
    int p = 0;
    for (int i = 30; i >= 0; -- i){
        int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    } 
}

int query(int x){
    int p = 0, res = 0;
    for (int i = 30; i >= 0; -- i){
        int s = x >> i & 1;
        if (son[p][!s]){
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i){
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    
    int res = 0;
    for (int i = 0; i < n; ++ i) res = max(res, query(a[i]));
    printf("%d\n", res);
    return 0;
}

Python

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
def main():
    N = 100010
    M = N * 31
    son = [[0] * 2 for _ in range(M)]
    idx = 0
    
    def insert(x):
        nonlocal idx
        p = 0
        for i in range(30, -1, -1):
            u = x >> i & 1
            if not son[p][u]:
                idx += 1
                son[p][u] = idx
            p = son[p][u]
    
    def query(x):
        p, res = 0, 0
        for i in range(30, -1, -1):
            u = x >> i & 1
            if son[p][~u]:
                res += 1 << i
                p = son[p][~u]
            else: p = son[p][u]
        return res
    
    n = int(input())
    nums = list(map(int, input().split()))
    res = 0
    for x in nums:
        insert(x)
        res = max(query(x), res)
    print(res)

if __name__ == "__main__":
    main()

并查集

操作：

  1. 将两个集合合并

  2. 询问两个元素是否在一个集合当中

并查集能够在近乎$O(1)$完成这两个操作

原理：

  • 每个集合用一棵树表示，树根的编号就是集合的编号

  • 每个节点存储它的父节点，p[x]表示x的父节点

技巧：

  1. 如何判断树根：

  2. 如何求x的集合编号：

  3. 如何合并两个集合： px是x的集合编号，py是y的集合编号，只需（合并集合只需要增加一个从根节点到根节点的边）

优化：

  • 路径压缩：找到根节点后，将走过的路径上所有节点的父节点都变成根节点（只会搜一遍，后面就不用遍历查找了）

  • 按秩合并：在对两个不同子集连接时，按照rank来连，也就是rank低的连在rank高的下面。rank高的做父亲节点

一般使用“路径压缩”，而“按秩合并”一般可不使用

并查集同时可以维护

  • 每个集合大小

  • 每个节点到根节点的距离

模板

递归路径压缩

1
2
3
4
5
6
int find(int x){       //查找x元素所在的集合, 返回x的祖宗节点，回溯时压缩路径
    if (x != p[x]){
        p[x] = find(p[x]);     //回溯时的压缩路径
    }         //从x结点搜索到祖先结点所经过的结点都指向该祖先结点
    return p[x];
}

非递归式

查两遍，第一遍找到祖宗节点并存储，第二遍更新路径上每个节点的父节点为祖宗节点

1
2
3
4
5
6
7
8
9
10
11
12
13
int find(int x){
    int k, j, r;
    r = x;
    while(r != p[r])     //查找根节点
        r = p[r];      //找到根节点，用r记录下
    k = x;        
    while(k != r){            //非递归路径压缩操作
        j = p[k];         //用j暂存parent[k]的父节点
        p[k] = r;        //p[x]指向跟节点
        k = j;                    //k移到父节点
    }
    return r;         //返回根节点的值            
}

(1) 朴素并查集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点 + 路径压缩
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
// 初始时每个节点的父节点为自身
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 判断操作
if (find(a) == find(b))

// 合并操作，合并a和b所在的两个集合
p[find(a)] = find(b); // 使a集合根节点插到b集合根节点下

(2)维护集合大小size的并查集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
    p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)]; // 合并时更新集合大小, 只用维护根节点size
p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x){
    if (p[x] != x){
        d[x] += d[p[x]];
	    p[x] = find(p[x]);
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ){
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; 
// 根据具体问题，初始化find(a)的偏移量

1. AcWing 836. 合并集合

C++

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
// AcWing 836. 合并集合——朴素并查集
#include <iostream>
using namespace std;

const int N = 100010;

int n, m;
int p[N];//存储每个点的祖宗节点

// 返回x的祖宗节点 + 路径压缩
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){

    scanf("%d%d ", &n, &m);

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i++) p[i] = i;

    while(m --)
    {
        char op[2];// 注意这里不使用%c，防止出错
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M') p[find(a)] = find(b);// 合并a和b所在的两个集合：
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

python

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
# AcWing 836. 合并集合——朴素并查集
def main():
    N = 100010
    p = [0] * N
    
    def find(x):
        if p[x] != x:
            p[x] = find(p[x])
        return p[x]
        
    n, m = map(int, input().split())
    # 注意题中编号从1开始
    for i in range(1, n + 1):
        p[i] = i
    while m:
        m -= 1
        op, a, b = input().split()
        a, b = int(a), int(b)
        if op == 'M':
            p[find(a)] = p[find(b)]
        else:
            if find(a) == find(b):
                print("Yes")
            else:
                print("No")

if __name__ == "__main__":
    main()

2. AcWing 837. 连通块中点的数量

C++

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
// AcWing 837. 连通块中点的数量
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int p[N], cnt[N];

int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++ i){
        p[i] = i;
        cnt[i] = 1;
    }
    while (m --){
        string op ;
        int a, b;
        cin >> op;
        if (op == "C"){
            cin >> a >> b;
            if (find(a) != find(b)){
                cnt[find(b)] += cnt[find(a)];
                p[find(a)] = find(b);
            }
        }
        else if (op == "Q1"){
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else{
            cin >> a;
            printf("%d\n", cnt[find(a)]);
        }
    }
    return 0;
}

Python

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
# AcWing 837. 连通块中点的数量
def main():
    N = 100010
    p = [0] * N
    cnt = [0] * N
    
    def find(x):
        if p[x] != x:
            p[x] = find(p[x])
        return p[x]
    
    n, m = map(int, input().split())
    for i in range(1, n + 1):
        p[i] = i
        cnt[i] = 1
    
    while m:
        m -= 1
        op, *num = input().split()
        if op == 'C':
            a, b = int(num[0]), int(num[1])
            a, b = find(a), find(b)
            if a != b:
                cnt[b] += cnt[a]
                p[a] = b
        elif op == 'Q1':
            a, b = int(num[0]), int(num[1])
            if find(a) == find(b): print("Yes")
            else: print("No")
        else:
            a = int(num[0])
            print(cnt[find(a)])
            
if __name__ == "__main__":
    main()

堆

堆即优先队列

操作：

  1. 插入一个数

    1
    heap[++ size] = x; up(size)

  2. 求集合当中的最小值

    1
    heap[1]

  3. 删除最小值

    1
    2
    3
    heap[1] = heap[size];
    size--;
    down(1);

  4. 删除任意一个元素

    1
    2
    3
    4
    heap[k] = heap[size];
    size --;
    down(k);
    up(k);

  5. 修改任意一个元素

    1
    2
    3
    heap[k] = x;
    down(k);
    up(k);

堆是完全二叉树，除了最后一层节点都是满的

小根堆：父节点小于两个子节点

大根堆：父节点大于两个子节点

模拟堆：使用数组存储二叉树

x左儿子：2x

x右儿子：2x+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
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
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;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

1. AcWing 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
30
31
32
33
34
35
36
37
38
// 堆排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// cnt为当前节点数
void down(int u){
    int t = u;
    if (u * 2 <= cnt && h[u*2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u*2+1] < h[t]) t = u * 2 + 1;
    if (u != t ){
        swap(h[u], h[t]);
        down(t);
    }
}
void up(int u){
    while (u / 2 && h[u/2] > h[u]){
        swap(h[u/2], h[u]);
        u /= 2;
    }
}
int main(){
    scanf("%d%d", &n,&m);
    for (int i = 1;i <= n; ++i) scanf("%d", &h[i]);
    cnt = n;
    
    // O(n)建堆
    for (int i = n / 2; i; -- i) down(i);
    while(m--){
        printf("%d ", h[1]);
        h[1] = h[cnt--];
        down(1);
    }
    return 0;
}

2. AcWing 839. 模拟堆

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
// 模拟堆
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], ph[N], hp[N], cnt;
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// cnt为当前节点数
void heap_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b])
}
void down(int u){
    int t = u;
    if (u*2 <= cnt && h[u*2] < h[t]) t = u * 2;
    if (u*2+1 <= cnt && h[u*2+1] < h[t]) t = u * 2 + 1;
    if (u != t ){
        swap(h[u], h[t]);
        down(t);
    }
}
void up(int u){
    while (u / 2 && h[u/2] > h[u]){
        swap(h[u/2], h[u]);
        u /= 2;
    }
}
int main(){
    scanf("%d%d", &n,&m);
    for (int i = 1;i <= n; ++i) scanf("%d", &h[i]);
    cnt = n;
    
    // O(n)建堆
    for (int i = n / 2; i;--i) down(i);
    while(m--){
        printf("%d ", h[1]);
        h[1] = h[cnt--];
        down(1);
    }
    return 0;
}


int dist[N], backup[N];
struct Edge{
    int a, b, w;
}edges[M];

void bellman_ford(){
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;

    for (int i = 0; i < k; ++ i){
        memcpy(backup, dist, sizeof dist);

        for (int j = 0; i < m; ++ j){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
}

int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

哈希表

哈希表的作用：把庞大复杂的数据映射到较小的范围。通常的范围是0到$105$或$106$
$h(x)$ 可以把数据进行映射，称为哈希函数。我们可以这么考虑：

$\large{h(x)=x\ \text{mod}\ 10003}$ 。

  • 若干不同的数倍映射成相同的数，称为哈希冲突。

  • 对于冲突的处理：根据处理方法的不同，分为拉链法和开放寻址法。

    • 拉链法

      设 $h(11)=3$ ， $h(23)=3$，这就是一种冲突。我们可以设一个数组 h，也就是哈希的结果。对于每一个结果，建立一个链表。把映射为 $k$ 的所有数 $x$ 都放在 $h[k]$ 这个链表里。

    • 开放寻址法

      设 $h(x)=k$ 。也就是 $x$ 的哈希值为 $k$ 。如果在 $hash[k]$ 的位置已经有元素，持续往后遍历直到找到 $>x$（询问）或为空（插入）为止。注意开放寻址法一般会把数组开到数据范围的 $2-3$ 倍，能提高效率。

时间复杂度 $O(1)$ ，空间复杂度 $O(n)$

image-20230302204426872

2675_a8539bec58-2

2675_a8539bec58-2

2675_ac826b7458-3

2675_9b33804c58-4

2675_a204a13158-5

模板

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
(1) 拉链法
    int h[N], e[N], ne[N], idx;

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

    // 在哈希表中查询某个数是否存在
    bool find(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;
    }

(2) 开放寻址法
    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. AcWing 840. 模拟散列表

C++

拉链法

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
// AcWing 840. 模拟散列表
// 哈希——拉链法
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 3; // 取大于1e5的第一个质数，取质数冲突的概率最小。这个需要事先求一下

// 开一个槽 h
// h存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点int n;
int h[N], e[N], ne[N], idx; //邻接表

// 插入操作
void insert(int x){
    // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++; // 头插法
}

// 存储操作
bool find(int x){
    // 用上面同样的 Hash函数 将x映射到 从 0-1e5 之间的数
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x) 
            return true;
    return false;
}

int main(){
    scanf("%d", &n);
    
    // 将槽先清空 空指针一般用 -1 来表示
    memset(h, -1, sizeof h);
    
    while (n --){
        string op; 
        int x;
        cin >> op >> x;
        if (op == "I") insert(x);
        else{
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    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
// AcWing 840. 模拟散列表
// 哈希——开放地址法
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3; // 取大于数据范围的 2~3倍的第一个质数，取质数冲突的概率最小。这个需要事先求一下
const int null = 0x3f3f3f3f; //规定空指针为 null 0x3f3f3f3f，用于标记当前位置是否已被占
// 之所以使用0x3f3f3f3f标记，因为其在输入数据范围之外

// 开一个槽 h
int n;
int h[N];

// find查找对应位置，如果不存在, 则返回的是应该存储到的位置
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;
}

int main(){
    scanf("%d", &n);
    
    // 初始化，规定空指针为 0x3f3f3f3f
    memset(h, 0x3f, sizeof h);
    
    while (n --){
        string op; 
        int x;
        cin >> op >> x;
        if (op == "I") h[find(x)] = x; // 如果不存在, 则find()返回的是应该存储到的位置
        else{
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

Python

拉链法

str.isalpha()实现的是如果字符串至少有一个字符并且所有字符都是字母则返回 True，否则返回 False

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
# AcWing 840. 模拟散列表
# 哈希——拉链法
def main():
    MAX_N = int(1e5 + 3) # 大于数据范围的最小质数
    # 头节点h初始时全部赋为空指针-1
    h, e, ne = [-1] * MAX_N, [0] * MAX_N, [0] * MAX_N
    idx = 0
    
    # 找插入位置
    def add(x):
        nonlocal idx
        # 先模再加再模，可以让负数映射为自然数
        k = (x % MAX_N + MAX_N) % MAX_N
        e[idx] = x
        ne[idx] = h[k]
        h[k] = idx
        idx += 1
    
    def contains(x):
        k = (x % MAX_N + MAX_N) % MAX_N
        ptr = h[k]
        # 算出映射位置后，进行遍历查找
        while ptr != -1:
            if e[ptr] == x:
                return True
            ptr = ne[ptr]
        return False
    
    n = int(input())
    for _ in range(n):
        # str.isalpha()实现的是如果字符串至少有一个字符并且所有字符都是字母则返回 True，否则返回 False
        op, x = map(lambda x : x if x.isalpha() else int(x), input().split())
        if op == 'I':
            add(x)
        else:
            print("Yes" if contains(x) else "No")
            
if __name__ == "__main__":
    main()

开放寻址法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# AcWing 840. 模拟散列表
# 哈希——开放寻址法
def main():
    MAX_N = int(2e5 + 3) # 大于数据范围2到3倍的最小质数
    hs = [None] * MAX_N # 用None标记是否已被占用
    
    # 开放寻址法，映射后找可以插入的位置（或者找到 x 的位置）
    def find(x):
        pos = (x % MAX_N + MAX_N) % MAX_N
        while hs[pos] != x and hs[pos] != None:
           pos = (pos + 1) % MAX_N
        return pos
    
    n = int(input())
    for _ in range(n):
        # str.isalpha()实现的是如果字符串至少有一个字符并且所有字符都是字母则返回 True，否则返回 False
        op, x = map(lambda x : x if x.isalpha() else int(x), input().split())
        if op == 'I':
            hs[find(x)] = x
        else:
            print("Yes" if hs[find(x)] != None else "No")
            
if __name__ == "__main__":
    main()

字符串哈希

字符串哈希用于快速比较两个子串是否完全相同，复杂度为$O(n)+O(m)$ ，原理本质上是前缀哈希+前缀和。

全称字符串前缀哈希法，把字符串变成一个 p 进制数字（哈希值），实现不同的字符串映射到不同的数字。对形如 $X_1X_2X_3\cdots X_{n-1}X_n$ 的字符串, 采用字符的 ASCII 码乘上 P 的次方来计算哈希值。

映射公式
$$
(X_1 \times P^{n-1} + X_2 \times P^{n-2} + \cdots + X_{n-1} \times P^1 + X_n \times P^0) \bmod Q
$$

注意点：

  1. 任意字符不可以映射成 0，否则会出现不同的字符串都映射成 0 的情况，比如 A,AA,AAA 皆为 0

  2. 冲突问题：通过巧妙设置 P (131 或 13331) , Q $(2^{64})$ 的值，一般可以理解为不产生冲突。

    M=998244353

问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和。

前缀和公式:
$$
h[i+1] = h[i] \times P + s[i], \ i \in [0,n-1]
$$
h 为前缀和数组，s 为字符串数组

区间和公式:
$$
h[l,r] = h[r] - h[l-1] \times P^{r-l+1}
$$

区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，乘上 $P^2$ 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

2675_6024b68258-3

2675_63495d4a58-4

image-202303022040266

2675_5cc1dc5458-2

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

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

1. AcWing 841. 字符串哈希

判断任意两个区间包含的子串是否完全相同

C++

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
// AcWing 841. 字符串哈希
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// 使用场景： 两个字符串的子串是否相同
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突

int n, m;
char str[N];
ULL h[N], p[N]; 
// h[i]前i个字符的hash值
// 用 p 数组存储 p 的幂, p[i] 表示 p 的 i 次幂

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

int main(){
    scanf("%d%d", &n, &m);
    scanf("%s", str);
    
    // 第0位对应位权为1
    p[0] = 1;
    // 与前缀和相同，下标从1开始
    for (int i = 1; i <= n; ++ i){
        // 采用前缀和的方法计算 P进制每位的位权 和 字符串前缀对应的hash值
        p[i] = p[i - 1] * P; 
        h[i] = h[i - 1] * P + str[i - 1]; // 注意这里str的i-1对应于h的i(str下标从0开始)
    }
    
    while (m --){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        
        // 如果子串对应hash值相同，则两字符串完全相同
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

Python

C++ 可以使用 unsigned long long 自动溢出来对 (1 << 64) - 1 取模，Python / Java 需手动取模并注意取模时的括号范围。

内置函数 ord ()用于返回字符的ASCII码用法：ord('C')参数是一个字符，不能是字符串，返回该字符对应的Unicode码

对应的还是有ord()函数的配对函数chr()
chr()的作用是：输入一个十进制或十六进制数字，返回其在Unicode编码中对应的文字或符号

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
# AcWing 841. 字符串哈希
def main():
    P, MOD = 131, (1 << 64)
    # P取131或13331，M取1 << 64，一般不产生冲突
    n, m = map(int, input().split())
    hs, bs = [0] * (n + 1), [1] * (n + 1)
    # 注意由于前缀和从1开始，所以需要多开一位
    # bs[0] 应为1（0次幂）， hs[0] 应为0（避免影响前缀和）
    
    def get(l, r):
        # 取 [L, R] 范围内的字符串哈希值
        # 通过这种方式减去高位（[0, L] 范围内的字符串）的哈希值
        return (hs[r] - hs[l - 1] * bs[r - l + 1]) % MOD
        # 无法自动溢出，需要取模hash
        
    s = input()
    # 所以需要多开一位
    for i in range(1, n + 1):
        # 取模hash
        bs[i] = (bs[i - 1] * P) % MOD
        # ord ()用于返回字符的ASCII码
        hs[i] = (hs[i - 1] * P + ord(s[i - 1])) % MOD
        
    for _ in range(m):
        l1, r1, l2, r2 = map(int, input().split())
        # 哈希值相等则字符串完全相同
        print("Yes" if get(l1, r1) == get(l2, r2) else "No")

if __name__ == "__main__":
    main()