zhangas

Pay more attention

0%

数据结构基础

Posted on Edited on

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int e[maxn],ne[maxn];
//e指的是当前节点的值 而ne指的是当前节点的下一个节点的指针
int head,idx;
//head表示头节点的下标 而idx是当前节已经用到了那个点
void init(){
	head=-1;
	idx=0;
}//初始化
void add_to_head(int x){
	e[idx]=x;
	ne[idx]=head;
	head=idx;
	idx++;
}//在头节点插入值为x的节点
void add(int k,int x){
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx;
	idx++;
}//在第k个节点的后面插入值为x的节点
void remove(int k){
	ne[k]=ne[ne[k]];
}//删去第k个节点

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int idx;
int e[maxn],l[maxn],r[maxn];//e是当前节点的值 l是上一节点的指针 r是下一节点的指针
void init(){//初始化
	r[0]=1;//左边界
	l[1]=0;//右边界
	idx=2;//0 1 两个节点已经被使用

}
void add(int k,int x){//在第k个节点后插入值为x的节点
	e[idx]=x;
	r[idx]=r[k];
	l[idx]=k;

	l[r[k]]=idx;
	r[k]=idx;
	idx++;
}//若实现在第k个节点的前面插入 相当于在第k个节点前面的节点后面插入值为x的节点
void del(int k){//删除第k个节点
	r[l[k]]=r[k];
	l[r[k]]=l[k;]
}

调用函数

1
2
add(r[0],x);//在链表的最左端插入值为x的节点 
add(l[1],x);//在链表的最右端插入值为x的节点

模拟栈

栈顶插入 栈顶弹出 判断是否为空 查询栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int stk[maxn];
int tt=0;
void push(int x){
	stk[++tt]=x;
}
void pop(){
	--tt;
}
bool empty(){
	return tt>0?false:true;
}
int query(){
	return stk[tt];
}

模拟队列

队尾插入 队头弹出 判断是否为空 查询队头元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int q[maxn];
int tt=-1,hh=0;
void push(int x){
	q[++tt]=x;
}
void pop(){
	hh++;
}
bool empty(){
	return hh>tt?false:true;
}
int query(){
	return q[hh];
}

单调栈

输出左侧第一个比当前数字小的数 没有输出-1

1
2
3
4
const int maxn=1e5+10;
int stk[maxn];
int tt=0;
int n,x;

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=0;i<n;i++){
		cin>>x;
		while(tt&&stk[tt]>=x){//栈不空且栈顶比不比x小
			tt- -;//栈顶出栈
		}
		if(tt){
			cout<<stk[tt]<<" ";
		}
		else{
			cout<<"-1 ";
		}
		stk[++tt]=x;//x入栈
	}

单调队列

有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边且每次向右移动一个位置,分别输出窗口的最大值和最小值.
初始化并读入到a[]中

1
2
3
4
5
6
7
const int maxn=1e6+10;
int a[maxn],q[maxn];
int tt=-1,hh=0;

for(int i=0;i<n;i++){
    	cin>>a[i];
    }

求最小值

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<n;i++){//i指向窗口的末端
    	if(hh<=tt&&i-q[hh]+1>k){//队列不为空且滑动窗口的大小>k
    		hh++;
		}
    	while(hh<=tt&&a[q[tt]]>=a[i]){
    		tt--;
		}
		q[++tt]=i;
		if(i>=k-1){
			cout<<a[q[hh]]<<" ";
		}
    }

求最大值

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=0;i<n;i++){//i指向窗口的末端
    	if(hh<=tt&&i-q[hh]+1>k){//队列不为空且滑动窗口的大小>k
    		hh++;
		}
    	while(hh<=tt&&a[q[tt]]<=a[i]){
    		tt--;
		}
		q[++tt]=i;
		if(i>=k-1){
			cout<<a[q[hh]]<<" ";
		}
    }

KMP字符串匹配

初始化并输入

1
2
3
4
5
6
const int N=1e5+10,M=1e6+10;
char p[N],s[M];//p是子串 s是母串 
int ne[N];//next
int n,m;

cin>>n>>p+1>>m>>s+1;

求next[]

1
2
3
4
5
6
7
8
9
10
ne[1]=0;
for(int i=2,j=0;p[i];i++){
	while(j&&p[i]!=p[j+1]){
		j=ne[j];
	}
	if(p[i]==p[j+1]){
		j++;
	}
	ne[i]=j;
}

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1,j=0;s[i];i++){
		while(j&&s[i]!=p[j+1]){
			j=ne[j];
		}
		if(s[i]==p[j+1]){
			j++;
		}
		if(j==n){//匹配成功时 i在字符串s上对应串p的末尾 
			cout<<i-n<<" ";//输出的是数组的初位置 不需要+1
			j=ne[j];
		}
	}

Trie字符串统计

I x 向集合中插入一个字符串 x
Q x 询问一个字符串在集合中出现了多少次
初始化

1
2
3
4
const int maxn=1e5+10;
int son[maxn][26],cnt[maxn];//son[]子节点 cnt[]统计一个串出现了多少次
int idx=0;//表示用到了第几个节点
char op[2];//操作符的读入

插入操作

1
2
3
4
5
6
7
8
9
10
11
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]++;//计算串的出现次数
}

查找操作

1
2
3
4
5
6
7
8
9
10
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;//找不到子节点直接返回0
		}
	}
	return cnt[p];
}

主函数

1
2
3
4
5
6
7
8
9
10
11
int n;
cin>>n;
while(n--){
	cin>>op>>str;
	if(op[0]=='I'){
		insert(str);
	}
	if(op[0]=='Q'){
		cout<<query(str)<<endl;
	}
}

并查集

①讲两个集合合并
②询问两个集合是否在一个集合当中

基本原理:每个集合用一棵树来表示.树根的标号就是整个集合的编号.每个节点存储它的父节点.p[x]表示 x 的父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//初始化
for(int i=1;i<=n;i++){
	fa[i]=i;//让i的父节点指向i
}
//判断树根
if(p[x]==x){

}
//求x的集合编号
while(p[x]!=x){
	x=p[x];
}
//路程压缩优化
int find(int x){//查询x的属于哪个集合 (返回x的根节点)
	if(p[x]!=x){
		p[x]=find(p[x]);//路径压缩 路径上所有的点都指向树根
	}
	return p[x];
}
//合并两个集合 px是a的集合编号 py是b的集合编号
px=find(x);
py=find(y);
p[px]=py;//让a的根节点的父节点指向b的根节点

模拟堆

① I x 插入一个数 x;
② PM 输出当前集合中的最小值;(输出堆顶 h[1])
③ DM 删除当前集合中的最小值(数据保证此时的最小值唯一);
④ D k 删除第 k 个插入的数;
⑤ C k x 修改第 k 个插入的数,将其变为 x;

预处理

1
2
3
4
5
6
7
int n;
int siz;//堆的末尾
int m;//记录使用节点个数
int k,x;//输入第k个插入的数字 x存储这个数字
int h[N];//存储节点
int ph[N],hp[N];//ph指向第i个插入的数的下标x 插入序数映射到堆的下标 
//hp指向下标是x的数是第i个插入的数 由堆的下标映射到插入序数
1
2
3
4
5
void heap_swap(int a,int b){//堆排列特有的交换方式
	swap(ph[hp[a]],ph[hp[b]]);
	swap(hp[a],hp[b]);
	swap(h[a],h[b]);
}

两个堆的排序函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void down(int u){//u是节点的序号 寻找三个节点中最小的节点
	int t=u;
	if(u*2<=siz&&h[u*2]>h[t]){//未出界 且满足比子节点大 
		t=u*2;
	}
	if(u*2+1<=siz&&h[u*2+1]>h[t]){
		t=u*2+1;
	}
	if(t!=u){
		heap_swap(u,t);
		down(t);
		
	}
	return;
}
void up(int u){//交换比u大的父节点
	while(u/2>=1&&h[u/2]>h[u]){
		heap_swap(u,u/2);
		u/=2;
	}
	return;
}

操作实现

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
if(!strcmp(op,"I")){//插入数x
	cin>>x;
	m++;siz++;
	ph[m]=siz;hp[siz]=m;
	h[siz]=x;
	up(siz);
}
else if(!strcmp(op,"DM")){//删除堆顶
	heap_swap(1,siz);
	siz--;
	up(1);
	down(1);
}
else if(!strcmp(op,"D")){//删除第K的插入的数字
	cin>>k;
	k=ph[k];//在交换的过程中ph[k]会变化 预先存储到k上
	heap_swap(k,siz);
	siz--;
	up(k);
	down(k);
}
else if(!strcmp(op,"C")){//将第k个插入的数改变成x
	cin>>k>>x;
	k=ph[k];//同理
	h[k]=x;
	up(k);
	down(k);

}

哈希表

开放寻址法(蹲坑法)

1
2
3
const int null=0x3f3f3f3f;//极大值1061109567与INT_MAX同一数量级 且不会溢出
const int N=2e5+3;
int h[N];
1
2
3
4
5
6
7
8
9
10
int find(int x){//哈希表特有的搜索函数
	int k=(x%N+N)%N;
	while(h[k]!=null&&h[k]!=x){
		k++;
		if(k==N){//搜到了最后一个槽也是满的 让k回到头节点
			k=0;
		}
	}
	return k;//返回x在哈希表中的位置 若不存在返回null
}
1
2
3
4
5
6
7
8
9
10
11
12
memset(h,0x3f,sizeof(h));
//插入x操作
int k=find(x);
h[k]=x;
//查询x操作
int k=find(x);
if(h[k]!=null){
	puts("Yes");
}
else{
	puts("No");
}

拉链法

1
2
3
const int N=2e5+3;
int h[N];
int e[N],ne[N],idx;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insert(int x){
	int k=(x%N+N)%N;//负数取模还是负数 会导致数组越界 (+N)%N 避免这一问题
	e[idx]=x;
	ne[idx]=k;
	h[k]=idx;
	idx++;
}
bool find(int x){
	int k=(x%N+N)%N;
	for(int i=h[k];i!=-1;i=ne[i]){
		if(e[k]==x){
			return true;
		}
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
memset(h,-1,sizeof(h));//-1表示链表的末尾
if(*op=='I'){
	cin>>x;
	insert(x);
}
else if(*op=='Q'){
	cin>>x;
	if(find(x)){
		puts("Yes");
	}
	else{
		puts("No");
	}
	}
}

字符串哈希

判断一个字符串的两个子区间是否完全相等

1
2
3
4
5
6
7
typedef unsigned long long ULL;
const int N=1e5+5,Q=133;
char str[N];//存储字符串
ULL p[N];//对Q进行预处理
ULL h[N];
int n,m;//n是字符串的长度 m是操作次数
int l1,r1,l2,r2,
1
2
3
ULL get(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];//前缀和计算
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//预处理
cin>>n>>m;
p[0]=1;
for(int i=1;i<=n;i++){
	p[i]=p[i-1]*Q;
	h[i]=h[i-1]*Q+str[i];
}
while(m--){
	cin>>l1>>r1>>l2>>r2;
	if(get(l1,r1)==get(l2,r2)){
		puts("Yes");
	}
	else{
		puts("No");
	}
}