数据结构初步

博主： RearWaves
发布时间：2023 年 04 月 16 日
305 次浏览
暂无评论
9629字数
分类：算法设计

# 数据结构1

> **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分.
> 
> 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢.
> 
> 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱).

# 1 链表与邻接表: 树与图的存储

## 1.1 单链表

作用: 邻接表, 存储图和树.

$$
head \to [0]:3\to [1]:5\to [2]:7 \to [3]:9 \to [-1]:\varnothing
$$

e[0]=3,  e[1]=5,  e[2]=7,  e[3]=9;

ne[0]=1, ne[1]=2, ne[2]=3, ne[3]=-1;

### [826. 单链表](https://www.acwing.com/problem/content/828/)

实现一个单链表, 链表初始为空, 支持三种操作:

1. 向链表头插入一个数;
2. 删除第 k 个插入的数后面的数; (删除下标为k-1的数)
3. 在第 k 个插入的数后插入一个数. (在下标为k-1的数后插入一个数)

现在要对该链表进行 M 次操作, 进行完所有操作后, 从头到尾输出整个链表.

输入格式: 整数 M , 表示操作次数.

H x, 表示向链表头插入一个数 x . D k, 表示删除第 k 个插入的数后面的数(当 k 为 0 时, 表示删除头结点). I k x, 表示在第 k 个插入的数后面插入一个数 x (此操作中 k 均大于 0 ).

输出格式: 共一行, 将整个链表从头到尾输出.

```c++
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;	//为存储0号节点做准备
}
//将x插入到头节点
void add_to_head(int x) {
	e[idx] = x, ne[idx] = head, head = idx++;
}
//将x插入到下标为k的点的后面
void add(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 m;
	cin >> m;
	init();
	while (m--) {
		int k, x;
		char op;
		cin >> op;
		if (op == 'H') {
			cin >> x;
			add_to_head(x);
		}
		else if (op == 'D') {
			cin >> k;
			if (!k) head = ne[head];
			else remove(k - 1);
		}
		else {
			cin >> k >> x;
			add(k - 1, x);
		}
	}
	for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
	cout << endl;
	return 0;
}
```

## 1.2 双链表

作用: 优化某些问题.

### [827. 双链表](https://www.acwing.com/problem/content/829/)

实现一个双链表, 双链表初始为空, 支持 5 种操作:

1. 在最左侧插入一个数;
2. 在最右侧插入一个数;
3. 将第 k 个插入的数删除; (下标为k+1)
4. 在第 k 个插入的数左侧插入一个数;
5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作, 进行完所有操作后, 从左到右输出整个链表.

```c++
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int m;
int e[N], l[N], r[N], idx;
//其中l[N]表示该点左边的节点,r[N]表示右边的节点
//初始化
void init() {
	//0表示左端点,1表示右端点
	r[0] = 1, l[1] = 0;
	idx = 2;
}
//在下标为k的点的右边插入点x
void add(int k, int x) {
	e[idx] = x;
	r[idx] = r[k], l[idx] = k;
	l[r[k]] = idx, r[k] = idx++;
}
//在下表为k的点的左边插入点x
//add(l[k], x)
//删除下标为k的点
void remove(int k) {
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}
int main()
{
	cin >> m;
	init();
	while (m--)
	{
		string op;
		cin >> op;
		int k, x;
		if (op == "L")
		{
			cin >> x;
			add(0, x);
		}
		else if (op == "R")
		{
			cin >> x;
			add(l[1], x);
		}
		else if (op == "D")
		{
			cin >> k;
			remove(k + 1);
		}
		else if (op == "IL")
		{
			cin >> k >> x;
			add(l[k + 1], x);
		}
		else
		{
			cin >> k >> x;
			add(k + 1, x);
		}
	}
	for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
	cout << endl;
	return 0;
}
```

# 2 栈与队列: 单调队列、单调栈

## 2.1 栈

**模板:**

```c++
const int N = 1e5 + 10;
//定义栈
int stk[N], tt;
//插入
stk[++tt] = x;
//弹出
tt--;
//判断栈是否为空
if (tt > 0) not empty;
else empty;
//取栈顶元素
stk[tt];
```

### [828. 模拟栈](https://www.acwing.com/problem/content/830/)

实现一个栈, 栈初始为空, 支持四种操作:

1. `push x` – 向栈顶插入一个数 xx;
2. `pop` – 从栈顶弹出一个数;
3. `empty` – 判断栈是否为空;
4. `query` – 查询栈顶元素.

现在要对栈进行 M 个操作, 其中的每个操作 3 和操作 4 都要输出相应的结果.

```c++
const int N = 1e5 + 10;
int m, x;
string op;
int stk[N], tt;
int main() {
	scanf("%d", &m);
	while (m--) {
		cin >> op;
		if (op == "push") {
			scanf("%d", &x);
			stk[++tt] = x;
		}
		else if (op == "pop") tt--;
		else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;
		else if (op == "query") cout << stk[tt] << endl;
	}
	return 0;
}
```

### [3302. 表达式求值](https://www.acwing.com/problem/content/3305/)

给定一个表达式, 其中运算符仅包含 `+,-,*,/`(加 减 乘 整除), 可能包含括号, 请你求出表达式的最终值.

**注意: **

> - 数据保证给定的表达式合法.
> - 题目保证符号 `-` 只作为减号出现, 不会作为负号出现, 例如, `-1+2`,`(2+2)*(-(1+1)+2)` 之类表达式均不会出现.
> - 题目保证表达式中所有数字均为正整数.
> - 题目保证表达式在中间计算过程以及结果中, 均不超过 $2^{31}−1$.
> - 题目中的整除是指向 0 取整, 也就是说对于大于 0 的结果向下取整, 例如 5/3=1, 对于小于 0 的结果向上取整, 例如 5/(1−4)=−1.
> - C++和Java中的整除默认是向零取整; Python中的整除`//`默认向下取整, 因此Python的`eval()`函数中的整除也是向下取整, 在本题中不能直接使用.

**中序遍历表达式树的计算过程:**

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

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

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

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

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

![8.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/2401_ee9fc12c25-8.png)

```c++
stack<int> num;
stack<char> op;
void eval() {
	auto b = num.top(); num.pop();	//第二个操作数
	auto a = num.top(); num.pop();	//第一个操作数
	auto c = op.top(); op.pop();	//运算符
	int x;
	if (c == '+') x = a + b;
	else if (c == '-') x = a - b;
	else if (c == '*') x = a * b;
	else x = a / b;
	num.push(x);
}
int main()
{
	unordered_map<char, int> pr{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };
	string str;
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		auto c = str[i];
		if (isdigit(c)) {
			int x = 0, j = i;	//计算数字
			while (j < str.size() && isdigit(str[j]))
				x = x * 10 + str[j++] - '0';
			i = j - 1;
			num.push(x);	//数字入栈
		}
		//括号特殊, 遇到左括号直接入栈, 遇到右括号计算括号里面的
		else if (c == '(') op.push(c);
		else if (c == ')') {
			while (op.top() != '(') eval();
			op.pop();
		}
		//如果当前运算符优先级比上一运算符高, 说明是往下走, 则只需将运算符压栈
		//如果当前运算符优先级比上一运算符低, 说明是往上走, 则需要一直计算上一运算符直至当前运算符优先级比上一运算符高
		else {
			while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
			op.push(c);	
		}
	}
	while (op.size()) eval();	//剩余的进行计算
	cout << num.top() << endl;
	return 0;
}
```

## 2.2 队列

**模板:**

```c++
const int N = 1e5 + 10;
//定义队列
int q[N], hh, tt = -1;
//在队尾插入元素,在队头弹出元素
//插入
q[++tt] = x;
//弹出
hh++;
//判断队列是否为空
if (hh <= tt) not empty;
else empty;
//取出队头元素
q[hh];
```

### [829. 模拟队列](https://www.acwing.com/problem/content/831/)

实现一个队列, 队列初始为空, 支持四种操作:

1. `push x` – 向队尾插入一个数 xx;
2. `pop` – 从队头弹出一个数;
3. `empty` – 判断队列是否为空;
4. `query` – 查询队头元素.

现在要对队列进行 M 个操作, 其中的每个操作 3 和操作 4 都要输出相应的结果.

```c++
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int m, x;
string op;
int q[N], hh, tt = -1;
int main() {
	scanf("%d", &m);
	while (m--) {
		cin >> op;
		if (op == "push") {
			scanf("%d", &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;
}
```

## 2.3 单调栈

常见题型: 给出一个序列, 找出每个数左边(或右边)满足某个性质最近的数.

### [830. 单调栈](https://www.acwing.com/problem/content/832/)

给定一个长度为 N 的整数数列, 输出每个数左边第一个比它小的数, 如果不存在则输出 −1.

输入格式:第一行包含整数 N, 表示数列长度. 第二行包含 N 个整数, 表示整数数列.

输出格式:共一行, 包含 N 个整数, 其中第 i 个数表示第 i 个数的左边第一个比它小的数, 如果不存在则输出 −1.

> 用单调递增栈, 当该元素可以入栈的时候, 栈顶元素就是它左侧第一个比它小的元素. 以: 3 4 2 7 5 为例, 过程如下:

![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/data_structure/20201211221031165.gif)

```c++
const int N = 1e5 + 10;
int n;
int stk[N], tt;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
        //如果栈不空且栈顶元素大于当前待入栈元素则出栈
		while (tt && stk[tt] >= x) tt--;
        //如果栈为空,则该元素前没有比该元素更小的值
		if (!tt) printf("-1 ");
        //栈顶匀速即为所求解
		else printf("%d ", stk[tt]);
		stk[++tt] = x;
	}
	return 0;
}
```

## 2.4 单调队列

常见题型: 求滑动窗口的最大值最小值.

### [154. 滑动窗口](https://www.acwing.com/problem/content/156/)

给定一个大小为 $n\le 10^6$ 的数组. 有一个大小为 k 的滑动窗口, 它从数组的最左边移动到最右边. 你只能在窗口中看到 k 个数字. 每次滑动窗口向右移动一个位置.

以下是一个例子: 该数组为 `[1 3 -1 -3 5 3 6 7]`, k 为 3.

| 窗口位置            | 最小值 | 最大值 |
| :------------------ | :----- | :----- |
| [1 3 -1] -3 5 3 6 7 | -1     | 3      |
| 1 [3 -1 -3] 5 3 6 7 | -3     | 3      |
| 1 3 [-1 -3 5] 3 6 7 | -3     | 5      |
| 1 3 -1 [-3 5 3] 6 7 | -3     | 5      |
| 1 3 -1 -3 [5 3 6] 7 | 3      | 6      |
| 1 3 -1 -3 5 [3 6 7] | 3      | 7      |

你的任务是确定滑动窗口位于每个位置时, 窗口中的最大值和最小值.

![滑动窗口.PNG](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_0923cf569c-滑动窗口.png)

```c++
int n, k;
int a[N], q[N];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	//初始化队列
	int hh = 0, tt = -1;
	for (int i = 0; i < n; i++) {
		//判断队头是否已经滑出窗口(q[hh]-i<=k),确保滑动窗口数据
		if (hh <= tt && i - k + 1 > q[hh]) hh++;
		//把队列里所有比a[i]大的数都踢掉,因为他们不可能成为答案
		while (hh <= tt && a[q[tt]] >= a[i]) tt--;
		q[++tt]=i;
		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;
}
```

# 3 KMP算法

最长公共前后缀长度数组next[j]含义是: P[j] 前面的字符串的最长公共前后缀长度.

![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/data_structure/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQzMzk0NDc=,size_16,color_FFFFFF,t_70.png)

P=“ababf” 的最长公共前后缀:

P[0] 前面没有字符串, 所以最长公共前后缀长度为 0.

P[1] 前面的字符串为: a, a没有前后缀(前后缀长度要小于字符串长度). 最长公共前后缀长度为 0.

P[2] 前面的字符串为: ab, 它的前缀为: a, 后缀为b. 前缀不等于后缀, 所以没有公共前后缀, 最长公共前后缀长度为 0.

P[3] 前面的字符串为: aba, aba 的前缀有: a, ab,  后缀有: a, ba. 因为 ab 不等于 ba, 所以最长公共前后缀为 a, 最长公共前后缀长度为 1.

P[4] 前面的字符串为: abab, abab 的前缀有: a, ab, aba, 后缀有: a, ab, bab. 最长公共前后缀为 ab, 长度为 2.

![Hongda_2022-11-21_15-56-17](https://www.rearwaves.com/usr/assets/algorithm/data_structure/Hongda_2022-11-21_15-56-17.png)

**next数组的具体求法:**

1. 当P[ next[i-1] ] 与 P[i - 1] 是同一个字母的时候, P[i] = P[i-1] + 1;
   
   举例:next[8] = 3, 即 P[0 ~ 2] 与 P[5 ~ 7] 相同, 又因为 P[ next[i-1] ] ( next[i - 1] = 3 ) 与 P[i - 1] (i - 1 = 8) 是相同字母, 所以P[0 ~ 3] 与 P[5 ~ 8] 相同.
   
   ![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/data_structure/20201217204219739.png)
2. 当 P[ next[i - 1] ] 与 P[i - 1] 不同的时候, 可以这样求 next[i]:
   
   令 j 等于 next[i - 1], 如果 P[j] 与 P[i -1] 不同, 一直通过 j = next[j] 更新 j 的值, 直到遇到 P[j] 与 P[i - 1] 相同, P[i] 就等于 j + 1. 如果 j 的值更新到了 0 , 就不用继续更新了, 这时候: 如果 P[0] 与 P[i - 1] 相同,  next[i] 就等于 1; 如果 P[0] 与 P[i - 1] 不同, next[i] 就等于 0.
   
   ![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/data_structure/20201217204236419.png)

### [831. KMP字符串](https://www.acwing.com/problem/content/833/)

给定一个字符串 S, 以及一个模式串 P, 所有字符串中只包含大小写英文字母以及阿拉伯数字.

模式串 P 在字符串 S 中多次作为子串出现.

求出模式串 P 在字符串 S 中所有出现的位置的起始下标.

输入格式:字符串 P 的长度,字符串 P;字符串 SS 的长度,字符串 S.

输出格式:所有出现位置的起始下标(下标从 0 开始计数), 整数之间用空格隔开.

```c++
const int N = 1e6 + 5;
int n, m;
char p[N], s[N];
int ne[N];
int main() {
	cin >> n >> p + 1 >> m >> s + 1;	//字符串下标从1开始
	//求next数组
	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;
	}
	//进行匹配,其中i, j分别为s和p字符串的指针
	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];
		}
	}
}
```

# 4 Tire树

用来高效的存储和查找字符串集合的数据结构.存储方法: 如图所示,最后需要在每一个单词的结尾加上一个标记.

![Trie1.PNG](https://www.rearwaves.com/usr/assets/algorithm/data_structure/31041_aa11ff2cad-Trie1.png)

![Hongda_2022-11-22_11-34-04](https://www.rearwaves.com/usr/assets/algorithm/data_structure/Hongda_2022-11-22_11-34-04.png)

### [835. Trie字符串统计](https://www.acwing.com/problem/content/837/)

维护一个字符串集合, 支持两种操作:

1. `I x` 向集合中插入一个字符串 x;
2. `Q x` 询问一个字符串在集合中出现了多少次.

共有 N 个操作, 字符串仅包含小写英文字母.

**解题思路:**

![Trie2.PNG](https://www.rearwaves.com/usr/assets/algorithm/data_structure/31041_aed49a42ad-Trie2.png)

```c++
const int N = 1e5 + 10;
//son[p][u]表示p节点的u字母对应的节点编号
int son[N][26], cnt[N], idx;
char str[N];
//插入一个字符串
void insert(char str[]) {
	int p = 0;
	//字符串的结尾为'\0', str[i]判断是否读到字符串结尾
	for (int i = 0; str[i]; i++) {
		int u = str[i] - 'a';	//字母对应的编号0~25
		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;
	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;
}
```

### [143. 最大异或对](https://www.acwing.com/problem/content/145/)

在给定的 N 个整数A1, A2...AN 中选出两个进行 xor(异或) 运算, 得到的结果最大是多少?

**解题思路:**

首先`son[N][x]`这是个二维数组.

第一维N是题目给的数据范围, 像在trie树中的模板题当中N为字符串的总长度(这里的总长度为所有的字符串的长度加起来), 在本题中N需要自己计算, 最大为N*31(其实根本达不到这么大, 举个简单的例子假设用0和1编码, 按照前面的计算最大的方法应该是4乘2=8但其实只有6个结点).

第二维x代表着儿子结点的可能性有多少, 模板题中是字符串, 而题目本身又限定了均为小写字母所以只有26种可能性, 在本题中下一位只有0或者1两种情况所以为2. 而这个二维数组本身存的是当前结点的下标, 就是N喽, 所以总结的话`son[N][x]`存的就是第N的结点的x儿子的下标是多少, 然后idx就是第一个可以用的下标.

```c++
const int N = 1e5 + 10, 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 u = x >> i & 1;		//取二进制数的某一位的值
		if (!son[p][u]) son[p][u] = ++idx;	// 如果下标为p的点的u(0或1)这个儿子不存在, 那就创建
		p = son[p][u];
	}
}
int search(int x) {
	int p = 0, res = 0;
	for (int i = 30; i >= 0; i--) {
		int u = x >> i & 1;
		if (son[p][!u]) {
			res += 1 << i;	//如果找到了与当前位不一样的,异或的结果是1
			p = son[p][!u];
		}
		else p = son[p][u];	//如果没找到,异或的结果为0,不需要处理
	}
	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, search(a[i]));
	printf("%d\n", res);
	return 0;
}
```

# 5 并查集

快速地处理以下问题:

1、将两个集合合并

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

对于暴力解法:

```c++
belong[x]=a;//x元素属于集合a
//查询是否在同一个集合操作
if(belong[x]==belong[y]) //O(1)
//合并两个集合
//需要一个一个修改每个元素的编号, 时间复杂度太高
```

并查集可以在近乎O(1)的复杂度内解决这些问题.

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

问题1: 如何判断树根: `if(p[x]==x)`;

问题2: 如何求x的集合编号: `while(p[x]!=x) x=p[x];`;

问题3: 如何合并两个集合: px是x的集合编号, py是y的集合编号, `p[x]=y`.

**查找 + 路径压缩:**

举例:针对 x = 1

> - find(1) p[1] = 2  p[1] = find(2)
> - find(2) p[2] = 3  p[2] = find(3)
> - find(3) p[3] = 4  p[3] = find(4)
> - find(4) p[4] = 4  将p[4]返回
> - 退到上一层 find(3) p[3] = 4  p[3] = 4 将p[3]返回
> - 退到上一层 find(2) p[2] = 3  p[2] = 4 将p[2]返回
> - 退到上一层 find(1) p[1] = 2  p[1] = 4 将p[1]返回

![13.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/64616_94ca39eb65-13.png)

**合并操作:**

合并1,  5: find(1) = 3 find(5) = 4; p[find(1)] = find(5) –> p[3] = 4.

![14.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/64616_1c43d0af65-14.png)

![15.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/64616_db117f1f65-15.png)

### [836. 合并集合](https://www.acwing.com/problem/content/838/)

一共有 n 个数, 编号是 1∼n, 最开始每个数各自在一个集合中. 现在要进行 m 个操作, 操作共有两种:

1. `M a b`, 将编号为 a 和 b 的两个数所在的集合合并, 如果两个数已经在同一个集合中, 则忽略这个操作;
2. `Q a b`, 询问编号为 a 和 b 的两个数是否在同一个集合中;

```c++
int n, m;
int p[N];
//返回x所在集合的编号(祖宗节点)+路径压缩
int find(int x) {
	//祖先节点的父节点是自己本身.如果p[x]不为根节点,让父节点等于祖宗节点
	if (p[x] != x) p[x] = find(p[x]);
	//返回父节点
	return p[x];
}
int main() {
	scanf("%d%d", &n, &m);
    //初始化,将当前数据的父节点指向自己
	for (int i = 1; i <= n; i++) p[i] = i;
	while (m--) {
		char op[2];
		int a, b;
		scanf("%s%d%d", op, &a, &b);
		//合并操作:让a的祖宗节点的父亲=b的祖宗节点
		if (op[0] == 'M') p[find(a)] = find(b);
		else puts((find(a) == find(b)) ? "Yes" : "No");
	}
	return 0;
}
```

### [837. 连通块中点的数量](https://www.acwing.com/problem/content/839/)

给定一个包含 n 个点(编号为 1∼n)的无向图, 初始时图中没有边. 现在要进行 m 个操作, 操作共有三种:

1. `C a b`, 在点 a 和点 b 之间连一条边, a 和 b 可能相等;
2. `Q1 a b`, 询问点 a 和点 b 是否在同一个连通块中, a 和 b 可能相等;
3. `Q2 a`, 询问点 a 所在连通块中点的数量;

```c++
int n, m;
int p[N], s[N];	//根节点的size才有意义
//返回x所在集合的编号(祖宗节点)+路径压缩
int find(int x) {
	//祖先节点的父节点是自己本身.如果p[x]不为根节点,让父节点等于祖宗节点
	if (p[x] != x) p[x] = find(p[x]);
	//返回父节点
	return p[x];
}
int main() {
	scanf("%d%d", &n, &m);
	//初始化,将当前数据的父节点指向自己
	for (int i = 1; i <= n; i++) {
		p[i] = i;
		s[i] = 1;
	}
	while (m--) {
		char op[2];
		int a, b;
		scanf("%s", op);
		//合并操作:让a的祖宗节点的父亲=b的祖宗节点
		if (op[0] == 'C') {
			scanf("%d%d", &a, &b);
			if (find(a) == find(b)) continue;
			s[find(b)] += s[find(a)];
			p[find(a)] = find(b);
		}
		else if (op[1] == '1') {
			scanf("%d%d", &a, &b);
			puts((find(a) == find(b)) ? "Yes" : "No");
		}
		else {
			scanf("%d", &a);
			printf("%d\n", s[find(a)]);
		}
	}
	return 0;
}
```

### [240. 食物链](https://www.acwing.com/problem/content/242/)

动物王国中有三类动物A,B,C, 这三类动物的食物链构成了有趣的环形. A吃B, B吃C, C吃A. 现有N个动物, 以1～N编号. 每个动物都是A,B,C中的一种, 但是我们并不知道它到底是哪一种.

有人用两种说法对这N个动物所构成的食物链关系进行描述:第一种说法是`1 X Y`, 表示X和Y是同类. 第二种说法是`2 X Y`, 表示X吃Y.

此人对N个动物, 用上述两种说法, 一句接一句地说出K句话, 这K句话有的是真的, 有的是假的. 当一句话满足下列三条之一时, 这句话就是假话, 否则就是真话. 1.当前的话与前面的某些真的话冲突, 就是假话;2.当前的话中X或Y比N大, 就是假话;3.当前的话表示X吃X, 就是假话.

你的任务是根据给定的N和K句话, 输出假话的总数.

使用带权重的并查集:在一棵树上,当动物x和动物y的距离%3等于1时,说明x捕食y;当动物x和动物y的距离%3等于2时,说明y捕食x也可以说y是x的天敌;当动物x和动物y的距离%3等于0时,说明x和y是同类.

```c++
const int N = 1e5 + 10;
int n, m;
int p[N], d[N];	//每个节点的父节点和该节点到根节点的距离
int find(int x) {
	if (p[x] != x) {	//如果该节点的父节点不是根节点
		int t = find(p[x]);	//令t为x的根节点
		d[x] += d[p[x]];	//该节点的距离值是该节点到父节点的距离+父节点到根节点的距离
		p[x] = t;	//路径压缩,该节点指向根节点
	}
	return p[x];
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) p[i] = i;
	int res = 0;
	while (m--) {
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		//当前的话中X或Y比N大, 就是假话
		if (x > n || y > n) res++;
		else {
			int px = find(x), py = find(y);
			if (t == 1) {
				//如果px和py在同一棵树,并且是捕食关系
				if (px == py && (d[x] - d[y]) % 3) res++;
				else if (px != py) {
					p[px] = py;		//让y的父节点成为x的父节点
					d[px] = d[y] - d[x];	//更新距离关系
				}
			}
			else {
				//如果px和py在同一棵树,并且是同类关系
				if (px == py && (d[x] - d[y] - 1) % 3) res++;
				else if (px != py) {
					p[px] = py;		//让y的父节点成为x的父节点
					d[px] = d[y] + 1 - d[x];	//更新距离关系
				}
			}
		}
	}
	printf("%d\n", res);
	return 0;
}
```

# 6 堆

手写堆主要解决以下问题:

1. 插入一个数: heap[++size]=x;up(size);
2. 求集合当中的最小值: heap[1];
3. 删除最小值: heap[1]=heap[size];size--;down(1);
4. 删除任意一个元素: heap[k]=heap[size];size--;down(k);up(k);//down和up只会执行一次;
5. 修改任意一个元素: heap[k]=x;down(k);up(k);

堆是具有以下性质的完全二叉树: 每个结点的值都大于或等于其左右孩子结点的值,  这种情况称为大顶堆, 注意:没有要求结点的左孩子的值和右孩子的值的大小关系. 每个结点的值都小于或等于其左右孩子结点的值,  这种情况称为小顶堆.

![20210320153023354.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_3b2cf2fbe9-20210320153023354.png)

**构造:**

最后一个非叶子结点开始(也就是下面的 6 结点), 从左至右, 从下至上进行调整. 6 有两个儿子: 5 和 9, 这三个值中 9 最大. 6 和 9 交换.

![20210320153221152.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_016ea910e9-20210320153221152.png)

因为 6 和 9 交换了, 递归处理现在保存 6 的那个节点, 发现它没有儿子, 停止递归.

找到第二个非叶节点4, 由于[4,9,8]中9元素最大, 4 和 9 交换.

![20210320153251438.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_c90da89de9-20210320153251438.png)

因为 4 和 9 交换了, 递归处理现在保存 4 的那个节点: 找到它的两个儿子: 5, 6, 其中 6 最大, 交换 4 和 6.

![20210320153330130.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_8db80884e9-20210320153330130.png)

然后继续递归处理, 发现现在保存4 的节点没有儿子, 停止.

此时, 我们就将一个无序序列构造成了一个大顶堆.

### [838. 堆排序](https://www.acwing.com/problem/content/840/)

输入一个长度为 n 的整数数列, 从小到大输出前 m 小的数.

**解题思路:**

> 将堆顶元素与末尾元素进行交换, 使末尾元素最大. 然后继续调整堆, 再将堆顶元素与末尾元素交换, 得到第二大元素. 如此反复进行交换、重建、交换. 如下图:

将堆顶元素 9 和末尾元素 4 进行交换.

![20210320153411240.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_e37e2eb5e9-20210320153411240.png)

重新调整结构(规则如上), 使其继续满足堆定义.

![20210320153445908.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_074da01de9-20210320153445908.png)

再将堆顶元素 8 与末尾元素 5 进行交换, 得到第二大元素 8.

![20210320153510654.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_1c1ea166e9-20210320153510654.png)

后续过程, 继续进行调整, 交换, 如此反复进行, 最终使得整个序列有序.

```c++
const int N = 1e5 + 10;
int n, m;
int h[N], s;	//size为堆中的元素个数

void down(int u) {
	//把该节点及其左右儿子的最小值赋值给t
	int t = u;
    //有左儿子, 并且左儿子比t节点的值小, 更新t
	if (u * 2 <= s && h[u * 2] < h[t]) t = u * 2;
    //有右儿子, 并且右儿子比t节点的值小, 更新t
	if (u * 2+1 <= s && h[u * 2+1] < h[t]) t = u * 2+1;
	//将最小值换到父节点的位置
	if (u != t) {
		swap(h[u], h[t]);
		down(t);	//递归处理
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
	s = n;
	//O(n)的建堆方式,从第一个非叶节点开始, 从右到左, 从下到上处理每个节点
	for (int i = n / 2; i; i--) down(i);
	while (m--) {
		printf("%d ", h[1]);	//输出堆顶元素
		h[1] = h[s];	//用最后一个元素覆盖堆顶
		s--;
		down(1);
	}
	return 0;
}
```

### [839. 模拟堆](https://www.acwing.com/problem/content/841/)

维护一个集合, 初始时集合为空, 支持如下几种操作:

1. `I x`, 插入一个数 x;
2. `PM`, 输出当前集合中的最小值;
3. `DM`, 删除当前集合中的最小值(数据保证此时的最小值唯一);
4. `D k`, 删除第 k 个插入的数; (需要额外开数组存储)
5. `C k x`, 修改第 k 个插入的数, 将其变为 x;

现在要进行 N 次操作, 对于所有第 2 个操作, 输出当前集合的最小值.

> 关于ph[N]与hp[N]: h[x] 表示树中位置 x 的元素; ph[k] = x 表示第 k 个插入的元素在树中存放的位置 x.
> 
> 此时如果要交换 ph 中的两个元素需要知道树中位置 x 是第几个被插入的, 于是便引入了数组 hp: hp[x] = k 表示树中位置 x 存放的为第 k 个插入的元素.

![位置指针](https://www.rearwaves.com/usr/assets/algorithm/data_structure/11802_daec3b5c5d-位置指针.png)

```c++
const int N = 1e5 + 10;
int n, m;
//ph[k]存第k插入的数在堆中的下标, hp[i]存堆中的i号点是第几个插入点
int h[N], ph[N], hp[N], s;
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) {
	//把该节点及其左右儿子的最小值赋值给t
	int t = u;
	if (u * 2 <= s && h[u * 2] < h[t]) t = u * 2;
	if (u * 2 + 1 <= s && 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 / 2] > h[u]) {
		heap_swap(u / 2, u);
		u /= 2;
	}
}
int main() {
	scanf("%d", &n);
    while (n--) {
        char op[10];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I")) {
            scanf("%d", &x);
            s++, m++;
            ph[m] = s, hp[s] = m;
            h[s] = x;
            up(s);
        }
        else if (!strcmp(op, "PM")) {
            printf("%d\n", h[1]);
        }
        else if (!strcmp(op, "DM")) {
            heap_swap(1, s);
            s--;
            down(1);
        }
        else if (!strcmp(op, "D")) {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, s);
            s--;
            down(k); up(k);
        }
        else {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}
```

# 7 哈希表

## 7.1 哈希表

哈希表的作用: 把庞大复杂的数据映射到较小的范围. h(x) 可以把数据进行映射, 成为哈希函数.

若干不同的数倍映射成相同的数, 称为哈希冲突. 对于冲突, 我们有两种处理方法. 根据处理方法的不同, 分为拉链法和开放寻址法.

开放寻址法: 如果看到一个坑里有人就往前找没人的坑; 拉链法: 认准一个坑无论有没有人都在厕所门口排队.

> 在算法竞赛中, 我们常常需要用到设置一个常量用来代表“无穷大”.
> 
> 比如对于int类型的数, 有的人会采用INT_MAX, 即0x7fffffff作为无穷大. 但是以INT_MAX为无穷大常常面临一个问题, 即加一个其他的数会溢出.
> 
> 而这种情况在动态规划, 或者其他一些递推的算法中常常出现, 很有可能导致算法出问题.
> 
> 所以在算法竞赛中, 我们常采用0x3f3f3f3f来作为无穷大. 0x3f3f3f3f主要有如下好处:
> 
> 0x3f3f3f3f的十进制为1061109567, 和INT_MAX一个数量级, 即10^9数量级, 而一般场合下的数据都是小于10^9的.
> 0x3f3f3f3f * 2 = 2122219134, 无穷大相加依然不会溢出.
> 可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f, 因为这个数的每个字节都是0x3f.

### [840. 模拟散列表](https://www.acwing.com/problem/content/842/)

维护一个集合, 支持如下几种操作:

1. `I x`, 插入一个数 x;
2. `Q x`, 询问数 x 是否在集合中出现过;

现在要进行 N 次操作, 对于每个询问操作输出对应的结果.

**方法一: 开放寻址法**

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

```c++
//N最好取数据范围的2-3倍,且当N为质数时哈希冲突较小
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
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() {
	memset(h, 0x3f, sizeof h);
	int n;
	scanf("%d", &n);
	while (n--) {
		char op[2];
		int x;
		scanf("%s%d", op, &x);
		if (*op == 'I') h[find(x)] = x;
		else {
			if (h[find(x)] == null) puts("No");
			else puts("Yes");
		}
	}
	return 0;
}
```

**方法二: 拉链法**

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

```c++
const int N = 100003;
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;
}
int main() {
	int n;
	scanf("%d", &n);
	memset(h, -1, sizeof h);
	while (n--) {
		char op[2];
		int x;
		scanf("%s%d", op, &x);
		if (*op == 'I') insert(x);
		else {
			if (find(x)) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}
```

## 7.2 字符串哈希

字符串哈希时间复杂度: O(n)+O(m). 全称字符串前缀哈希法, 把字符串变成一个p进制数字(哈希值), 实现不同的字符串映射到不同的数字.

对形如 $X_1X_2X_3⋯X_{n−1}X_n$ 的字符串,采用字符的 ascii 码乘上 P 的次方来计算哈希值.

映射公式 $(X_1×P^{n−1}+X_2×P^{n−2}+⋯+X_{n−1}×P^1+X_n×P^0)mod\ Q$

注意点:

1. 任意字符不可以映射成0, 否则会出现不同的字符串都映射成0的情况, 比如A,AA,AAA皆为0
2. 冲突问题: 通过巧妙设置P (131 或 13331) , Q ($2^{64}$)的值, 一般可以理解为不产生冲突.

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

前缀和公式 $h[i+1]=h[i]×P+s[i] \ i∈[0,n−1]$ h为前缀和数组, s为字符串数组;

区间和公式 $h[l,r]=h[r]−h[l−1]×P^{r−l+1}$.

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

### [841. 字符串哈希](https://www.acwing.com/problem/content/843/)

给定一个长度为 n 的字符串, 再给定 m 个询问, 每个询问包含四个整数 l1,r1,l2,r2l, 请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同.

字符串中只包含大小写英文字母和数字.

```c++
typedef unsigned long long ull;
const int N = 1e5 + 10, P = 131;
int n, m;
char str[N];
ull h[N], p[N];	//h[i]存放字符串的前缀值,p[i]预处理P^i

ull get(int l, int r) {
	//将h[l-1]左移,将h[l-1]的高位与h[r]相对齐从而才可以未完成计算
	return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
	scanf("%d%d%s", &n, &m, str + 1);
	p[0] = 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;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if (get(l1, r1) == get(l2, r2)) puts("Yes");
		else puts("No");
	}
	return 0;
}
```

# 8 STL使用技巧

1.vector, 变长数组, 倍增的思想

```
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算, 按字典序
```

2.pair<int, int>

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

3.string, 字符串

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

4.queue, 队列

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

5.priority_queue, 优先队列, 默认是大根堆

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

6.stack, 栈

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

7.deque, 双端队列

```
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
```

8.set, map, multiset, multimap, 基于平衡二叉树(红黑树),

```
动态维护有序序列
size()
empty()
clear()
begin()/end()
++, –- 返回前驱和后继, 时间复杂度 O(logn)
```

(1) 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的最小的数的迭代器
```

(2) map/multimap

```
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作.  时间复杂度是 O(logn)
lower_bound()/upper_bound()
```

(3) unordered_set, unordered_map, unordered_multiset,

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

9.bitset, 圧位

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

count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
```

最后修改：2023 年 04 月 16 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

欢迎使用 Typecho
评论数： 1
比赛常用技巧及库函数
评论数： 0
贪心讲解
评论数： 0
动态规划基础
评论数： 0
数据结构初步
评论数： 0

竞赛常识
评论数： 0
图论初步
评论数： 0
考研励志
评论数： 0
基础数学知识
评论数： 0
搜索初步
评论数： 0

数据结构初步

RearWaves • 2023 年 04 月 16 日

# 数据结构1

# 1 链表与邻接表: 树与图的存储

## 1.1 单链表

作用: 邻接表, 存储图和树.

$$
head \to [0]:3\to [1]:5\to [2]:7 \to [3]:9 \to [-1]:\varnothing
$$

e[0]=3,  e[1]=5,  e[2]=7,  e[3]=9;

ne[0]=1, ne[1]=2, ne[2]=3, ne[3]=-1;

### [826. 单链表](https://www.acwing.com/problem/content/828/)

实现一个单链表, 链表初始为空, 支持三种操作:

1. 向链表头插入一个数;
2. 删除第 k 个插入的数后面的数; (删除下标为k-1的数)
3. 在第 k 个插入的数后插入一个数. (在下标为k-1的数后插入一个数)

现在要对该链表进行 M 次操作, 进行完所有操作后, 从头到尾输出整个链表.

输入格式: 整数 M , 表示操作次数.

输出格式: 共一行, 将整个链表从头到尾输出.

## 1.2 双链表

作用: 优化某些问题.

### [827. 双链表](https://www.acwing.com/problem/content/829/)

实现一个双链表, 双链表初始为空, 支持 5 种操作:

现在要对该链表进行 M 次操作, 进行完所有操作后, 从左到右输出整个链表.

```c++
#include <iostream>
using namespace std;

# 2 栈与队列: 单调队列、单调栈

## 2.1 栈

**模板:**

```c++
const int N = 1e5 + 10;
//定义栈
int stk[N], tt;
//插入
stk[++tt] = x;
//弹出
tt--;
//判断栈是否为空
if (tt > 0) not empty;
else empty;
//取栈顶元素
stk[tt];
```

### [828. 模拟栈](https://www.acwing.com/problem/content/830/)

实现一个栈, 栈初始为空, 支持四种操作:

1. `push x` – 向栈顶插入一个数 xx;
2. `pop` – 从栈顶弹出一个数;
3. `empty` – 判断栈是否为空;
4. `query` – 查询栈顶元素.

现在要对栈进行 M 个操作, 其中的每个操作 3 和操作 4 都要输出相应的结果.

### [3302. 表达式求值](https://www.acwing.com/problem/content/3305/)

给定一个表达式, 其中运算符仅包含 `+,-,*,/`(加 减 乘 整除), 可能包含括号, 请你求出表达式的最终值.

**注意: **

**中序遍历表达式树的计算过程:**

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

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

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

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

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

![8.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/2401_ee9fc12c25-8.png)

## 2.2 队列

**模板:**

### [829. 模拟队列](https://www.acwing.com/problem/content/831/)

实现一个队列, 队列初始为空, 支持四种操作:

1. `push x` – 向队尾插入一个数 xx;
2. `pop` – 从队头弹出一个数;
3. `empty` – 判断队列是否为空;
4. `query` – 查询队头元素.

现在要对队列进行 M 个操作, 其中的每个操作 3 和操作 4 都要输出相应的结果.

## 2.3 单调栈

常见题型: 给出一个序列, 找出每个数左边(或右边)满足某个性质最近的数.

### [830. 单调栈](https://www.acwing.com/problem/content/832/)

给定一个长度为 N 的整数数列, 输出每个数左边第一个比它小的数, 如果不存在则输出 −1.

输入格式:第一行包含整数 N, 表示数列长度. 第二行包含 N 个整数, 表示整数数列.

输出格式:共一行, 包含 N 个整数, 其中第 i 个数表示第 i 个数的左边第一个比它小的数, 如果不存在则输出 −1.

> 用单调递增栈, 当该元素可以入栈的时候, 栈顶元素就是它左侧第一个比它小的元素. 以: 3 4 2 7 5 为例, 过程如下:

![在这里插入图片描述](https://www.rearwaves.com/usr/assets/algorithm/data_structure/20201211221031165.gif)

## 2.4 单调队列

常见题型: 求滑动窗口的最大值最小值.

### [154. 滑动窗口](https://www.acwing.com/problem/content/156/)

以下是一个例子: 该数组为 `[1 3 -1 -3 5 3 6 7]`, k 为 3.

你的任务是确定滑动窗口位于每个位置时, 窗口中的最大值和最小值.

![滑动窗口.PNG](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_0923cf569c-滑动窗口.png)

# 3 KMP算法

最长公共前后缀长度数组next[j]含义是: P[j] 前面的字符串的最长公共前后缀长度.

P=“ababf” 的最长公共前后缀:

P[0] 前面没有字符串, 所以最长公共前后缀长度为 0.

P[1] 前面的字符串为: a, a没有前后缀(前后缀长度要小于字符串长度). 最长公共前后缀长度为 0.

P[2] 前面的字符串为: ab, 它的前缀为: a, 后缀为b. 前缀不等于后缀, 所以没有公共前后缀, 最长公共前后缀长度为 0.

P[3] 前面的字符串为: aba, aba 的前缀有: a, ab,  后缀有: a, ba. 因为 ab 不等于 ba, 所以最长公共前后缀为 a, 最长公共前后缀长度为 1.

P[4] 前面的字符串为: abab, abab 的前缀有: a, ab, aba, 后缀有: a, ab, bab. 最长公共前后缀为 ab, 长度为 2.

![Hongda_2022-11-21_15-56-17](https://www.rearwaves.com/usr/assets/algorithm/data_structure/Hongda_2022-11-21_15-56-17.png)

**next数组的具体求法:**

### [831. KMP字符串](https://www.acwing.com/problem/content/833/)

给定一个字符串 S, 以及一个模式串 P, 所有字符串中只包含大小写英文字母以及阿拉伯数字.

模式串 P 在字符串 S 中多次作为子串出现.

求出模式串 P 在字符串 S 中所有出现的位置的起始下标.

输入格式:字符串 P 的长度,字符串 P;字符串 SS 的长度,字符串 S.

输出格式:所有出现位置的起始下标(下标从 0 开始计数), 整数之间用空格隔开.

# 4 Tire树

用来高效的存储和查找字符串集合的数据结构.存储方法: 如图所示,最后需要在每一个单词的结尾加上一个标记.

![Trie1.PNG](https://www.rearwaves.com/usr/assets/algorithm/data_structure/31041_aa11ff2cad-Trie1.png)

![Hongda_2022-11-22_11-34-04](https://www.rearwaves.com/usr/assets/algorithm/data_structure/Hongda_2022-11-22_11-34-04.png)

### [835. Trie字符串统计](https://www.acwing.com/problem/content/837/)

维护一个字符串集合, 支持两种操作:

1. `I x` 向集合中插入一个字符串 x;
2. `Q x` 询问一个字符串在集合中出现了多少次.

共有 N 个操作, 字符串仅包含小写英文字母.

**解题思路:**

![Trie2.PNG](https://www.rearwaves.com/usr/assets/algorithm/data_structure/31041_aed49a42ad-Trie2.png)

### [143. 最大异或对](https://www.acwing.com/problem/content/145/)

在给定的 N 个整数A1, A2...AN 中选出两个进行 xor(异或) 运算, 得到的结果最大是多少?

**解题思路:**

首先`son[N][x]`这是个二维数组.

# 5 并查集

快速地处理以下问题:

1、将两个集合合并

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

对于暴力解法:

并查集可以在近乎O(1)的复杂度内解决这些问题.

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

问题1: 如何判断树根: `if(p[x]==x)`;

问题2: 如何求x的集合编号: `while(p[x]!=x) x=p[x];`;

问题3: 如何合并两个集合: px是x的集合编号, py是y的集合编号, `p[x]=y`.

**查找 + 路径压缩:**

举例:针对 x = 1

![13.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/64616_94ca39eb65-13.png)

**合并操作:**

合并1,  5: find(1) = 3 find(5) = 4; p[find(1)] = find(5) –> p[3] = 4.

![14.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/64616_1c43d0af65-14.png)

![15.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/64616_db117f1f65-15.png)

### [836. 合并集合](https://www.acwing.com/problem/content/838/)

一共有 n 个数, 编号是 1∼n, 最开始每个数各自在一个集合中. 现在要进行 m 个操作, 操作共有两种:

### [837. 连通块中点的数量](https://www.acwing.com/problem/content/839/)

给定一个包含 n 个点(编号为 1∼n)的无向图, 初始时图中没有边. 现在要进行 m 个操作, 操作共有三种:

### [240. 食物链](https://www.acwing.com/problem/content/242/)

有人用两种说法对这N个动物所构成的食物链关系进行描述:第一种说法是`1 X Y`, 表示X和Y是同类. 第二种说法是`2 X Y`, 表示X吃Y.

你的任务是根据给定的N和K句话, 输出假话的总数.

# 6 堆

手写堆主要解决以下问题:

![20210320153023354.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_3b2cf2fbe9-20210320153023354.png)

**构造:**

最后一个非叶子结点开始(也就是下面的 6 结点), 从左至右, 从下至上进行调整. 6 有两个儿子: 5 和 9, 这三个值中 9 最大. 6 和 9 交换.

![20210320153221152.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_016ea910e9-20210320153221152.png)

因为 6 和 9 交换了, 递归处理现在保存 6 的那个节点, 发现它没有儿子, 停止递归.

找到第二个非叶节点4, 由于[4,9,8]中9元素最大, 4 和 9 交换.

![20210320153251438.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_c90da89de9-20210320153251438.png)

因为 4 和 9 交换了, 递归处理现在保存 4 的那个节点: 找到它的两个儿子: 5, 6, 其中 6 最大, 交换 4 和 6.

![20210320153330130.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_8db80884e9-20210320153330130.png)

然后继续递归处理, 发现现在保存4 的节点没有儿子, 停止.

此时, 我们就将一个无序序列构造成了一个大顶堆.

### [838. 堆排序](https://www.acwing.com/problem/content/840/)

输入一个长度为 n 的整数数列, 从小到大输出前 m 小的数.

**解题思路:**

将堆顶元素 9 和末尾元素 4 进行交换.

![20210320153411240.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_e37e2eb5e9-20210320153411240.png)

重新调整结构(规则如上), 使其继续满足堆定义.

![20210320153445908.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_074da01de9-20210320153445908.png)

再将堆顶元素 8 与末尾元素 5 进行交换, 得到第二大元素 8.

![20210320153510654.png](https://www.rearwaves.com/usr/assets/algorithm/data_structure/55289_1c1ea166e9-20210320153510654.png)

后续过程, 继续进行调整, 交换, 如此反复进行, 最终使得整个序列有序.

```c++
const int N = 1e5 + 10;
int n, m;
int h[N], s;	//size为堆中的元素个数

### [839. 模拟堆](https://www.acwing.com/problem/content/841/)

维护一个集合, 初始时集合为空, 支持如下几种操作:

现在要进行 N 次操作, 对于所有第 2 个操作, 输出当前集合的最小值.

![位置指针](https://www.rearwaves.com/usr/assets/algorithm/data_structure/11802_daec3b5c5d-位置指针.png)

# 7 哈希表

## 7.1 哈希表

哈希表的作用: 把庞大复杂的数据映射到较小的范围. h(x) 可以把数据进行映射, 成为哈希函数.

若干不同的数倍映射成相同的数, 称为哈希冲突. 对于冲突, 我们有两种处理方法. 根据处理方法的不同, 分为拉链法和开放寻址法.

开放寻址法: 如果看到一个坑里有人就往前找没人的坑; 拉链法: 认准一个坑无论有没有人都在厕所门口排队.

### [840. 模拟散列表](https://www.acwing.com/problem/content/842/)

维护一个集合, 支持如下几种操作:

1. `I x`, 插入一个数 x;
2. `Q x`, 询问数 x 是否在集合中出现过;

现在要进行 N 次操作, 对于每个询问操作输出对应的结果.

**方法一: 开放寻址法**

**方法二: 拉链法**

## 7.2 字符串哈希

字符串哈希时间复杂度: O(n)+O(m). 全称字符串前缀哈希法, 把字符串变成一个p进制数字(哈希值), 实现不同的字符串映射到不同的数字.

对形如 $X_1X_2X_3⋯X_{n−1}X_n$ 的字符串,采用字符的 ascii 码乘上 P 的次方来计算哈希值.

映射公式 $(X_1×P^{n−1}+X_2×P^{n−2}+⋯+X_{n−1}×P^1+X_n×P^0)mod\ Q$

注意点:

前缀和公式 $h[i+1]=h[i]×P+s[i] \ i∈[0,n−1]$ h为前缀和数组, s为字符串数组;

区间和公式 $h[l,r]=h[r]−h[l−1]×P^{r−l+1}$.

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

### [841. 字符串哈希](https://www.acwing.com/problem/content/843/)

给定一个长度为 n 的字符串, 再给定 m 个询问, 每个询问包含四个整数 l1,r1,l2,r2l, 请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同.

字符串中只包含大小写英文字母和数字.

```c++
typedef unsigned long long ull;
const int N = 1e5 + 10, P = 131;
int n, m;
char str[N];
ull h[N], p[N];	//h[i]存放字符串的前缀值,p[i]预处理P^i

# 8 STL使用技巧

1.vector, 变长数组, 倍增的思想

```
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算, 按字典序
```

2.pair<int, int>

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

3.string, 字符串

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

4.queue, 队列

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

5.priority_queue, 优先队列, 默认是大根堆

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

6.stack, 栈

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

7.deque, 双端队列

```
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
```

8.set, map, multiset, multimap, 基于平衡二叉树(红黑树),

```
动态维护有序序列
size()
empty()
clear()
begin()/end()
++, –- 返回前驱和后继, 时间复杂度 O(logn)
```

(1) set/multiset

(2) map/multimap

```
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作.  时间复杂度是 O(logn)
lower_bound()/upper_bound()
```

(3) unordered_set, unordered_map, unordered_multiset,

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

9.bitset, 圧位

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

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数据结构初步

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款