算法基础复盘笔记Day04【数据结构】—— KMP、字典树(Tire)、并查集、堆、哈希表
第一章 KMP
一、KMP字符串
1. 题目描述
给定一个字符串 ,以及一个模式串 ,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 在字符串 中多次作为子串出现。
求出模式串 在字符串 中所有出现的位置的起始下标。
输入格式
第一行输入整数 ,表示字符串 的长度。
第二行输入字符串 。
第三行输入整数 ,表示字符串 的长度。
第四行输入字符串 。
输出格式
共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。
数据范围
输入样例:
3
aba
5
ababa
输出样例:
0 2
2. 思路分析
求前缀数组,即 数组,每一个子串都有一个固定的 数组,它记录着字符串匹配过程中失配情况下可以向后多跳几个字符,其实也就是子串的前缀和后缀相同的最长长度。
如果给定的模式串是:“ABCDABD”,从左至右遍历整个模式串,其各个子串的前缀后缀分别如下表格所示:
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
int ne[N]; //保存next数组
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1; //下标从1开始
//求next数组
//j表示匹配成功的长度,i表示p数组中下标,因为p数组的下标是从1开始的,只有1个时,j一定是0,所以i从2开始
for (int i = 2, j = 0; i <= n; i ++ )
{
//匹配不成功,则换到next数组
while (j && p[i] != p[j + 1]) j = ne[j];
//匹配成功的话,则j加1
if (p[i] == p[j + 1]) j ++;
//对应其下标
ne[i] = j;
}
//j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度是0
for (int i = 1, j = 0; i <= m; i ++ )
{
//如果匹配不成功,则切换j到next数组中的值
while (j && s[i] != p[j + 1]) j = ne[j];
//匹配成功,则j加1,继续后面的匹配
if (s[i] == p[j + 1]) j ++;
if (j == n)
{
//因为题目中下标从0开始所以是i - n,如果是从1开始则是i - n + 1
printf("%d ", i - n);
//继续切换j到next数组中值,继续匹配是否还能与后面的匹配成功
j = ne[j];
}
}
return 0;
}
第二章 字典树(Tire)
一、Tire字符串统计
1. 题目描述
维护一个字符串集合,支持两种操作:
I x
向集合中插入一个字符串 ;Q x
询问一个字符串在集合中出现了多少次。
共有 个操作,所有输入的字符串总长度不超过 ,字符串仅包含小写英文字母。
输入格式
第一行包含整数 ,表示操作数。
接下来
行,每行包含一个操作指令,指令为 I x
或 Q x
中的一种。
输出格式
对于每个询问指令 Q x
,都要输出一个整数作为结果,表示
在集合中出现的次数。
每个结果占一行。
数据范围
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例:
1
0
1
2. 思路分析
Trie树中有个二维数组 son[N][26]
,表示当前结点的儿子,如果没有的话,可以等于++idx
。Trie树本质上是一颗多叉树,对于字母而言最多有26个子结点。所以这个数组包含了两条信息。
建字典树:
儿子数组 son[p][u]
存储节点 p 沿着 u 这条边走到的子节点。边为 26 个小写字母(a ~ z)对应的映射值 0 ~ 25,每个节点最多可以有26个分叉。
比如:son[1][0]=2
表示1结点的一个值为a的子结点为结点2; 如果son[1][0] = 0
,则意味着没有值为a子结点。这里的son[N][26]
相当于链表中的ne[N]。
计数数组cnt[p]
存储以节点 p 结尾的单词的插入次数。
节点编号 idx
用来给节点编号。
- 空 Tire 仅有一个根节点,编号为0;
- 从根节点开始插,枚举字符串的每个字符,如果有儿子,则 p 指针走到儿子;如果没有儿子,则先创建儿子,p 指针再走到儿子;
- 在单词结束点记录插入次数。
3. 代码实现
//Tire树快速存储字符集合和快速查询字符集合
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// son[p][26]存储子节点的位置,分支最多26条
// cnt[] 存储以某节点为结尾的字符串个数(同时起标记作用)
// idx 表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str)
{
int p = 0; //指针p,指向当前节点
for (int i = 0; str[i]; i ++)
{
int u = str[i] - 'a'; //将字母映射为数字
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[2];
scanf("%s%s", op, str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
二、最大异对
1. 题目描述
在给定的 个整数 中选出两个进行 (异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 。
第二行输入 个整数 。
输出格式
输出一个整数表示答案。
数据范围
,
输入样例:
3
1 2 3
输出样例:
3
2. 思路分析
异或: 如果a、b两个值不相同,则异或结果为1;如果a、b两个值相同,异或结果为0。
- 将一个整数转化为一个32位的二进制数,也就是长度为32位的二进制字符串;
- 从最高位开始检索,每次找与该位相反的数字,才能让异或最大,如果没有想反的数字,则选择相同的数字。
- 返回最大的异或数。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
//M代表一个数字串二进制可以到多长
const int N = 100010, M = 3100010;
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; //x >> i:取二进制数x的第i位; x >> i & 1:二进制数x的第i位是0还是1
if (!son[p][u]) son[p][u] = ++idx; //不存在该子节点,创建该子节点
p = son[p][u]; //p指针指向子节点
}
}
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 = res * 2 + 1; // 更新res的值,每次把旧值乘以2(这一步相当于左移一位)再加上当前值
p = son[p][!u]; //p指针就指向不同数的地址
}
//如果当前层没有对应的不相同的数,则p指针指向相同的数的地址
//刚开始找0的时候是一样的所以+0 到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
// else
// {
// res = res * 2 + 0; //对res的值没有改变,省略
// p = son[p][u];
// }
else p = son[p][u];
}
return res;
}
int main()
{
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, search(a[i])); //查找a[i]最大的异或值
cout << res << endl;
return 0;
}
第三章 并查集
一、合并集合
1. 题目描述
一共有 个数,编号是 ,最开始每个数各自在一个集合中。
现在要进行 个操作,操作共有两种:
M a b
,将编号为 和 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;Q a b
,询问编号为 和 的两个数是否在同一个集合中;
输入格式
第一行输入整数 和 。
接下来
行,每行包含一个操作指令,指令为 M a b
或 Q a b
中的一种。
输出格式
对于每个询问指令 Q a b
,都要输出一个结果,如果 aa 和 bb 在同一集合内,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
2. 思路分析
并查集是一种树形的数据结构。
并查集支持的两个操作:
- 合并: 将两个子集合并成一个集合。
- 查找: 确定某个元素在哪个集合。
带路径压缩的查找:
根节点是集合的代表,查找就是找到元素所在集合的根。
- 如果父节点等于自己,则找到了根并返回;
- 如果还没有找到根,则继续递归查找;
- 在返回的路上,顺带修改各节点的父节点为根。
合并:
把一个集合的根指向另一个集合的根。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N];
// 返回x的祖先节点 + 路径压缩
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
cin >> 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);
//合并:把一个集合的根指向另一个集合的根
if (*op == 'M') p[find(a)] = find(b);
else
{
//若两个数的父节点一样,则在同一个集合
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
二、连通块中点的数量
1. 题目描述
给定一个包含 n 个点(编号为 )的无向图,初始时图中没有边。
现在要进行 m 个操作,操作共有三种:
C a b
,在点 aa 和点 bb 之间连一条边,a 和 b 可能相等;Q1 a b
,询问点 aa 和点 bb 是否在同一个连通块中,a 和 b 可能相等;Q2 a
,询问点 aa 所在连通块中点的数量;
输入格式
第一行输入整数 n 和 m。
接下来 m 行,每行包含一个操作指令,指令为 C a b
,Q1 a b
或 Q2 a
中的一种。
输出格式
对于每个询问指令 Q1 a b
,如果 a 和 b 在同一个连通块中,则输出 Yes
,否则输出 No
。
对于每个询问指令 Q2 a
,输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
输入样例:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例:
Yes
2
3
2. 思路分析
- 初始化:先设置每个节点的根节点为自己,刚开始是每个集合中点的数量为1;
- 合并集合: 把一个集合的根指向另一个集合的根,并且把该集合中点的数量加入另一个集合中;
- 查询:即判断两个集合的父节点是否一样。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
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()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
p[i] = i;
cnt[i] = 1;
}
while (m --)
{
string op;
int a, b;
cin >> op;
if (op == "C")
{
cin >> a >> b;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
cnt[b] += cnt[a];
}
}
else if (op == "Q1")
{
cin >> a >> b;
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
三、食物链
待完善......
第四章 堆
一、堆排序
1. 题目描述
输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
输出格式
共一行,包含 m 个整数,表示整数数列中前 m 小的数。
数据范围
,
输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3
2. 思路分析
如何手写一个堆?
- 插入一个数:
heap[ ++ size] = x; up(size)
; - 求集合中的最小值:
heap[1]
; - 删除最小值:
heap[1] = heap[size]; size -- ;down(1)
; - 删除任意一个元素:
heap[k] = heap[size]; size -- ;up(k); down(k)
; - 修改任意一个元素:
heap[k] = x; up(k); down(k)
;
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
//h[i]表示第i个结点存储的值,i从1开始,2 * i是左子节点,2 * i + 1是右子节点
//cnt 既表示堆里存储的元素个数,又表示最后一个结点的下标
int h[N], cnt;
void down(int u)
{
int t = u; //t存储三个结点中存在的最小的结点的下标,初始化为当前结点u
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //左子节点存在并且小于当前结点,更新t的下标
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; //右子节点存在并且小于当前结点,更新t的下标
if (u != t) //如果t==u意味着不用变动,u就是三个结点中拥有最小值的结点下标,否则交换数值
{
swap(h[u], h[t]);
down(t); //交换数值后,t这个结点存储原本u的值,u存储存储t的值(三个数中的最小值)。u不用调整了,但t情况不明,可能需要调整。直到它比左右子节点都小。
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> h[i];
cnt = n; //初始化cnt,表示堆中有多少个元素
//把堆初始化成小根堆,从二叉树的倒数第二行开始,把数字大的下沉
for (int i = n/2; i; i --) down(i);
while (m --)
{
cout << h[1] << ' '; //输出堆顶(最小值)
h[1] = h[cnt --]; ////删除堆顶(用最后一个数覆盖第一个数),并且长度减1
down(1); //让覆盖好的值继续往下走
}
return 0;
}
二、模拟堆
1. 题目描述
维护一个集合,初始时集合为空,支持如下几种操作:
I x
,插入一个数 x;PM
,输出当前集合中的最小值;DM
,删除当前集合中的最小值(数据保证此时的最小值唯一);D k
,删除第 k 个插入的数;C k x
,修改第 k 个插入的数,将其变为 x;
现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行,每行包含一个操作指令,操作指令为 I x
,PM
,DM
,D k
或 C k x
中的一种。
输出格式
对于每个输出指令 PM
,输出一个结果,表示当前集合中的最小值。
每个结果占一行。
数据范围
数据保证合法。
输入样例:
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例:
-10
6
2. 思路分析
相关思路在以下的代码注释中。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N]; //堆
int ph[N];//ph[k] = x:表示第k个插入的元素在树中存放的位置x
int hp[N];//hp[x] = k:表示树中位置x存放的是第k个插入的元素
int 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 (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)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u /= 2;
}
}
int main()
{
int n, m = 0; //m是记录插入的数的个数,m是对应hp中应该存的值
cin >> n;
while (n --)
{
string op;
int k, x;
cin >> op;
//插入一个数 x
if (op == "I")
{
cin >> x;
cnt ++;
m ++;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
//输出当前集合中的最小值
else if (op == "PM") cout << h[1] << endl;
//删除当前集合中的最小值
else if (op == "DM")
{
heap_swap(1, cnt);
cnt --;
down(1);
}
//删除第 k 个插入的数
else if (op == "D")
{
cin >> k;
k = ph[k]; //这里一定要用k=ph[k]保存第k个插入点的下标
heap_swap(k, cnt); //因为在此处heap_swap操作后ph[k]的值已经发生
cnt --;
up(k); //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
down(k);
}
//修改第 k 个插入的数,将其变为 x
else
{
cin >> k >> x;
h[ph[k]] = x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个,所以可直接传入ph[k]作为参数
up(ph[k]);
down(ph[k]);
}
}
return 0;
}
第五章 哈希表
一、模拟散列表
1. 题目描述
维护一个集合,支持如下几种操作:
I x
,插入一个数 x;Q x
,询问数 x 是否在集合中出现过;
现在要进行 N 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N,表示操作数量。
接下来 N 行,每行包含一个操作指令,操作指令为 I x
,Q x
中的一种。
输出格式
对于每个询问指令 Q x
,输出一个询问结果,如果 xx 在集合中出现过,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
2. 思路分析
散列表,也叫哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
开放寻址法:
- 如果要插入元素的映射位置没有元素,那么直接将该元素放在当前位置;
- 如果要插入元素的映射位置已经有了元素,那么就以此往后找,如果到了数组末尾还没有找到一个空的位置,就返回数组的头接着找;
- 为了防止整个数组都找了一遍还没有找到一个空的位置,数组大小通常要开数据范围的2~3倍。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 200003; //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
//t表示x映射到哈希表中的位置
//+N再%N可以避免出现负数
int t = (x % N + N) % N;
//冲突情况:当前位置不为空,并且不为x
while (h[t] != null && h[t] != x)
{
t ++;
if (t == N) t = 0; //如果到了末尾就从头开始
} //while一定会结束,因为我们的数组范围是开了2~3倍的,所以整个数组不会被完全使用,因此while不会无限循环
//如果x存在哈希表中,返回的t是下标;如果x不在哈希表中,返回的t是x在哈希表中要存储的位置
return t;
}
int main()
{
//把哈希表的值设置成一个不可能被映射到的数,以此来判断该位置有没有被使用
memset(h, 0x3f, sizeof h);
int n;
cin >> 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;
}
二、字符串哈希
1. 题目描述
给定一个长度为 n 的字符串,再给定 m 个询问,每个询问包含四个整数 ,请你判断 和 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m,表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串,字符串中只包含大小写英文字母和数字。
接下来 m 行,每行包含四个整数 ,表示一次询问所涉及的两个区间。
注意,字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes
2. 思路分析
字符串哈希,全称是字符串前缀哈希法,把 字符串变成一个p进制数字(哈希值),实现不同的字符串映射到不同的数字。
对形如
的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。
映射公式:
注意点:
- 任意字符不可以映射成0,否则会出现不同的字符串都映射成0的情况,比如A,AA,AAA…都映射成0的话那就无法进行比较字符串是否相同了;
- 冲突问题:听过巧妙设置P(131 或 13331),Q( )的值,一般情况下可以避免发生冲突;
- 由于需要模
,则可以直接用
unsigned long long
来存储,它可以溢出,溢出时相当于模了一个 ;
问题是比较不同区间的子串是否相同,就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和。
前缀和公式
h为前缀和数组,s为字符串数组。
区间和公式
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样,只差两位,乘上 把 ABC 变为 ABC00,再用 ABCDE - ABC00 得到 DE 的哈希值。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
// unsigned long long 数据类型的范围是[0,2^64-1]
// 用 unsigned long long来存储h\,它可以溢出,溢出时就相当于模了一个2^64
typedef unsigned long long ULL;
//P取131或者13331,mod取2^64,在99.99%的情况下不会发生冲突
const int N = 100010, P = 131;
int n, m;
char str[N];
//h[i]表示前i个字符的hash值
ULL h[N], p[N];
//求[l, r]区间中字符串的哈希值
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; //p的0次方等于1
for (int i = 1; i <= n; i ++)
{
h[i] = h[i - 1] * P + str[i]; //前缀和求以i结尾的整个字符串的哈希值
p[i] = p[i - 1] * P;
}
while (m --)
{
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
//如果两个区间的哈希值相同,则字符串相同;否则不同
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}
return 0;
}
创作不易,如果有帮助到你,请给文章==点个赞和收藏==,让更多的人看到!!!
==关注博主==不迷路,内容持续更新中。# 第一章 KMP
一、KMP字符串
1. 题目描述
给定一个字符串 ,以及一个模式串 ,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 在字符串 中多次作为子串出现。
求出模式串 在字符串 中所有出现的位置的起始下标。
输入格式
第一行输入整数 ,表示字符串 的长度。
第二行输入字符串 。
第三行输入整数 ,表示字符串 的长度。
第四行输入字符串 。
输出格式
共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。
数据范围
输入样例:
3
aba
5
ababa
输出样例:
0 2
2. 思路分析
求前缀数组,即 数组,每一个子串都有一个固定的 数组,它记录着字符串匹配过程中失配情况下可以向后多跳几个字符,其实也就是子串的前缀和后缀相同的最长长度。
如果给定的模式串是:“ABCDABD”,从左至右遍历整个模式串,其各个子串的前缀后缀分别如下表格所示:
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
int ne[N]; //保存next数组
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1; //下标从1开始
//求next数组
//j表示匹配成功的长度,i表示p数组中下标,因为p数组的下标是从1开始的,只有1个时,j一定是0,所以i从2开始
for (int i = 2, j = 0; i <= n; i ++ )
{
//匹配不成功,则换到next数组
while (j && p[i] != p[j + 1]) j = ne[j];
//匹配成功的话,则j加1
if (p[i] == p[j + 1]) j ++;
//对应其下标
ne[i] = j;
}
//j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度是0
for (int i = 1, j = 0; i <= m; i ++ )
{
//如果匹配不成功,则切换j到next数组中的值
while (j && s[i] != p[j + 1]) j = ne[j];
//匹配成功,则j加1,继续后面的匹配
if (s[i] == p[j + 1]) j ++;
if (j == n)
{
//因为题目中下标从0开始所以是i - n,如果是从1开始则是i - n + 1
printf("%d ", i - n);
//继续切换j到next数组中值,继续匹配是否还能与后面的匹配成功
j = ne[j];
}
}
return 0;
}
第二章 字典树(Tire)
一、Tire字符串统计
1. 题目描述
维护一个字符串集合,支持两种操作:
I x
向集合中插入一个字符串 ;Q x
询问一个字符串在集合中出现了多少次。
共有 个操作,所有输入的字符串总长度不超过 ,字符串仅包含小写英文字母。
输入格式
第一行包含整数 ,表示操作数。
接下来
行,每行包含一个操作指令,指令为 I x
或 Q x
中的一种。
输出格式
对于每个询问指令 Q x
,都要输出一个整数作为结果,表示
在集合中出现的次数。
每个结果占一行。
数据范围
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例:
1
0
1
2. 思路分析
Trie树中有个二维数组 son[N][26]
,表示当前结点的儿子,如果没有的话,可以等于++idx
。Trie树本质上是一颗多叉树,对于字母而言最多有26个子结点。所以这个数组包含了两条信息。
建字典树:
儿子数组 son[p][u]
存储节点 p 沿着 u 这条边走到的子节点。边为 26 个小写字母(a ~ z)对应的映射值 0 ~ 25,每个节点最多可以有26个分叉。
比如:son[1][0]=2
表示1结点的一个值为a的子结点为结点2; 如果son[1][0] = 0
,则意味着没有值为a子结点。这里的son[N][26]
相当于链表中的ne[N]。
计数数组cnt[p]
存储以节点 p 结尾的单词的插入次数。
节点编号 idx
用来给节点编号。
- 空 Tire 仅有一个根节点,编号为0;
- 从根节点开始插,枚举字符串的每个字符,如果有儿子,则 p 指针走到儿子;如果没有儿子,则先创建儿子,p 指针再走到儿子;
- 在单词结束点记录插入次数。
3. 代码实现
//Tire树快速存储字符集合和快速查询字符集合
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// son[p][26]存储子节点的位置,分支最多26条
// cnt[] 存储以某节点为结尾的字符串个数(同时起标记作用)
// idx 表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str)
{
int p = 0; //指针p,指向当前节点
for (int i = 0; str[i]; i ++)
{
int u = str[i] - 'a'; //将字母映射为数字
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[2];
scanf("%s%s", op, str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
二、最大异对
1. 题目描述
在给定的 个整数 中选出两个进行 (异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 。
第二行输入 个整数 。
输出格式
输出一个整数表示答案。
数据范围
,
输入样例:
3
1 2 3
输出样例:
3
2. 思路分析
异或: 如果a、b两个值不相同,则异或结果为1;如果a、b两个值相同,异或结果为0。
- 将一个整数转化为一个32位的二进制数,也就是长度为32位的二进制字符串;
- 从最高位开始检索,每次找与该位相反的数字,才能让异或最大,如果没有想反的数字,则选择相同的数字。
- 返回最大的异或数。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
//M代表一个数字串二进制可以到多长
const int N = 100010, M = 3100010;
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; //x >> i:取二进制数x的第i位; x >> i & 1:二进制数x的第i位是0还是1
if (!son[p][u]) son[p][u] = ++idx; //不存在该子节点,创建该子节点
p = son[p][u]; //p指针指向子节点
}
}
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 = res * 2 + 1; // 更新res的值,每次把旧值乘以2(这一步相当于左移一位)再加上当前值
p = son[p][!u]; //p指针就指向不同数的地址
}
//如果当前层没有对应的不相同的数,则p指针指向相同的数的地址
//刚开始找0的时候是一样的所以+0 到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
// else
// {
// res = res * 2 + 0; //对res的值没有改变,省略
// p = son[p][u];
// }
else p = son[p][u];
}
return res;
}
int main()
{
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, search(a[i])); //查找a[i]最大的异或值
cout << res << endl;
return 0;
}
第三章 并查集
一、合并集合
1. 题目描述
一共有 个数,编号是 ,最开始每个数各自在一个集合中。
现在要进行 个操作,操作共有两种:
M a b
,将编号为 和 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;Q a b
,询问编号为 和 的两个数是否在同一个集合中;
输入格式
第一行输入整数 和 。
接下来
行,每行包含一个操作指令,指令为 M a b
或 Q a b
中的一种。
输出格式
对于每个询问指令 Q a b
,都要输出一个结果,如果 aa 和 bb 在同一集合内,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
2. 思路分析
并查集是一种树形的数据结构。
并查集支持的两个操作:
- 合并: 将两个子集合并成一个集合。
- 查找: 确定某个元素在哪个集合。
带路径压缩的查找:
根节点是集合的代表,查找就是找到元素所在集合的根。
- 如果父节点等于自己,则找到了根并返回;
- 如果还没有找到根,则继续递归查找;
- 在返回的路上,顺带修改各节点的父节点为根。
合并:
把一个集合的根指向另一个集合的根。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N];
// 返回x的祖先节点 + 路径压缩
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n, m;
cin >> 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);
//合并:把一个集合的根指向另一个集合的根
if (*op == 'M') p[find(a)] = find(b);
else
{
//若两个数的父节点一样,则在同一个集合
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
二、连通块中点的数量
1. 题目描述
给定一个包含 n 个点(编号为 )的无向图,初始时图中没有边。
现在要进行 m 个操作,操作共有三种:
C a b
,在点 aa 和点 bb 之间连一条边,a 和 b 可能相等;Q1 a b
,询问点 aa 和点 bb 是否在同一个连通块中,a 和 b 可能相等;Q2 a
,询问点 aa 所在连通块中点的数量;
输入格式
第一行输入整数 n 和 m。
接下来 m 行,每行包含一个操作指令,指令为 C a b
,Q1 a b
或 Q2 a
中的一种。
输出格式
对于每个询问指令 Q1 a b
,如果 a 和 b 在同一个连通块中,则输出 Yes
,否则输出 No
。
对于每个询问指令 Q2 a
,输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
输入样例:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例:
Yes
2
3
2. 思路分析
- 初始化:先设置每个节点的根节点为自己,刚开始是每个集合中点的数量为1;
- 合并集合: 把一个集合的根指向另一个集合的根,并且把该集合中点的数量加入另一个集合中;
- 查询:即判断两个集合的父节点是否一样。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
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()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
p[i] = i;
cnt[i] = 1;
}
while (m --)
{
string op;
int a, b;
cin >> op;
if (op == "C")
{
cin >> a >> b;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
cnt[b] += cnt[a];
}
}
else if (op == "Q1")
{
cin >> a >> b;
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
三、食物链
待完善......
第四章 堆
一、堆排序
1. 题目描述
输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
输出格式
共一行,包含 m 个整数,表示整数数列中前 m 小的数。
数据范围
,
输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3
2. 思路分析
如何手写一个堆?
- 插入一个数:
heap[ ++ size] = x; up(size)
; - 求集合中的最小值:
heap[1]
; - 删除最小值:
heap[1] = heap[size]; size -- ;down(1)
; - 删除任意一个元素:
heap[k] = heap[size]; size -- ;up(k); down(k)
; - 修改任意一个元素:
heap[k] = x; up(k); down(k)
;
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
//h[i]表示第i个结点存储的值,i从1开始,2 * i是左子节点,2 * i + 1是右子节点
//cnt 既表示堆里存储的元素个数,又表示最后一个结点的下标
int h[N], cnt;
void down(int u)
{
int t = u; //t存储三个结点中存在的最小的结点的下标,初始化为当前结点u
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //左子节点存在并且小于当前结点,更新t的下标
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; //右子节点存在并且小于当前结点,更新t的下标
if (u != t) //如果t==u意味着不用变动,u就是三个结点中拥有最小值的结点下标,否则交换数值
{
swap(h[u], h[t]);
down(t); //交换数值后,t这个结点存储原本u的值,u存储存储t的值(三个数中的最小值)。u不用调整了,但t情况不明,可能需要调整。直到它比左右子节点都小。
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> h[i];
cnt = n; //初始化cnt,表示堆中有多少个元素
//把堆初始化成小根堆,从二叉树的倒数第二行开始,把数字大的下沉
for (int i = n/2; i; i --) down(i);
while (m --)
{
cout << h[1] << ' '; //输出堆顶(最小值)
h[1] = h[cnt --]; ////删除堆顶(用最后一个数覆盖第一个数),并且长度减1
down(1); //让覆盖好的值继续往下走
}
return 0;
}
二、模拟堆
1. 题目描述
维护一个集合,初始时集合为空,支持如下几种操作:
I x
,插入一个数 x;PM
,输出当前集合中的最小值;DM
,删除当前集合中的最小值(数据保证此时的最小值唯一);D k
,删除第 k 个插入的数;C k x
,修改第 k 个插入的数,将其变为 x;
现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行,每行包含一个操作指令,操作指令为 I x
,PM
,DM
,D k
或 C k x
中的一种。
输出格式
对于每个输出指令 PM
,输出一个结果,表示当前集合中的最小值。
每个结果占一行。
数据范围
数据保证合法。
输入样例:
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例:
-10
6
2. 思路分析
相关思路在以下的代码注释中。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N]; //堆
int ph[N];//ph[k] = x:表示第k个插入的元素在树中存放的位置x
int hp[N];//hp[x] = k:表示树中位置x存放的是第k个插入的元素
int 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 (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)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u /= 2;
}
}
int main()
{
int n, m = 0; //m是记录插入的数的个数,m是对应hp中应该存的值
cin >> n;
while (n --)
{
string op;
int k, x;
cin >> op;
//插入一个数 x
if (op == "I")
{
cin >> x;
cnt ++;
m ++;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
//输出当前集合中的最小值
else if (op == "PM") cout << h[1] << endl;
//删除当前集合中的最小值
else if (op == "DM")
{
heap_swap(1, cnt);
cnt --;
down(1);
}
//删除第 k 个插入的数
else if (op == "D")
{
cin >> k;
k = ph[k]; //这里一定要用k=ph[k]保存第k个插入点的下标
heap_swap(k, cnt); //因为在此处heap_swap操作后ph[k]的值已经发生
cnt --;
up(k); //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
down(k);
}
//修改第 k 个插入的数,将其变为 x
else
{
cin >> k >> x;
h[ph[k]] = x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个,所以可直接传入ph[k]作为参数
up(ph[k]);
down(ph[k]);
}
}
return 0;
}
第五章 哈希表
一、模拟散列表
1. 题目描述
维护一个集合,支持如下几种操作:
I x
,插入一个数 x;Q x
,询问数 x 是否在集合中出现过;
现在要进行 N 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N,表示操作数量。
接下来 N 行,每行包含一个操作指令,操作指令为 I x
,Q x
中的一种。
输出格式
对于每个询问指令 Q x
,输出一个询问结果,如果 xx 在集合中出现过,则输出 Yes
,否则输出 No
。
每个结果占一行。
数据范围
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
2. 思路分析
散列表,也叫哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
开放寻址法:
- 如果要插入元素的映射位置没有元素,那么直接将该元素放在当前位置;
- 如果要插入元素的映射位置已经有了元素,那么就以此往后找,如果到了数组末尾还没有找到一个空的位置,就返回数组的头接着找;
- 为了防止整个数组都找了一遍还没有找到一个空的位置,数组大小通常要开数据范围的2~3倍。
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 200003; //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
//t表示x映射到哈希表中的位置
//+N再%N可以避免出现负数
int t = (x % N + N) % N;
//冲突情况:当前位置不为空,并且不为x
while (h[t] != null && h[t] != x)
{
t ++;
if (t == N) t = 0; //如果到了末尾就从头开始
} //while一定会结束,因为我们的数组范围是开了2~3倍的,所以整个数组不会被完全使用,因此while不会无限循环
//如果x存在哈希表中,返回的t是下标;如果x不在哈希表中,返回的t是x在哈希表中要存储的位置
return t;
}
int main()
{
//把哈希表的值设置成一个不可能被映射到的数,以此来判断该位置有没有被使用
memset(h, 0x3f, sizeof h);
int n;
cin >> 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;
}
创作不易,如果有帮助到你,请给文章==点个赞和收藏==,让更多的人看到!!!
==关注博主==不迷路,内容持续更新中。
- 点赞
- 收藏
- 关注作者
评论(0)