【题解】数据结构

• 主要内容
  • 链表
  • 哈希表
  • 并查集：在近乎O(1)的情况下，
    • 关键：p[N]初始化，find(int a)：返回a所在集合的编号
    • 合并 两集合
    • 询问 两元素是否在同一集合

链表与邻接表

数组模拟单链表（邻接表）

• 邻接表：常用于存储图和树

AcWing826 单链表（模板题）

• 一般来说，如果想删除链表第一个节点，会说“删除头结点”，如果想删除整个链表，会直接说“删除整个链表”~ head是指向头结点的指针，它本身是不存节点的，只是指向了整个链表的第一个节点。
• 初始化：head=-1；idx=0；
• 头插法：赋值、指向当前head的next、更新head，idx++
• 插到指定位置k后面：赋值，更新next
• 删除位置k的元素：将k的next指向k的next的next

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
//head=头结点下标
//e[i]:节点i的值
//ne[i]:节点i的下一个的坐标
//idx:指向当前即将处理的点的坐标 
int head,e[N],ne[N],idx;

//初始化
void init(){
	head=-1;
	idx=0;
} 
//将x插入到头节点
void add_to_head(int x){
	e[idx]=x,ne[idx]=head,head=idx,idx++;
} 
//将x插到下标是k的点的后面
void add(int k,int x){
	e[idx]=x,ne[idx]=ne[k],ne[k]=idx,idx++;
} 
//将下标是k的点后面的点删掉
void remove(int k){
	ne[k]=ne[ne[k]];
} 

int main(){
	ios::sync_with_stdio(false);
	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==0) 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]<<' ';
}

数组模拟双链表

• 双链表：用来优化某些题

827. 双链表 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int l[M],r[M],e[M],idx;
void init(){
	r[0]=1;l[1]=0;idx=2; //0左边界、1右边界
}
void insert(int k,int v){//第k个插入的数后面插入v
	e[idx]=v;
	l[idx]=k,r[idx]=r[k];
	l[r[k]]=idx,r[k]=idx;
	idx++;
}
void remove(int k){
	l[r[k]]=l[k];
	r[l[k]]=r[k];
}
int main(){
	int m;cin>>m;
	init();
	while(m--){
		string s;int k,x; cin>>s;
		if(s=="L"){
			cin>>x; insert(0,x);
		}else if(s=="R"){
			cin>>x; insert(l[1],x);
		}else if(s=="D"){
			cin>>k; remove(k+1);
		}else if(s=="IL"){
			cin>>k>>x; insert(l[k+1],x);
		}else{
			cin>>k>>x; insert(k+1,x);  //k-1+2
		}
	}
	for(int i=r[0];i!=1;i=r[i])  //遍历
		cout<<e[i]<<' ';
}

栈和队列

数组模拟栈

#include <iostream>
using namespace std;
const int N = 100010;
int st[N], top = -1;
int n;
int main(){
    cin >> n;
    while(n--){
        string s; cin >> s;
        if(s == "push"){
            int a; cin >> a;
            st[++top] = a;
        }
        if(s == "pop") top --;
        if(s == "query") cout << st[top] << endl;
        if(s == "empty") cout << (top == -1 ? "YES" : "NO") << endl;
    }
}

数组模拟队列

#include <iostream>
using namespace std;
const int N = 100010;
int m;
int q[N], hh, tt = -1;
int main(){
    cin >> m;
    while (m -- ){
        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;
}

单调栈

830. 单调栈 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
stack<int>stk;
int main(){
	int n;cin>>n;
	while(n--){
		int x;cin>>x;
		while(stk.size()&&stk.top()>=x) stk.pop();
		if(!stk.size()) cout<<"-1"<<' ';
		else{
			cout<<stk.top()<<' ';
		}
		stk.push(x);
	}
} 

单调队列

求滑动窗口的max、min

154. 滑动窗口 - AcWing题库

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];
//q存储的是下标不是值 
int hh,tt=-1;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n,k;cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
	//min
	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) cout<<a[q[hh]]<<' '; 
	}
	cout<<endl;
    //max
	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) cout<<a[q[hh]]<<' '; 
	}
}

KMP

哈希表

用到哈希表的情况：把一个大的空间映射到一个小的空间

基础知识

• 存储结构
  • 开放寻址法
  • 拉链法：开一个一维数组，存储所有的哈希值
• 字符串哈希方式

离散化可以看成是一种特殊的哈希，之前的那个离散化要保证顺序

AcWing 840 模拟散列表

题意

维护一个集合，支持下列操作：

• lx： 插入一个数
• Qx：询问x是否在集合中出现过

对于N次操作，输出询问结果

思路

• N行：N个操作，虽然-10^9 <= x <= 10^9 但是，N最大取到10^5，所以实际只涉及10^5个数；

• 题目操作只有插入和查询而已，没有说要插入到哪个位置，而只是插入到了一个无序的集合中，并且没有顺序要求。

• 对于插入操作，我们可以把要插入的每个数存到一个哈希表里里面

• x mod 10^5

  • 一般来说，取模的这个数要是质数，且离2的整数次幂远
  • 因此确定数组大小后，首先找一个大于最大数据范围的一个质数

  //找第一个大于dest的质数 
  for(int i=dest;;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;
      }
  }

• 冲突：把两个不一样的数映射成同一个数；处理冲突：开放寻址or拉链法

• 拉链法：开一个一维数组；每个位置可以看成一个槽，存储当前槽上已有的数；

  • 期望算法，每条链（单链表）的长度可以看成常数；一般哈希表的算法题只有添加和查找操作，没有删除操作；如果要实现删除，并不是真的删掉，而是打一个标记

  

代码(拉链法)

#include<bits/stdc++.h>
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--){
		//要读如字符，但用的是scanf的话尽量读入的是一个字符串
		//因为这样scanf会自动把空格、回车等给忽略掉 
		//降低出错的概率 
		char op[2];
		int x;
		scanf("%s%d",op,&x);
		if(*op=='I') insert(x);
		else{
			if(find(x)) puts("Yes");
			else puts("No");
		} 
	}
}

代码（开放寻址法比较nice）

开放寻址法：只开一个一维数组，开到题目数据范围的2-3倍（首先要找到这个大于最大数据范围的一个质数）

#include<bits/stdc++.h>
using namespace std; 
const int N=200003,null=0x3f3f3f3f;
int h[N];
int find(int x){
	//将x映射到数组下标内 
	int k=(x%N+N)%N;//如果是负数 那取模也是负的 所以 加N 再 %N 就一定是一个正数
	//如果不存在，则返回的是它应该存储的位置 
	while(h[k]!=null&&h[k]!=x){
        //如果当前数组已经放了数据且数据不等于x
		//就一直往后找 
		k++;
		if(k==N) k=0;
	}
	//如果x在哈希表中已经存在，则返回x所在的位置
	return k;
}
int main(){
	int n; 
	scanf("%d",&n);
	memset(h,0x3f,sizeof h);
	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]!=null) puts("Yes");
			else puts("No");
		}
	}
}

AcWing 841 字符串哈希