本篇有单链表，双链表，栈，队列，单调栈，单调队列，KMP，Trie，并查集，堆，哈希表，C++STL的内容~
以下都是依据其数据结构课所整理的笔记
单链表：
实现一个单链表，链表初始为空，支持三种操作：
(1) 向链表头插入一个数；
(2) 删除第k个插入的数后面的数；
(3) 在第k个插入的数后插入一个数
现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。
输入格式
第一行包含整数M，表示操作次数。
接下来M行，每行包含一个操作命令，操作命令可能为以下几种：
(1) “H x”，表示向链表头插入一个数x。
(2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。
(3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例：
6 4 6 5
记得复习注释哦~:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int head;//定义一个头节点
int e[N];//存储i节点的值
int ne[N];//存储第i个的下一个节点
int idx;//下一个结点是啥呀~/目前已经用到了哪个点
//初始化操作
void init(){
head=-1;
idx=0;
}
//头插入x
void add_head(int x){
e[idx]=x;
ne[idx]=head;
head=idx++;
}
//将x插到下标是k的点后面
void insert(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 n;
cin>>n;
init();
while(n--){
char op;
int x,k;
cin>>op;
if(op=='H'){
cin>>x;
add_head(x);
}
else if(op=='I'){
cin>>k>>x;
insert(k-1,x);
}
else{
cin>>k;
if(!k) head=ne[head];
else remove(k-1);
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
双链表：
双链表的有两个索引指针，l和r。
那么这里只需要-->int e[N], l[N], r[N], idx;
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
int main()
{
cin >> m;
// 0是左端点，1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
while (m -- )
{
string op;
cin >> op;
int k, x;
if (op == "L")
{
cin >> x;
insert(0, x);
}
else if (op == "R")
{
cin >> x;
insert(l[1], x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1);
}
else if (op == "IL")
{
cin >> k >> x;
insert(l[k + 1], x);
}
else
{
cin >> k >> x;
insert(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
模拟栈：
实现一个栈，栈初始为空，支持四种操作：
(1) “push x” – 向栈顶插入一个数x；
(2) “pop” – 从栈顶弹出一个数；
(3) “empty” – 判断栈是否为空；
(4) “query” – 查询栈顶元素。
现在要对栈进行M个操作，其中的每个操作3和操作4都要输出相应的结果。
输入格式
第一行包含整数M，表示操作次数。
接下来M行，每行包含一个操作命令，操作命令为”push x”，”pop”，”empty”，”query”中的一种。
输出格式
对于每个”empty”和”query”操作都要输出一个查询结果，每个结果占一行。
其中，”empty”操作的查询结果为“YES”或“NO”，”query”操作的查询结果为一个整数，表示栈顶元素的值。
数据范围
1≤M≤100000 ,
1≤x≤109
所有操作保证合法。
输入样例：
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
输出样例：
5
5
YES
4
NO
记得复习注释哦~：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100010;
int stk[N];//模拟栈
int tt;//栈顶~
//模拟栈tt要从下标为1开始存，目的就是在tt为零的时候方便判空
int main(){
int n;
cin>>n;
while(n--){
string op;
int x;
cin>>op;
if(op=="push"){
cin>>x;
stk[++tt]=x;
}
else if(op=="pop"){
tt--;
}
else if(op=="empty"){
cout<<(tt?"NO":"YES")<<endl;
}
else cout<<stk[tt]<<endl;
}
return 0;
}
模拟队列：
int q[N], hh, tt = -1;
hh指向头的指针，tt指向尾巴的指针；
当hh>tt的时候表示队列为空队列；
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int q[N],hh,tt=-1;
int main(){
int n;
cin>>n;
while(n--){
string op;
int x;
cin>>op;
if(op=="push"){
cin>>x;
q[++tt]=x;
}
else if(op=="pop"){
hh++;
}
else if(op=="empty"){
cout<<(hh<=tt?"NO":"YES")<<endl;
}
else{
cout<<q[hh]<<endl;
}
}
return 0;
}
单调栈 ：
给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。
输入格式
第一行包含整数N，表示数列长度。
第二行包含N个整数，表示整数数列。
输出格式
共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
注意模拟栈的时候，tt=0的时候，栈为空。
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N],tt;
int main(){
int n;
scanf("%d",&n);
while(n--){
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;
}
单调队列：
这类题型的经典就是滑动窗口，这里需要运用到双向队列 #include <deque>
但是我们这里用本期所写的数组模拟队列的方式来写
单调队列里一般存的是下标，因为要判断队头元素是否已经不在窗口内了，这里的窗口是指以当前元素为右端点的，给定长度的一段。
重要的事情说三遍：
单调队列里一般存的是下标
单调队列里一般存的是下标
单调队列里一般存的是下标
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1008010;
int q[N],hh,tt=-1;
int a[N];
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++){
if(hh<=tt&&i-q[hh]==k) hh++;
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-q[hh]==k) hh++;
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) printf("%d ",a[q[hh]]);
}
return 0;
}
KMP算法：
https://www.bilibili.com/video/BV1jb411V78H?from=search&seid=3229400042356758421
#include <iostream>
using namespace std;
const int N = 100100, M = 100010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
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];
}
}
return 0;
}
Trie树：
非常非常简单的数据结构~
高效的存储和查找字符串集合的数据结构
模板题：
Trie字符串统计
维护一个字符串集合，支持两种操作：
“I x”向集合中插入一个字符串x；
“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入格式
第一行包含整数N，表示操作数。
接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。
输出格式
对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1
用scanf读入%c的时候注意他不会过滤回车
在网上看到一个大佬解释son[N][26]很**形象了，展示一下~
关于理解int son[N][26] 这个二维数组的心得
Tire树本质上一个多叉树，最多可以分多少叉呢？因为此题存的都是小写字母，所以是26叉；
这里就解释了son这个二维数组的第二维的含义，就是他最多有26个孩子，那么他是谁呢，他当然是结点了，那结点之间怎么区分，或者这些孩子的爸爸叫啥，爸爸们用下标来区别，所以第一维就是爸爸们的id，son[0][1]含义就是0号爸爸有个儿子b ，那son[0][1] = 2，就是0号爸爸有个儿子b，儿子的id是2； 这些id就是由idx` 来赋值的；
idx可以理解为计划生育的管理局的给上户口的，生一个孩子，给孩子上身份证，证件上ID 为++idx ，而孩子叫啥，其实就是26个小写字母中的其中一个了；
对于每个结点而言，可以知道他有没有这个孩子，有的话叫啥，在哪里；
对于查询，从根节点一路查下来，就可以找到某个字符串在不在；
对于插入字符串，也是一路下来，看有没有这个儿子，没有了给你生个儿子，有了继续给下面找，所以只插入该字符串中原来不存在的字符即可； 也就是利用了公共前缀来降低查询时间的开销以达到提高效率的目的~
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
const int N = 100010;
int son[N][26];
int cnt[N];//打标记
int idx;
char str[N];
void insert(char str[]){
int p=0;
for(int i=0;str[i];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];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可以过滤上一行回车
scanf("%s%s",op,str);
if(op[0]=='I') insert(str);
else printf("%d\n",query(str));
}
return 0;
}
并查集：
代码短。思路精巧。笔试，竞赛常用算法~
两个操作：
1.将两个集合合并
2.询问两个元素是否在一个集合中
操作方法： 用树的形式来维护每个集合。
1.树根的编号就是整个集合的编号
2.每个节点存储他的父亲节点 p[x]表示x的父亲节点
问题一：如何判断树根？
ANS:if(p[x]==x)那就是树根。
问题二：如何求x的集合编号？
ANS：while(p[x]!=x) x=p[x]；这样最后一直往上走，就能找到树根（集合编号）有优化---->问题四。
问题三：如何合并两个集合？
ANS：假设px是x的集合编号，py是y的集合编号---->p[x]=y即可
问题四：如何优化问题二？
ANS：路径压缩，直接让x的父亲节点=x的根节点
以下是并查集最核心的操作：
int p[N];
int find(int x){//查找x的祖宗节点+路径压缩
if(p[x]!=x) p[x]=find(p[x]);//让x的父亲节点直接等于根节点
return p[x];
}
模板题：
836. 合并集合
一共有n个数，编号是1~n，最开始每个数各自在一个集合中。
现在要进行m个操作，操作共有两种：
“M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
“Q a b”，询问编号为a和b的两个数是否在同一个集合中；
输入格式
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种。
输出格式
对于每个询问指令”Q a b”，都要输出一个结果，如果a和b在同一集合内，则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
一定要注意这一点：int find(int x)//查找x的祖宗节点+路径压缩 ，操作的重点就是让x的父亲节点直接等于根节点，注意看代码第13行
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int p[N];
int find(int x){//查找x的祖宗节点+路径压缩
if(p[x]!=x) p[x]=find(p[x]);//让x的父亲节点直接等于根节点
return p[x];
}
int main(){
int n,m;
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;
}
我们还可以利用并查集的性质查找一个集合中的一些变量，利用并查集来维护一些信息,比如利用根节点去存储每一个集合的数量有多少
连通块中 点的数量
给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。
现在要进行m个操作，操作共有三种：
“C a b”，在点a和点b之间连一条边，a和b可能相等；
“Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；
“Q2 a”，询问点a所在连通块中点的数量；
输入格式
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。
输出格式
对于每个询问指令”Q1 a b”，如果a和b在同一个连通块中，则输出“Yes”，否则输出“No”。
对于每个询问指令“Q2 a”，输出一个整数表示点a所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
注意这里的cnt每次只是利用根节点的信息来维护整个集合中元素的个数
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int p[N];
int cnt[N];
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
cnt[i]=1;
p[i]=i;
}
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)) continue;
cnt[find(b)]+=cnt[find(a)];
p[find(a)]=find(b);
}
else if(op[1]=='1'){
scanf("%d%d",&a,&b);
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
else if(op[1]=='2'){
scanf("%d%d",&a);
printf("%d\n",cnt[find(a)]);
}
}
return 0;
}
堆：
堆是一颗完全二叉树！
完全二叉树：除了最后一层节点外，上面任何一个节点都不是空的，最后一层节点是从左到右依次排列的
如何手写一个堆？
要做的操作：
1.插入一个数
2.求这个集合中的最小值
3.删除最小值
（STL中不能直接实现的功能）我们还可以做到：
1.删除任意一个元素
2.修改任意一个元素
以小根堆为例
基本性质：每个点都小于等于左右儿子因此--->根节点是这个堆最小值
STL中的优先队列呀
堆的存储
全新的存储方式：用一维数组去存~
操作
有基本两个操作：up down
heap[N]表示堆，up,down,size为下标指针
down:
void down(int u){
int t=u;
if((u<<1) <=cnt && h[t]>h[u<<1]) t=(u<<1);
if((u<<1)+1<=cnt && h[t]>h[(u<<1)+1]) t=(u<<1)+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
模板题：
堆排序
输入一个长度为n的整数数列，从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数，表示整数数列。
输出格式
共一行，包含m个整数，表示整数数列中前m小的数。
数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
注意位运算符优先级低于+，因此要加括号！当然用*写更好~
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N];
int cnt;
void down(int u){
int t=u;
if((u<<1) <=cnt && h[t]>h[u<<1]) t=(u<<1);
if((u<<1)+1<=cnt && h[t]>h[(u<<1)+1]) t=(u<<1)+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
cnt=n;
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
for(int i=n/2;i;i--) down(i);//建堆
while(m--){
printf("%d ",h[1]);
h[1]=h[cnt--];
down(1);
}
return 0;
}
模拟堆（迪杰斯特拉可利用堆优化）
在模拟堆的时候有个操作时删除第k个插入的数~那么这里就需要再开两个数组
ph[N]和hp[N]来记录一些信息:
重点：ph[k]表示第k个插入的节点在堆中的下标，hp[k]表示堆中第k个节点是第几个插入的数。
首先搞清楚这些问题；
1.ph,hp是啥？
ANS:hp是heap pointer的缩写，表示堆数组中下标到第k个插入的映射
ph是pointer heap的缩写，表示第k个插入到堆数组中的下标的映射
hp和ph数组是互为反函数的
2.为什么会用ph和hp这两个数组呢？
ANS：首先用PH的原因在于在删除第k个插入元素的操作中，我们首先得知道第k个插入元素在堆数组中的什么位置，即堆数组下标是啥。
很显然，用一个ph数组来存储会方便查找。这样我们就知道了第k个插入的元素在哪了。然后我们需要做的是和堆尾元素交换，最后再在原来第k个元素所在的位置进行down和up操作。
由于交换完后ph[k]的值变了，为ph[size]了，所以必须要在之前保存ph[k]的值，不然无法进行down和up操作。
其次用HP的原因在于在swap操作中我们输入是堆数组的下标，无法知道每个堆数组的下标对应的是第几个插入的元素。
所以需要hp数组方便查找~
模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
“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”，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
注意swap的运用~
这里要将ph,hp充分理解再去写heap_swap哦~
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int cnt,h[N],ph[N],hp[N];
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/2]>h[u]){
heap_swap(u/2,u);//注意这里和第21行代码一样传递的是这两节点在堆中的下标
u/=2;
}
}
int main(){
int n,m=0;
scanf("%d",&n);
while(n--){
char op[10];
int k,x;
scanf("%s",op);
if(!strcmp(op,"I")){
scanf("%d",&x);
m++;
cnt++;
ph[m]=cnt;//第m个插入的数，在堆中的下标为cnt
hp[cnt]=m;//在堆中下标为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--;
down(k);
up(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
return 0;
}
哈希表：
什么情况下要用到哈希表？
将一个庞大的空间，或者是值域，映射到0~N（N在10的五次方到10的六次方以内)
存储方式：
1.开放寻址法（常用）
2.拉链法
操作方法：
(1)拉链法：
开一个一维数组为N个坑并且每个坑下再拉一个链表~：输入一个数 然后mod 一个N(数组长度，即多少个坑)，取利用for（）循环找一个大于数据范围，尽可能大的质数因为------>首先N如果小于10000的话，可能存在“坑多人少”的情况，就死循环了。然后取模的数是质数，冲突的概率会低一些，否则如果N是合数，比如是2的倍数，那么所有被2整除的数就不会被分到奇数位置上，分散的程度会变低，冲突概率就会变大。所以，我们要利用代码求大于数据范围的第一个质数，例如大于100000的第一个质数~
如果~有取得mod之后，余数相同，那么在这坑下面拉一条链。
(2)开放寻址法：
只开一个一维数组，不拉链表。一维数组的大小，从经验上来说，要开到题目所给数据范围的2--3倍。
然后利用for()循环和拉链法一开始找N一样，找一个最小的质数
x mod N 找到一个坑位，如果这个坑位有人，去++看下一个坑位，一直找到没人的坑位就放进去。
除此之外
开放寻址法要约定一个数字来表示若这一点等于这个数，则表示这个坑位没人。那么我们用nulll=0X3f3f3f3f来表示一个无穷大的数字，这个数字大于10的9次方，通常不会在数据范围内。
核心操作：
就是find,意思是找找看，如果x在哈希表中已经存在的话，返回的是他在哈希表中的位置，否则的话，返回的是他应该存储的位置：
int find(int x){
int k=(x%N+N)%N;
while( h[k]!=null && h[k]!=x ){
k++;
if(k==N){
k=0;
}
}
return k;
}
840. 模拟散列表
维护一个集合，支持如下几种操作：
“I x”，插入一个数x；
“Q x”，询问数x是否在集合中出现过；
现在要进行N次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数N，表示操作数量。
接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。
输出格式
对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤10
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No
拉链法：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003;
int e[N],h[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 m;
scanf("%d",&m);
memset(h,-1,sizeof h);
while(m--){
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0]=='I') insert(x);
else{
if(find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
开放寻址法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200003, null=0x3f3f3f3f;
int h[N];
int find(int x){
int k=(x%N+N)%N;
while(h[k]!=null && h[k]!=x){
k++;
if(k==N) k=0;
}
return k;
}
int main(){
int m;
scanf("%d",&m);
memset(h,0x3f,sizeof h);
while(m--){
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0]=='I') h[find(x)]=x;
else {
if(h[find(x)]!=null) puts("Yes");
else puts("No");
}
}
return 0;
}
字符串哈希：
字符串前缀哈希法
（1）把字符串看成一个P进制的数，字符串有10个字母的话，就看成10位
（2）把P进制的数转换位10进制的数，最高位乘以P的-1次幂
（3）将整个数mod一个Q
通过这样一个方式我们可以将任何一个字符串映射到0~Q-1之间的一个数
注意事项：
（1）不能把某个字母映射成数字0!
（2）假定人品足够好！不存在重复！即不存在映射成同一个值~
方法：我们有经验值-->当P=131或者1331，Q=2的64次方的时候（或者用ULL开数组），就99.99%的情况下，则不会出现冲突!
（3）计算出来的字串的值用typedef unsigned long long ULL;的数组存
由于前缀值的值会很大 所以应该将数组中的数据定义为ULL型，在C++里溢出等价于取模。
那么这样我们就可以利用一个公式算出所有子串的哈希值。
下面这步其实是将h[l-1]左移
其目的事实上是为了将h[l-1]的高位与h[r]相对齐从而才可以未完成计算~
ULL get(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
模板题：
841. 字符串哈希
给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数n和m，表示字符串长度和询问次数。
第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。
接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从1开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P=131;
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(){
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",str+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;
}
当我们要快速判断两个字符串是否相等的时候，就可以用这个做法~
哈希只需要O（1)的时间
除了求一个字符串的循环节哈希不能做，要用KMP算法，其余所有子串问题哈希吊打所有~
