哈希表
这里我们先介绍哈希函数hash()
哈希函数的作用是将一个大值域集合 映射成 小值域集合
举个例子：
原来的集合存的是x x在-10^9 - 10^9之间，我们通过hash函数，hash(x) = k
将x映射成k, k在0-10^5之间，通过哈希函数我们将空间进行了压缩。
而哈希表是一个键值对集合，就是存储了上述的映射关系
其中key就是哈希值k，value就是元素x
然后我们一般用数组h[]模拟哈希表，下标就是key（哈希值k）, h[k]是value(元素x)
哈希表里，我们很容易发现，对于相同的key，可能存在多个元素，这就是哈希冲突
怎么解决哈希冲突呢，这里常用的有两种方法：
- 开放寻址法：发现当前槽里有元素，就去找下一个空的槽
- 拉链法：在当前槽里放一个邻接表，然后插入表头
基本思路
拉链法或者是开放寻址法都是可以的，一般开放寻址法要好写一些
注意：
表示空节点（节点值为空），一般有两种方法
- 通过节点地址，常见在链表中，如果是结构体模拟，那就指针指向空，指针 = nullptr; 如果是数组模拟，那就是下标 = -1.
- 通过节点值，一般把节点值设为正无穷或者负无穷 常见的是0x3f3f3f3f，为什么不用INT_MAX或者INT_MIN，因为后者可能会在做一些运算后溢出
参考代码
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
|
#include <cstring>
#include <iostream>
using namespace std;
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;
}
#include <cstring>
#include <iostream>
using namespace std;
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;
}
|
Reference
[1]. yxc
[2]. 理解两种哈希表的实现方法
[3]. 开放寻址法细节
[4]. STL
基本思路
给定一个字符串的任意两段区间，判断两个子串是否相等
如果暴力做法，m次询问，每次都需要同时扫描两个子串，时间复杂度$O(n*m)$,显然会超时。
所以这里我们利用前缀和的思想可以提前预处理这段字符串，那么对于字符串没有所谓的前缀和呢，所以我们实际处理的是前缀哈希值
这就是我们所说的字符串哈希算法，然后对于每一次询问，就可以把查询时间缩减到$O(1)$,时间复杂度就可以优化成$O(n + m)$
所以总结就是以下几个步骤
- 求字符串的前缀哈希值数组
- 根据前缀和哈希值数组得到两个子串的哈希值
- 比较两个子串的哈希值，如果相等，那就代表两个字符串相等
参考代码
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
| #include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];
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 + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
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;
}
|
Reference
[1]. yxc
[2]. Sean今天AC了吗
[3]. 小张同学
[4]. _不知道
[5]. 三个不好理解的地方逐一击破 + 完整注释！
[6]. 字符串哈希的简单分析与证明
并查集
并查集是一种数据结构，它可以动态维护若干个不重叠的结合，并且支持合并与查询
对于每一个集合我们可以用一棵树表示，其中root节点就代表这棵树，然后根节点的父节点是它自己。
在图论之前，数组经常是用来存一个序列，但是学习图论之后，数组经常用来存一些节点的属性，比如说e[]存节点值，ne[]存节点的next指针
p[]存节点的父节点 son[]存节点的子节点 还有很多
这里我们用p[]存储每个节点的父节点。
那么对于并查集的两个操作
- 合并：实际上就是把其中一个树的根节点，作为另一颗树根节点的子节点，p[x] = y
- 查询：就是查该节点的根节点，然后通过根节点判断属于哪个集合
基本思路
并查集模板题，对于查询操作，可以用递归查询，然后回溯的过程里可以做路径压缩
参考代码
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
| #include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[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 = 1; i <= n; i ++) p[i] = i;
while(m --){
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'M') p[find(a)] = find(b);
else{
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
|
Reference
[1]. yxc
[2]. 图解_并查集
[3]. 理解并查集中的find函数
[4]. Bug-Free
基本思路
该题是并查集的应用，乍看像图论，其实是并查集
每一个连通块其实都是一个集合。
- 对于连边操作，其实就是集合间的合并。
- 对于查询是否在同一连通块，也就是集合的询问操作。
- 对于查询连通块中点的数量，也就是查询集合的大小。
因此，我们这题直接用并查集模板就可以完成了。
只是要附加一个size，在合并的时候加上即可。
参考代码
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
| #include <iostream>
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()
{
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;
}
|
Reference
[1]. yxc
[2]. 并查集_连通块中点的数量
[3]. 封禁用户