[AcWing]基础算法课程--数据结构
目录
1、单链表
2、双链表
3、栈
3.1 模拟栈
3.2 表达式求值
4、队列
5、单调栈
6、滑动窗口
7、KMP字符串
8、Trie字符串统计
方法一
方法二
9、并查集
9.1 合并集合
9.2 连通块中点的数量
10、堆
10.1 堆排序
10.2 模拟堆
11、哈希表
11.1 模拟散列表
拉链法
开放寻址法
11.2 字符串哈希
1、单链表
826. 单链表 - AcWing题库
实现单链表实际上有两种方式
第一种是使用结构体+指针，称为动态链表，在面试中是可以使用的，但是在算法题中因为new太慢了，所以不推荐使用
第二种是使用数组模拟，称为静态链表，我们这里用的就是静态链表
静态链表有几个参数：
数组e表示某个点的值
数组ne表示某个点的next指针
head是头指针，链表为空时用-1
idx表示当前使用到了哪一个点
#include<iostream>
#include<stdio.h>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], head, idx, n;
void init()
{
head = -1;
idx = 0;
}
void push_front(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void insert(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void erase(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
scanf("%d", &n);
while(n--)
{
int k, x;
char ch;
cin>>ch; // 不要使用scanf，因为缓冲区
// while(scanf(" %c", &ch) != 1 || ch == ' '); 若要使用scanf，就这样
if(ch == 'H')
{
scanf("%d", &x);
push_front(x);
}
else if(ch == 'D')
{
scanf("%d", &k);
if(!k) head = ne[head];
else erase(k - 1);
}
else
{
scanf("%d %d", &k, &x);
insert(k - 1, x);
}
}
for(int i = head;i != -1;i = ne[i]) printf("%d ", e[i]);
printf("\n");
return 0;
} 注意：
（1）insert中是将x插到下标为k的结点的后面
（2）删除第k个插入，就是删除下标为k-1的，因为第1个插入，下标为0
（3）对于头删需要特殊处理，否则head没变
2、双链表
827. 双链表 - AcWing题库
（1）双链表是让下标为0的点为头结点，下标为1的点为尾结点。刚初始化完就已经有2个结点了，所以idx是从2开始的
（2）因为idx是从2开始的，所以我们在处理第k个插入时，传参时下标时k + 1
#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int e[N], l[N], r[N], idx, m;
void init()
{
r[0] = 1,l[1] = 0;
idx = 2;
}
void insert_r(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx++;
}
void insert_l(int k, int x)
{
/*e[idx] = x;
r[idx] = k;
l[idx] = l[k];
r[l[k]] = idx;
l[k] = idx++;*/
insert_r(l[k], x); // 后面3个直接复用insert_r即可
}
void push_front(int x)
{
/*e[idx] = x;
l[idx] = 0;
r[idx] = r[0];
l[r[0]] = idx;
r[0] = idx++;*/
insert_r(0, x);
}
void push_back(int x)
{
/*e[idx] = x;
r[idx] = 1;
l[idx] = l[1];
r[l[1]] = idx;
l[1] = idx++;*/
insert_l(1, x);
}
void erase(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
init();
scanf("%d", &m);
while(m--)
{
string ch;cin>>ch;
if(ch == "L")
{
int x;scanf("%d", &x);
push_front(x);
}
else if(ch == "R")
{
int x;scanf("%d", &x);
push_back(x);
}
else if(ch == "D")
{
int k;scanf("%d", &k);
erase(k + 1);
}
else if(ch == "IL")
{
int x, k;scanf("%d%d", &k, &x);
insert_l(k + 1, x);
}
else
{
int x, k;scanf("%d%d", &k, &x);
insert_r(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
return 0;
}3、栈
3.1 模拟栈
828. 模拟栈 - AcWing题库
tt是栈顶下标，初始化tt为-1
#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int st[N], tt;
void init()
{
tt = -1;
}
void push(int x)
{
st[++tt] = x;
}
void pop()
{
--tt;
}
bool empty()
{
return tt == -1;
}
int query()
{
return st[tt];
}
int main()
{
init();
int m;scanf("%d", &m);
while(m--)
{
string s;cin>>s;
if(s == "push")
{
int x;scanf("%d", &x);
push(x);
}
else if(s == "pop") pop();
else if(s == "empty")
{
if(empty()) printf("YES\n");
else printf("NO\n");
}
else printf("%d\n", query());
}
return 0;
}3.2 表达式求值
3302. 表达式求值 - AcWing题库
这道题看起来是很简单的，明显就是开两个栈，一个栈用来存数字，一个栈用来存符号，当遇到右括号就拿出两个数和一个符号来计算，再将计算结果放入栈，直到左括号。最后直到存放符号的栈为空，存放数字的栈中有唯一的数，这个数就是答案。
这样是不对的，没有考虑到运算的优先级，乘除法的优先级是高于加减法的。如2 * 3 + 5，按上面的思路，最终存数字的栈2 3 5，存符号的栈* +，我们会先算加法，导致出错
为了考虑优先级，此时有4步。开一个存数字的栈num，存符号的栈op
考虑优先级主要有两条规则：
优先级高的要比优先级低的先计算
优先级相同的要从左向右依次计算
(1)遇到数字，放入num
(2)遇到'('，放入op
(3)遇到')'，从num中取出两个数，从op中取出一个符号，计算完再将结果放入num，直到op的栈顶是'('，然后将'('弹出栈
(4)遇到+、-、*、/，要看一下op栈顶的符号的优先级是否大于等于当前的符号，若大于等于，要先计算，直到op栈顶的符号优先级低于当前符号。像上面的2 * 3 + 5，我们遍历到+时，num里面是2 3，op里里面是*，*的优先级明显高于+，所以我们要先计算，直到op的栈顶元素的优先级低于+，第一次计算后，num里面是6，op里面没有元素了，直接放入+，此时就先计算了*。注意：这一步为什么要有等于，因为我们计算优先级相同的运算符时需要从左向右依次计算，比方说0 - 5 + 8，如果没有等于，会先计算5 + 8，结果是-13，明显是错的
#include<iostream>
#include<stack>
#include<unordered_map>
#include<string>
using namespace std;
stack<int> num;
stack<char> op;
unordered_map<char, int> cmp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; // 存放个运算符的优先级
void equl() // 计算过程
{
int a = num.top(); num.pop();
int b = num.top(); num.pop();
char x = op.top(); op.pop();
int k = 0;
if(x == '+') k = a + b;
else if(x == '-') k = b - a;
else if(x == '*') k = a * b;
else k = b / a;
num.push(k);
}
int main()
{
string s; cin>>s;
for(int i = 0;i < s.size();i++)
{
char ch = s[i];
if(isdigit(ch))
{
int k = ch - '0', j = i + 1;
while(j < s.size() && isdigit(s[j]))
k = k * 10 + (s[j++] - '0');
num.push(k);
i = j - 1;
}
else if(ch == '(') op.push('(');
else if(ch == ')')
{
while(op.size() && op.top() != '(') equl();
op.pop();
}
else
{
while(op.size() && cmp[op.top()] >= cmp[ch]) equl();
op.push(ch);
}
}
// 此时剩余的运算符都是优先级低的，因为优先级低的运算符放入栈前要先将优先级高的弹出
while(op.size()) equl();
cout << num.top() << endl;
return 0;
}4、队列
829. 模拟队列 - AcWing题库
hh表示队头下标，tt表示队尾下标，hh初始化为0，tt初始化为-1
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt;
void init()
{
hh = 0, tt = -1;
}
void push(int x)
{
q[++tt] = x;
}
void pop()
{
++hh;
}
bool empty()
{
return tt < hh;
}
int query()
{
return q[hh];
}
int main()
{
init();
int m;scanf("%d", &m);
while(m--)
{
string s;cin>>s;
if(s == "push")
{
int x;scanf("%d", &x);
push(x);
}
else if(s == "pop") pop();
else if(s == "empty")
{
if(empty()) printf("YES\n");
else printf("NO\n");
}
else printf("%d\n", query());
}
return 0;
}5、单调栈
830. 单调栈 - AcWing题库
这道题很容易就能想到暴力解法，两层for循环，这样的时间复杂度明显是O(N^2)的
我们需要对其就行优化。
假设我们当前遍历到下标为i的位置，可以用一个栈来存储i左边的所有元素。此时会发现有一些元素是没有用的，假设i>5，此时栈中有a[3] >= a[5]，我们现在是要找离下标i最近的一个，且比a[i]小的，a[3]离a[i]比a[5]离a[i]更远，且a[3] >= a[5]，所以在i以及后面的所有数中，都不可能会用到a[3]，所以可以直接将a[3]从栈中删除
现在思路就变成了，遍历到a[i]，看一下栈顶元素是否大于等于a[i]，若栈顶元素大于等于a[i]，那么a[i]之后的元素一定不会用到这个栈顶元素，直接将栈顶元素删除，然后继续比较，直到找到一个栈顶元素小于a[i]，输出，并将a[i]放入栈中。当然也有可能a[i]在与栈中元素比较过程中，栈中元素弹出完了还没有找到比a[i]小的元素，此时直接输出-1，然后将a[i]放入栈中
只要按照这个思路执行，这个栈就是单调的，以这道题找左边最近的较小值为例，这个栈是单调递增的
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int st[N], tt = -1;
int main()
{
int n;scanf("%d", &n);
while(n--)
{
int x;scanf("%d", &x);
while(tt != -1) // 只要栈不为空就一直找比x小的
{
if(st[tt] < x)
{
printf("%d ", st[tt]);
break;
}
else --tt;
}
if(tt == -1) printf("-1 "); // 栈弹出完了输出-1
st[++tt] = x; // 将x入栈
}
return 0;
}这里使用的是数组模拟的栈，数组模拟的栈可以不用像前面模拟栈中写成各个函数，在做题时直接写反而更简便些。这里也可以使用STL中的stack，不过这样不如直接使用数组模拟的快。
这样，我们对于每一个元素最多出栈一次、入栈一次，所以时间复杂度是O(N)
6、滑动窗口
154. 滑动窗口 - AcWing题库
我们以输出窗口中的最小值为例，输出最大值是类似的，这道题很容易想到的就是每次遍历一遍窗口，这样时间复杂度是O(k*n)。
这个窗口是从前面出，后面进，所以我们可以用一个队列来模拟这个窗口。我们会发现有一些值是没有用的，假设我们现在的遍历到的元素是-3，从队头弹出一个元素后，队列中的值是-5，1，我们会发现1 > -3，并且1在-3的左边，也就是说对于-3往后遍历到的值，1在的时候-3一定也在，所以1是没用的，直接弹出，现在队列中剩下-5，-5比-3小，不需要管，将-3放入队列，此时-5就是这个队列中最小的。
现在思路就变成了，遍历到a[i]，若下标已经大于等于3(下标从0开始)，先弹出队头元素，若小于3，则不需要弹出。比较一下a[i]与队尾元素的大小，若队尾元素大于等于a[i]，直接弹出，直到找到一个比a[i]小的或者弹出完了，就将a[i]放入。只要根据这个规则，这个队列就一定是单调的，像这道题，队列就是单调递增的，最小的元素就是队头元素
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], hh, tt, n, k; // q是存下标
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0;i < n;i++) scanf("%d", &a[i]);
hh = 0, tt = -1;
for(int i = 0;i < n;i++)
{
// 判断队头是否需要滑出窗口,hh<=tt是保证队列不为空，i-k+1>q[hh]是保证队列中元素最多只有3个
if(hh <= tt && i - k + 1 > q[hh]) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--; // 如果队尾数据大于等于a[i],则弹出
q[++tt] = i;
if(i >= k - 1) printf("%d ", a[q[hh]]); // 当窗口中只有第1个数或前两个数时是不会输出的
}
printf("\n");
hh = 0, tt = -1; // 一定要记得恢复
for(int i = 0;i < n;i++)
{
// 判断队头是否需要滑出窗口,hh<=tt是保证队列不为空，i-k+1>q[hh]是保证队列中元素最多只有3个
if(hh <= tt && i - k + 1 > q[hh]) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--; // 如果队尾数据大于等于a[i],则弹出
q[++tt] = i;
if(i >= k - 1) printf("%d ", a[q[hh]]); // 当窗口中只有第1个数或前两个数时是不会输出的
}
return 0;
}7、KMP字符串
831. KMP字符串 - AcWing题库
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N];
int n, m;
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
// 构建next数组
for (int i = 2, j = 0; i <= n; i++)
{
while (j && p[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
if (p[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
ne[i] = j;
}
// 匹配原数组
for (int i = 1, j = 0; i <= m; i++)
{
while (j && s[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
if (s[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
if (j == n) // p数组遍历完了
{
printf("%d ", i - n); // 打印起始位置
j = ne[j]; // 遍历完成后回退到ne[j]的位置继续匹配
}
}
return 0;
}8、Trie字符串统计
835. Trie字符串统计 - AcWing题库
方法一
使用Trie树，Trie树快速存储和查找字符串集合的一种数据结构
一般字符串集里的字符都是全小写、全大写或全数字
一般会在一个单词结尾的位置打上标记
查询时不仅要看这个单词能否走完，还要看走完时有没有标记
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx; // 下标是0的点，既是根节点，也是空结点
char str[N];
void insert(char str[])
{
int p = 0;
for(int i = 0;str[i] != '\0';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] != '\0';i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0; // 如果没有这个子节点返回0
p = son[p][u]; // 若有这个子节点则移动到子节点
}
return cnt[p]; // 返回以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;
}son --- 存每个结点的子节点，因为这道题里面字符串都是小写字母，所以每个字母最多向外延申26条边
cnt --- 以当前字母结尾的单词有几个
0是根节点，一个结点没有下一个结点也会让其下一个为0
方法二
使用map
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
int n;scanf("%d", &n);
map<string, int> mp;
while(n--)
{
char ch;
string s;
cin>>ch>>s;
if(ch == 'I')
{
int x = mp.count(s);
if(x == 0) mp.insert({s, 1});
else mp[s]++;
}
else
{
int x = mp.count(s);
if(x == 0) cout<<x<<endl;
else cout<<mp[s]<<endl;
}
}
return 0;
}9、并查集
并查集主要能够完成两个操作：
1. 将两个集合合并
2. 询问两个元素是否在一个集合当中
通过并查集完成这两个操作可以将时间复杂度控制在近乎O(1)
基本原理：每个集合用一颗树存储。树根的编号就是这颗树的编号。每个结点存储它的父结点，p[x]表示x的父结点。
问题一：如何判断一个结点是否是树根：if(p[x] == x)，结果为真就是树根
问题二：如何求x所在集合编号：while(p[x] != x) x = p[x]; 先看一下这个点的父结点是否是根，若不是则一直往上找，直到找到根，根的编号就是集合的编号
问题三：如何合并两个集合：px、py分别是x、y的集合编号。p[px] = py。合并两个集合，实际上就是将一个集合变成另一个集合的子树，这里就是将x所在集合变成y所在集合的子树。
此时将两个集合合并的时间复杂度是O(1)，但是询问两个元素是否在一个集合中的时间复杂度并不是O(1)，所以此时需要进行路径压缩优化
路径压缩：当找一个点的祖先时，直接将这个点以及这个点到祖先路径上的所有点都指向根
这样在下一次寻找路径上的点时，就能做到O(1)的时间复杂度了
9.1 合并集合
836. 合并集合 - AcWing题库
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
int find(int x) // 返回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); // 让a所在集合变成b所在集合的子树
else
{
if(find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}9.2 连通块中点的数量
837. 连通块中点的数量 - AcWing题库
这道题与上一道题是类似的，只是这道题还需要维护每一个集合有几个元素
在a和b之间连一条边就是将a和b所在集合合并，若a和b相等则不进行操作
连通块是指a可以到b，b也可以到a，就说明a和b在一个连通块中，判断a和b是否在一个连通块中，实际上就是判断a和b是否在一个集合中
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N], sz[N]; // sz数组表示的是每一个集合的大小，只保证集合的根节点有意义
int find(int x) // 返回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;
sz[i] = 1;
}
while(m--)
{
char op[5];
int a, b;
scanf("%s", op);
if(op[0] == 'C')
{
scanf("%d%d", &a, &b);
if(find(a) != find(b)) // 只有当a和b在两个不同集合时才进行操作
{
sz[find(b)] += sz[find(a)]; // b集合的大小需要加上a集合的大小
p[find(a)] = find(b); // 将a集合变成b集合的子树
}
}
else if(op[1] == '1')
{
scanf("%d%d", &a, &b);
if(find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
else
{
scanf("%d", &a);
printf("%d\n", sz[find(a)]);
}
}
return 0;
}10、堆
堆主要有5个操作：
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)
5. 修改任意一个元素 heap[k] = x; down(k)或up(k)
这里删除任意一个元素是将这个元素与堆的最后一个元素交换，然后让size--，此时有3种可能性，若不变，则不需要任何操作，若变小了需要向上调整，变大了需要向下调整。为了简便代码，可以不管这些，直接down一遍，再up一遍，最多只会执行一个。修改任意一个元素同理。
注意：堆要从1开始存放数据，若从0，0*2=0
10.1 堆排序
838. 堆排序 - AcWing题库
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], sz;
void down(int u) // u是下标
{
int t = u; // 用t在记录最小的那个数的下标
if(2 * u <= sz && h[2 * u] < h[t]) t = 2 * u;
if(2 * u + 1 <= sz && h[2 * u + 1] < h[t]) t = 2 * u + 1;
if(t != u)
{
swap(h[u], h[t]);
down(t);
}
}
void up(int u) // 这道题不需要用到向上调整法，写在这里只是为了记忆，因为下道题会对down和up进行修改
{
while(u / 2 != 0 && h[u] < h[u / 2])
{
swap(h[u], h[u / 2]);
u /= 2;
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1;i <= n;i++) scanf("%d", &h[i]);
sz = n;
// 使用向下调整法来建堆
for(int i = n / 2;i > 0;i--) down(i);
while(m--)
{
printf("%d ", h[1]);
swap(h[1], h[sz]);
sz--;
down(1);
}
return 0;
}10.2 模拟堆
839. 模拟堆 - AcWing题库
这道题很关键的一个点就是，它是删除、修改第k个插入的数，而我们将元素放进堆后，顺序全被打乱了，根本不知道一个元素是第几个插入的，所以此时就需要使用一个ph数组存放数据，ph[k]表示第k个插入的数在堆中的下标是几。此时仍然是不够的，因为我们现在已经知道了第k个插入的数在堆中的下标是几，但是我们不知道堆中的一个数是第几个插入的，所以还需要有一个hp数组，hp[k]表示下标为k的点是第几个插入的点
我们现在要交换这两个点，不仅仅要交换这两个点的值，还需要交换hp，但是我们此时只知道这两个点在堆中的下标，要如何通过下标去找到ph呢？是没有办法的，所以要有hp，通过hp找到ph，ph也是要交换的。
#include<iostream>
#include<algorithm>
#include <string.h>
using namespace std;
const int N = 1e5 + 10;
int n, m; // m记录是第几个插入的点
int h[N], ph[N], hp[N], cnt; // cnt用来记录当前堆中有几个元素
void heap_swap(int a, int b) // 交换下标为a、b的元素，此时交换就不仅仅交换h[a]、h[b]，还要交换hp、ph
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u) // u是下标
{
int t = u; // 用t在记录最小的那个数的下标
if(2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u;
if(2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
if(t != u)
{
heap_swap(u, t); // 交换的地方都要换
down(t);
}
}
void up(int u) // 这道题不需要用到向上调整法，写在这里只是为了记忆，因为下道题会对down和up进行修改
{
while(u / 2 != 0 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u /= 2;
}
}
int main()
{
int n, m = 0;
scanf("%d", &n);
while (n -- )
{
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I"))
{
scanf("%d", &x);
cnt ++ ;
m ++ ;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, cnt);
cnt -- ;
down(1);
}
else if (!strcmp(op, "D"))
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, cnt);
cnt -- ;
up(k);
down(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
return 0;
}带映射的堆并不常用，但是Dijkstra算法需要用到
11、哈希表
11.1 模拟散列表
840. 模拟散列表 - AcWing题库
哈希表就是能够将数据范围非常庞大的数据，通过哈希函数计算后，映射到一个相对较小的数据范围内的数据结构。如将数据范围在[-10^9, 10^9]的数据通过哈希函数映射到[0, 10^5]内。看起来十分像离散化，实际上离散化是一种特殊的哈希，离散化映射是需要保序的，这里讨论的是一般的哈希。而在将原始数据通过哈希函数映射的过程中，有可能有两个数通过哈希函数映射后的值是相等的，也就是发生了哈希冲突。解决哈希冲突的方法有两种，拉链法和开发寻址法，所以，实现哈希表的方法也有两种
拉链法
一般使用拉链法建立的哈希表只提供两种操作，插入元素和查找元素，不会支持删除元素，若要删除元素也可以，新开一个数组记录一下每个结点的情况，并不会真正的去链表中删除
这里为了避免哈希冲突，取模的数，也就是哈希表中存放链表根节点的数要是一个质数，并且这个质数要离2的整次幂尽可能的远，这样能将哈希冲突降到最低。这道题最多有10^5个数，所以我们先来计算一下比10^5的的第一个质数
int main()
{
for(int i = 100000;;i++)
{
bool flag = true;
for(int j = 2;j * j <= i;j++)
if(i % j == 0)
{
flag = false;
break;
}
if(flag)
{
cout<< i <<endl;
break;
}
}
return 0;
}结果是100003，所以我们哈希表的数组开100003
注意C++中的负数取模结果也是负数，-10 % 3 = -1，所以取模后一定要让数大于0，因为我们开了100003个空间，取模后的结果范围应该在[0, 100003)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx, n; // h数组就是哈希表，h[k] = -1表示这个链表为空，h[k]就是这个链表头结点的下标，就是单链表那一个题的head
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()
{
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)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}开放寻址法
开放寻址法开的数组大小要是数据的2到3倍，删除操作与拉链法类似
这道题的数据范围最大是10^5，所以我们找大于20000的第一个质数
int main()
{
for(int i = 200000;;i++)
{
bool flag = true;
for(int j = 2;j * j <= i;j++)
if(i % j == 0)
{
flag = false;
break;
}
if(flag)
{
cout<< i <<endl;
break;
}
}
return 0;
}结果是200003
开放寻址法重点是定义一个find函数，这个find函数若x在哈希表中，返回x在哈希表中的位置，若不在哈希表中，则返回其应该存储的位置
要定义一个不在数据范围内的数，表示位置没有数
memset是按字节进行赋值的
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 3, null = 0x3f3f3f3f; // 定义null来表示一个位置没有数
int h[N], n;
int find(int x) // 找到了返回x在哈希表中的位置，没找到返回应该放入的位置
{
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x) // 当映射到的位置有值，并且这个值与x不相等时，往后找
{
k++;
if(k == N) k = 0;
}
return k;
}
int main()
{
scanf("%d", &n);
memset(h, 0x3f, sizeof(h)); // 按照字节赋值，0x3f3f3f3f，有4个字节，每个字节都是0x3f
while(n--)
{
char op[2];
int x;
scanf("%s%d", op, &x);
int k = find(x);
if(*op == 'I') h[k] = x;
else
{
if(h[k] == x) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}11.2 字符串哈希
841. 字符串哈希 - AcWing题库
这道题我们可以预处理出一个所有前缀的哈希值,当要比较两个区间的字符串是否相等时,我们只需要比较这两个区间的哈希值是否相等。这里说的哈希值就是每个字符串通过哈希函数映射后的结果
计算字符串所有前缀的哈希值
给的是一个字符串，我们要如何计算出前缀的哈希值呢？
我们采用的方法是将这个字符串看成是一个p进制数，哈希函数就是将p进制数转成十进制数，计算出的十进制数就是哈希值
通常p会取131或13331。因为p比较大，而且字符串可能会非常长，所以需要取模，取模通常取2^64，这样哈希冲突会最低
我们取p=131，来计算一下ABCD所有前缀的哈希值
计算子区间的哈希值
我们现在计算出了这个字符串的所有前缀哈希值，那要如何用这些前缀哈希值去求某一个子区间的哈希值呢？
能使用这种计算方法是因为将字符串ABCD看成p进制数A是高位，D是低位
因为我们上面取模是取的2^64，所以这个哈希表需要用usinged long long来存储，无符号类型可以利用栈溢出来达到取模的效果，所以在代码中并没有取模的操作
#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]; // p数组用来存P的次方，如p[2] = 131 ^ 2
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; // 131 ^ 0 = 1
for (int i = 1; i <= n; i ++ ) // 预处理出前缀和
{
h[i] = h[i - 1] * P + str[i]; // 这里既有大小写也有数字，所以使用ASCII值来计算
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;
}上一篇： [算法] 分割等码和子集码