模板(数据结构)

数组模拟单链表

  用数组模拟单链表,可以免去new占用的时间,加快算法执行速度。不过删除节点时会造成内存泄漏,但这一般是工程中考虑的问题,算法题跑时间就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// head 指向头节点, index 表示当前可用数组下标(只增)
int head = -1, v[N], next[N], index = 0;
//插入到头结点后(头插法),头节点是递增的
void add2head(int x){
v[index] = x, ne[index] = head, head = index++;
}
//插入到下标k后
void add(int k, int x){
v[index] = x, ne[index] = ne[k], ne[k] = index++;
}
//删除下标k后一个节点
void remove(int k){
ne[k] = ne[ne[k]];
}

模拟栈和队列

栈只需要一个top指针,队列需要一个头指针一个尾指针。

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
//*********************//栈
int stk[N], top = 0;
//p指向栈顶,插入时先+p再赋值
stk[++top] = x;
//弹出
top--;
//判断空
if(top > 0) ;
//栈顶
stk[top];

//**********************//队列
//队尾插入,队首弹出
int q[N], head = 0, tail = -1;
//插入
q[++tail] = x;
//弹出
head ++;
// 判空
if(head <= tail);
// 取队头
q[head];

//*********************// 循环队列,hh和tt相等时为空,会损失一个容量
// 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];
// 判断队列是否为空
if (hh != tt)

单调栈

给定一个数列,输出每个数左边离它最近的比它小的数,不存在输出-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 1e5+10;

int n ;
int stk[N], tt=0;
int main(){
cin.tie(0);
cin >> n;

for(int i = 0; i < n; i++)
{
int x;
cin >> x;
while( tt && stk[tt] >= x) tt--; //每次入栈前保证栈中之前的节点数值小于当前入栈值
if(tt) cout << stk[tt] << ' ';
else cout << -1 << ' ';

stk[ ++tt ] = x;
}
return 0;
}

堆(以小根堆为例)

定义:完全二叉树,且父节点小于等于左右子节点。

特性:左节点下标(2x),右节点下标(2x+1)。

操作:down(x) : x变大了,那么需要往下调整。up(x) :x变小了,需要往上调整。

1619358192132

建堆(O(n)做法)

从$n / 2$处,即倒数第2层开始,往跟节点遍历,对这些节点执行down操作。最后一层经历过上层的down操作一定是满足堆定义的。O(n) 证明如下:

倒数第二层有$ n / 4$个节点,则最多的操作的次数为:

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 heap[N], sz, m;

void down(int idx) { // 往下调整需要与两个子节点比较,因此比较两次
int t = idx;
if (2 * idx <= sz && heap[2 * idx] < heap[t]) t = 2 * idx;
if (2 * idx + 1 <= sz && heap[2 * idx + 1] < heap[t]) t = 2 * idx + 1;
if (idx != t) {
swap(heap[t], heap[idx]);
down(t);
}
}

// 建堆,从后往前开始下调整即可
for (int i = sz / 2; i != 0; -- i) down(i);



void up(int idx) { // 往上调整只需要与父节点比较即可
while (idx / 2 && heap[idx / 2] > heap[idx]) {
swap(heap[idx / 2], heap[u]);
idx /= 2;
}
}


// 堆弹出的时候,将堆顶弹出,末尾放入堆顶,执行down操作。

并查集

朴素并查集

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
// 并查集模板题,主要功能是合并两个集合、查找两个元素是否属于同一集合
// 主要想法是建立一个集合数字的哈希表,表中保存当前数字的祖宗节点,若祖宗节点相同,表示它们是一个集合。

#include <iostream>

using namespace std;

const int N = 1e5+10;

int p[N];

int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);// 使用p[x]是为了合并集合时更改祖宗节点
return p[x];
}

int main(){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++) p[i] = i; // 1. 并查集需要初始化自己为根节点

while(m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);

if(op[0] == 'M') p[find(a)] = find(b); // 2. 合并操作,将a的祖宗节点的祖宗节点设为b的祖宗节点
else
{
if(find(a) == find(b)) printf("Yes\n"); // 查找操作
else printf("No\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
#include <iostream>

using namespace std;

const int N = 1e5+10;
int p[N], num[N];
int n, m;

int find(int x){
if(p[x] != x) p[x] = find(p[x]); // 使用p[x]是为了合并集合时更改祖宗节点 , 路径压缩
return p[x];
}

int main(){
cin >> n >> m;
string op;
int a, b;

for(int i = 1; i <= n; i ++){
p[i] = i;
num[i] = 1;
}

while(m --){
cin >> op;

if(op == "C"){ // 合并操作
cin >> a >> b;
int x = find(a), y = find(b);
if(x != y){
p[x] = y;
num[y] += num[x]; // b设为根节点
}
}
else if(op == "Q1"){ // 查询是否在同一集合
cin >> a >> b;
find(a)==find(b) ? puts("Yes") : puts("No");
}
else{ // 查询数量
cin >> a;
printf("%d\n", num[find(a)]);
}
}
}

STL

  • priority_queue与set的区别

其中优先队列是由堆实现的,适用于每次只取前面的数的情况。而set是由BST实现的,可以快速查询某个数是否在set中。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
ector, 变长数组,倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算,按字典序

pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字(字典序)

string,字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标,(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素

priority_queue, 优先队列,默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式:priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素

deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]

set, map, multiset, multimap, 基于平衡二叉树(红黑树),动态维护有序序列

setmap的公共操作:

size()
empty()
clear()
begin()/end()
++, -- 迭代器,返回前驱和后继,时间复杂度 O(logn)

setmap的区别:
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x,删除所有x O(k + logn)
(2) 输入一个迭代器,删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似,增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound(), 迭代器的++,--

bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]

count() 返回有多少个1

any() 判断是否至少有一个1
none() 判断是否全为0

set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反