基础数据结构合集¶
约 5238 个字 1007 行代码 13 张图片 预计阅读时间 39 分钟
md
1. 单链表¶
实现一个单链表，链表初始为空，支持三种操作：
向链表头插入一个数；
删除第 k 个插入的数后面的数；
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。
D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
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
我们用-1 表示空指针。
实现一些基本的操作：
(1)初始化
头节点指向-1 表示空节点,idx=0 表示从 0 好节点进行编号。
(2)向头节点后面插入一个新节点
(3)向第 k 个插入的点后面添加一个点同(2)
因为是从 0 号节点进行编号的，所以第 k 个插入的点其实是第 k-1 个点 add(k-1,x);
(4)删除头节点
(5)删除第 k 个插入的点
remove(k-1);
AC 代码
#include<bits/stdc++.h>
#include<string>
using namespace std;
const int N=1e6+10;
int head,e[N],ne[N],idx;
void init()//链表的初始化
{
head=-1;
idx=0;
}
void add_head(int x)//向头节点之后插入一个数
{
e[idx]=x,ne[idx]=head,head=idx++;
}
void add(int k,int x)//向第k个插入的数后面插入一个数
{
e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void de(int k)//删除第k个插入的数
{
ne[k]=ne[ne[k]];
}
void remove()//删除头节点
{
head=ne[head];
}
int main()
{
int t;
scanf("%d",&t);
init();
while(t--){
string op;
int k,x;
cin>>op;
if(op=="H"){
scanf("%d",&x);
add_head(x);
}
else if(op=="D"){
scanf("%d",&k);
if(k==0) remove();
de(k-1);
}
else{
scanf("%d%d",&k,&x);
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i])
cout<<e[i]<<" ";
return 0;
}
2. 双链表¶
实现一个双链表，双链表初始为空，支持 55 种操作：
在最左侧插入一个数；
在最右侧插入一个数；
将第 k 个插入的数删除；
在第 k 个插入的数左侧插入一个数；
在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k 个插入的数删除。
IL k x，表示在第 k 个插入的数左侧插入一个数。
IR k x，表示在第 k 个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例：
8 7 7 3 2 9
双链表类似单链表的操作进行处理，只是每个节点都有两个指针 l[],r[],分别指向前驱和后继。
模板：
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点，1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点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];
}
#include<bits/stdc++.h>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int l[N],r[N],e[N],idx;
void init()
{
r[0]=1;
l[1]=0;
idx=2;
}
void add(int k,int x)
{
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
void remove(int k)
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
init();
int t;
cin>>t;
while(t--)
{
string op;
cin>>op;
int k,x;
if(op=="R")
{
cin>>x;
add(l[1],x);
}
else if(op=="L")
{
cin>>x;
add(0,x);
}
else if(op=="D")
{
cin>>k;
remove(k+1);
}
else if(op=="IL")
{
cin>>k>>x;
add(l[k+1],x);
}
else
{
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])
cout<<e[i]<<" ";
return 0;
}
3. 栈¶
3.1 模拟栈¶
实现一个栈，栈初始为空，支持四种操作：
push x – 向栈顶插入一个数 x；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。
现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。
数据范围
1≤M≤100000,
1≤x≤1e9
所有操作保证合法。
输入样例：
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
输出样例：
5
5
YES
4
NO
栈：后进先出的数据结构。
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{
}
AC 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int stk[N],tt=0;
int main()
{
int t;
cin>>t;
while(t--)
{
string op;
cin>>op;
if(op=="push")
{
int x;
cin>>x;
stk[++tt]=x;
}
else if(op=="pop")
{
tt--;
}
else if(op=="empty")
{
if(tt>0)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
else if(op=="query")
{
cout<<stk[tt]<<endl;
}
}
return 0;
}
4. 队列¶
实现一个队列，队列初始为空，支持四种操作：
push x – 向队尾插入一个数 x；
pop – 从队头弹出一个数；
empty – 判断队列是否为空；
query – 查询队头元素。
现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。
输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。
数据范围
1≤M≤100000,
1≤x≤1e9,
所有操作保证合法。
输入样例：
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
输出样例：
NO
6
YES
4
队列:先进先出。
普通队列
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh <= tt)
{
}
循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh != tt)
{
}
AC 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int q[N],hh=0,tt=-1;
int main()
{
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--){
string op;
cin>>op;
if(op=="push"){
int x;
cin>>x;
q[++tt]=x;
}
else if(op=="pop"){
hh++;
}
else if(op=="empty"){
if(hh<=tt) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
else cout<<q[hh]<<endl;
}
return 0;
}
5. 堆¶
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
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 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && 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] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
5.1 堆排序¶
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤1e5，
1≤ 数列中元素 ≤1e9
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
一、堆的基本概念
堆：是一个完全二叉树。
堆分成两类，小根堆和大根堆。
小根堆：父节点小于等于左右孩子节点；
大根堆：父节点大于等于左右孩子节点。
STL 里面的堆又称为优先队列；
如何手写一个堆？
本篇文章以小根堆为例，实现堆的一些基本的操作。
我们用一维数组来维护一个堆，规定数组的下标从 1 开始，每个下标的左右儿子分别为 2*x，2*x+1；
我们先讲述堆中两个最基本的操作 down(x),up(x)两个操作。
down(x),如果我们修改堆某个节点或者删除某个节点 ，我们就需要用 down 和 up 来维护我们堆中的关系，我们以小根堆为例，如果父节点变大，那么他就要往下沉，因为我们小根堆满足父节点小于等于左右儿子，同理，up 恰好相反，如果父节点变小，它就要和自己的父节点比较，直到满足小根堆的定义为止。
二、堆的基本操作
那么我们就可以用 down 和 up 操作完成堆中最基本的操作：
1.插入一个数
我们插入一个数一般是插入到堆中最后一个数的后面再进行 up 操作。
heap[++size]=x,up(size);
2.求集合当中的最小值
因为是小根堆，我们堆顶元素是最小值。
heap[1];
3.删除最小值
我们需要删除堆顶元素，都是如果直接删除堆顶元素的话，会很麻烦，我们可以用最后一个元素来覆盖堆顶元素，如何进行 down(1)操作。
heap[1]=heap[size];size--;down(1);
4.删除任意一个值
我们类似于删除堆顶元素的操作，我们先用最后一个元素的值覆盖删除元素的值，因为我们不知道覆盖后的元素是变大还是变小了，所有我们需要判断是执行 up 还是 down。
当然我们可以简化：
5.修改任意一个元素
AC 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int h[N],siz;
int n,m;
void down(int u)
{
int t=u;//t存储3个节点中的最小值，开始时假设最小值为父节点
if(2*u<=siz&&h[2*u]<h[t]) t=2*u;//和左儿子比较
if(2*u+1<=siz&&h[2*u+1]<h[t]) t=2*u+1;//和右儿子比较
if(t!=u)
{
swap(h[t],h[u]);
down(t);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>h[i];
siz=n;
for(int i=n/2;i;i--) down(i);
while(m--)
{
cout<<h[1]<<" ";
h[1]=h[siz];
siz--;
down(1);
}
return 0;
}
5.2 模拟堆¶
维护一个集合，初始时集合为空，支持如下几种操作：
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≤1e5
−1e9≤x≤1e9
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
思路：
我们需要维护第 i 个插入的数，则需要再开两个数组维护信息；
AC 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,h[N],ph[N],hp[N],siz;
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(2*u<=siz&&h[2*u]<h[t]) t=2*u;
if(2*u+1<=siz&&h[2*u+1]<h[t]) t=2*u+1;
if(u!=t)
{
heap_swap(t,u);
down(t);
}
}
void up(int u)
{
if(u/2&&h[u/2]>h[u])
{
heap_swap(u/2,u);
up(u/2);
}
}
int main()
{
scanf("%d",&n);
int m=0;
while(n--)
{
string op;
cin>>op;
if(op=="I")
{
int x;
scanf("%d",&x);
m++;
h[++siz]=x;
ph[m]=siz;
hp[siz]=m;
up(siz);
}
else if(op=="PM") printf("%d\n",h[1]);
else if(op=="DM")
{
heap_swap(1,siz);
siz--;
down(1);
}
else if(op=="D")
{
int k;
scanf("%d",&k);
k=ph[k];
heap_swap(k,siz);
siz--;
down(k);
up(k);
}
else
{
int k,x;
scanf("%d%d",&k,&x);
k=ph[k];
h[k]=x;
down(k);
up(k);
}
}
return 0;
}
6. 哈希表¶
(1) 拉链法
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;
}
(2) 开放寻址法
int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
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;
}
1.什么是哈希表？
哈希表就是当范围很大时，我们可以通过哈希表将范围缩小，并快速找出一些数，如数组的下标范围是 1~1000000000，但是其中的数很少，我们可以将其映射为 1~100000，并快速找出，如原本数组下标是 500000，我们可以映射成 50，40....
2.哈希表产生的冲突
我们可以在映射的过程中，把两个数映射成为一个数，这个就是哈希表的冲突。
如何解决冲突？
有两种办法：开放寻址法和链地址法
(1)开放寻址法
我们可以先将 h[]中每个位置上的值初始化成一个很大的数，如何通过除留余数法来找到每个数映射后的地址，如果该位置上有数，那么就继续向下一个位置探测，如果探测到最后一个位置，从第 0 个位置再进行探测。
查找一个数也是类似的，如果这个数待探测的位置上有数，那么就向下一个位置探测，如果最终探测的位置上面的数为很大的数，那么查找失败，哈希表中没有该数。
(2)拉链法
拉链法不同于开放地址法的是，把每个位置看成一个单链表，如果要某个数通过除留余数法算出来的数位置上有数，不用向后探测，只需要用头插法插入到该位置上的单链表上，查找也是如此。
6.1 模拟散列表¶
维护一个集合，支持如下几种操作：
I x，插入一个数 x；
Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 xx 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤1e5
−1e9≤x≤1e9
输入样例：
5
I 1
I 2
I 3
Q 2
Q 5
输出样例：
Yes
No
开放寻址法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=2e5+3;
const int null=0x3f3f3f3f;
int h[N];
int 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()
{
cin>>n;
memset(h,0x3f,sizeof h);
while(n--)
{
string op;
int x;
cin>>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 = 1e5 + 3; // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度
//* 开一个槽 h
int h[N], e[N], ne[N], idx; //邻接表
void insert(int x) {
// c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
bool find(int x) {
//用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
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 n;
int main() {
cin >> n;
memset(h, -1, sizeof h); //将槽先清空 空指针一般用 -1 来表示
while (n--) {
string op;
int x;
cin >> op >> x;
if (op == "I") {
insert(x);
} else {
if (find(x)) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}
6.2 字符串哈希表¶
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1]和 [l2,r2]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从 1 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤1e5
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes
字符串前缀哈希法。
str="ABCADEFGKLM"
预处理出所有字符串的前缀的哈希
h[0]=0
h[1]="A"的哈希值
h[2]="AB"的哈希值
h[3]="ABC"的哈希值
1.如何定义某个前缀的哈希？
把字符串看成 P 进制的数。
如"ABCD"可以看成 P 进制的 1234
转化成十进制的数就是(1*p^3+2*p^2+3*p^1+4*p^0)%Q;
由于结果很大，我们模上 2^64 次方，可以直接用 unsigned long long 来存储，unsigned long long 相当于 2^64,溢出的部分就相当于取模。
注：一般不能映射成 0，比如 A->0,则 AA->00,这样就十分容易产生冲突。
前面的数字哈希会产生冲突，但是这里如果 P 取 131 或者 13331 的话，在 99.99% 的情况下不会产生冲突，则不需要进行处理冲突。
2.好处就是可以快速的求[l,r]子串的哈希值，判断两个子串是否相等。
前缀和公式 h[i+1]=h[i]×P+s[i] i∈[0,n−1] h 为前缀和数组，s 为字符串数组；
区间和公式 h[l,r]=h[r]−h[l−1]×P^(r−l+1)；
#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;
}
7. 树和图的一些预备知识¶
树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边 ab，存储两条有向边 a->b, b->a。
因此我们可以只考虑有向图的存储。
n：点数，m：边数
稀疏图:如果 m 和 n 是一个级别的，用邻接表。
稠密图:如果 m 和 n^2 是一个级别的，用邻接矩阵。
(1) 邻接矩阵：g[a][b] 存储边 a->b，先初始化 g 位正无穷
(2) 邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);//初始化表头
(1) 深度优先遍历
时间复杂度 O(n+m) ，n 表示点数，m 表示边数.
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
(2) 宽度优先遍历
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
7.1 树的深度优先遍历¶
树和图的深度优先遍历的模板：
// 需要标记数组st[N], 遍历节点的每个相邻的便
void dfs(int u) {
st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
dfs(j);
}
}
}
7.1.1 树的重心¶
给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。
接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。
输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤1e5
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4
每次算出他下面的 size 和 n-size 进行比较即可。
AC 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边
int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //表示重心的所有的子树中，最大的子树的结点数目
bool st[N]; //记录节点是否被访问过，访问过则标记为true
//a所对应的单链表中插入b a作为根
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// dfs 框架
/*
void dfs(int u){
st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]) {
dfs(j);
}
}
}
*/
//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
st[u] = true; //标记访问过u节点
int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点
//访问u的每个子节点
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
//因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
if (!st[j]) {
int s = dfs(j); // u节点的单棵子树节点数 如图中的size值
res = max(res, s); // 记录最大联通子图的节点数
sum += s; //以j为根的树 的节点数
}
}
//n-sum 如图中的n-size值，不包括根节点4；
res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
return sum;
}
int main() {
memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
cin >> n; //表示树的结点数
// 题目接下来会输入，n-1行数据，
// 树中是不存在环的，对于有n个节点的树，必定是n-1条边
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a); //无向图
}
dfs(1); //可以任意选定一个节点开始 u<=n
cout << ans << endl;
return 0;
}
7.2 树的广度优先遍历¶
7.2.1 图中点的层次¶
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
数据范围
1≤n,m≤1e5
输入样例：
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e6+10;
//邻接表表示方法
int h[N],e[N*2],ne[N*2],idx;
int n,m;
int d[N];//标记距离1号点的最短距离
bool st[N];//标记访问标志
int q[N];//定义一个队列
//从a->b连接一条边
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
memset(d,-1,sizeof d);
int hh=0,tt=-1;
d[1]=0;
q[++tt]=1;//从1号点开始搜索
st[1]=true;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i])//访问该点的邻接点
{
int j=e[i];
if(!st[j])
{
d[j]=d[t]+1;
q[++tt]=j;
st[j]=true;
}
}
}
return d[n];
}
int main()
{
memset(h,-1,sizeof h);//初始化邻接表头
scanf("%d%d",&n,&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
printf("%d\n",bfs());
return 0;
}
8. 二叉树¶
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int lson[N], rson[N], val[N];
int tot; // 当前节点总数
// 创建新节点
int newNode(int x) {
val[tot] = x;
lson[tot] = rson[tot] = -1; // 初始化左右子节点为空
return tot++; // 返回新节点编号
}
// 插入节点
void insert(int& root, int x) {
if (root == -1) { // 如果树为空，则创建新节点
root = newNode(x);
return;
}
// 根据值大小插入左右子树
if (x < val[root]) insert(lson[root], x);
else insert(rson[root], x);
}
// 中序遍历树
void inorder(int root) {
if (root == -1) return; // 如果节点为空，直接返回
inorder(lson[root]); // 递归遍历左子树
printf("%d ", val[root]); // 输出当前节点值
inorder(rson[root]); // 递归遍历右子树
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 提高输入输出效率
int root = -1; // 初始化树为空
insert(root, 10);
insert(root, 20);
insert(root, 5);
insert(root, 15);
inorder(root); // 输出中序遍历结果
puts("");
return 0;
}
9. Trie¶
9.1 Trie 字符串统计¶
维护一个字符串集合，支持两种操作：
I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N 个操作，所有输入的字符串总长度不超过 1e5，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 xx 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗1e4
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1
一.Trie 树的原理
1.Trie 树的作用
快速地查询某个字符串在集合中出现的次数，高效地存储和查找字符串，时间复杂度可以达到 O(n)。
2.实现思路
类似于树的形式，将字符串存储起来，如果存在以某个字符结尾的字符串，我们就进行标记次数，方便查找字符串出现的次数。
我们把小写字母或者大写字母映射成 0-25 进行创建 Trie 树。
3.各个变量代表的意思
儿子数组 son[p][j]:存储从节点 p 沿着 j 这条边走的子节点。边为 26 个小写的字母(a-z)对应的映射值 0-25，每个节点最多可以有 26 个分支。
例如，son[0][2]=1,son[1][2]=0.
计数数组 cnt[p]:存储以 p 结尾字符串出现的次数。
节点编号 idx：来给节点进行编号。
二.建 Trie 树
1.过程
(1)空的 Trie 树只有一个节点，节点编号为 0.
(2)从根开始进行插入，枚举字符串的每个字符，如果有儿子，p 指针走到儿子，如果没有儿子，先创建儿子，p 指针再走向儿子。
(3).在单词的结尾记录插入的次数。
2.图解过程
3.代码展示
void insert(char str[])
{
int p=0;//从根开始遍历
for(int i=0;str[i];i++)//沿着字符串一直走
{
int j=str[i]-'a';//映射成分支
if(!son[p][j]) son[p][j]=++idx;//如果没有这个节点，创建节点
p=son[p][j];//令p走向该节点
}
cnt[p]++;//记录次字符串出现的次数
}
三.查询 Trie
1.过程
(1).从根开始查询，对字符串进行扫描。
(2).有字符串 str[i]，则走到下一个节点，走到字符串尾，返回插入的次数。
(3).没有字符串 str[i],返回 0.
2.代码展示
int query(char str[])
{
int p=0;//从根开始
for(int i=0;str[i];i++)
{
int j=str[i]-'a';
if(!son[p][j]) return 0;//不存在节点，返回0
p=son[p][j];
}
return cnt[p];//返回字符串的次数
}
AC 代码
9.2 最大异或对¶
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤1e5,
0≤Ai\<2^31,
输入样例：
3
1 2 3
输出样例：
3
1.思路
我们首先考虑遍历枚举的方法，然后通过发现某些性质去优化它。
显然暴力的方法为 O(n2)，会超时。
我们发现异或(^)的性质为二进制表示中，两个数某一位进行异或， 相同为 0，不同为 1，如果二进制 100，我们首先考虑 011，因为只有不同的位时,得到的值才能最大，我们可以用 trie 树从高位往低位存储，如果找某一个数的最大值时，我们应该首先考虑它对于二进制某一位不同的值是否存在，如果存在，我们沿着这个分支走到 下一个节点，如果不存在，只能走和他相同的分支。
说明
用 Trie 存储单词，由 26 个字母构成的 Trie 树，是一颗 26 叉树，26 个字母构成分支，深度为最长单词的长度。
用 Trie 存储整数，由整数的十进制位构成的 Trie，是一颗 10 叉树，0-9 个数字构成分支，深度为 10 层。
用 Trie 存储整数，由整数的二进制位构成的 Trie，是一颗二叉树，0 和 1 构成分支，深度为 31 层。
- 图解
AC 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10,M=30000000;
int n,a[N],son[M][2],idx;
void insert(int x)//和字典树一样的思路
{
int p=0;
for(int i=30;i>=0;i--)//从二进制的最高位开始建树
{
int j=x>>i&1;//取出该位置的二进制表示的数
if(!son[p][j]) son[p][j]=++idx;
p=son[p][j];
}
}
int query(int x)
{
int res=0,p=0;
for(int i=30;i>=0;i--)
{
int j=x>>i&1;
if(son[p][!j])//如果存在某个节点和x该位置的二进制数不相同的话，说明异或结果为1，加上这一个二进制位对应十进制的数值，让p走到下一个节点
{
res+=1<<i;
p=son[p][!j];
}
else p=son[p][j];//否则只能走相等的分支，说明异或结果为0，即res+=0<<i,因为0<<i的结果为0，所有可以省略，p走到下一个节点
}
return res;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
insert(a[i]);
}
int res=0;
for(int i=0;i<n;i++)
res=max(res,query(a[i]));
cout<<res<<endl;
return 0;
}
10. 线段树¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int seg[4 * N], arr[N];
// 建树：构建线段树
void build(int node, int l, int r) {
if (l == r) {
seg[node] = arr[l];
} else {
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
seg[node] = seg[2 * node] + seg[2 * node + 1]; // 区间和
}
}
// 区间查询：查询区间 [l, r] 的和
int query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0; // 无交集
if (ql <= l && r <= qr) return seg[node]; // 完全包含
int mid = (l + r) / 2;
return query(2 * node, l, mid, ql, qr) + query(2 * node + 1, mid + 1, r, ql, qr); // 合并结果
}
// 单点更新：更新位置 idx 的值为 val
void update(int node, int l, int r, int idx, int val) {
if (l == r) {
arr[idx] = val;
seg[node] = val;
} else {
int mid = (l + r) / 2;
if (idx <= mid) update(2 * node, l, mid, idx, val);
else update(2 * node + 1, mid + 1, r, idx, val);
seg[node] = seg[2 * node] + seg[2 * node + 1]; // 更新当前节点
}
}
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> arr[i];
build(1, 1, n); // 初始化线段树
while (q--) {
int op;
cin >> op;
if (op == 1) {
int l, r;
cin >> l >> r;
cout << query(1, 1, n, l, r) << endl;
} else if (op == 2) {
int idx, val;
cin >> idx >> val;
update(1, 1, n, idx, val);
}
}
return 0;
}
-
l,r 表示区间的左右端点。 -
node 表示当前线段树节点。 -
ql,qr 表示查询区间的左右端点。 -
idx,val 表示更新位置和更新的值。