您的位置:首页 > 健康 > 美食 > 网络规划设计师教材_知名企业文化_百度一下app下载安装_保定百度首页优化

网络规划设计师教材_知名企业文化_百度一下app下载安装_保定百度首页优化

2025/3/17 13:51:34 来源:https://blog.csdn.net/2401_87257864/article/details/146187192  浏览:    关键词:网络规划设计师教材_知名企业文化_百度一下app下载安装_保定百度首页优化
网络规划设计师教材_知名企业文化_百度一下app下载安装_保定百度首页优化

数据结构--算法篇

  • 1 单调栈
    • 1.1 什么是单调栈
    • 1.2 发射站
    • 1.3 代码
  • 2.单调队列
    • 2.1 滑动窗口 /【模板】单调队列
    • 2.2 代码
    • 2.3 质量检测
    • 2.4 代码
  • 3、并查集
    • 3.1 双亲表⽰法
    • 3.2 并查集的概念
    • 3.3 并查集的实现
    • 3.4 亲戚
      • 代码
  • 4. 扩展域并查集
    • 4.1 团伙
      • 代码
  • 5、带权并查集
    • 5.1 食物链
      • 代码
    • 5.2 银河英雄传说
      • 代码
  • 6 字符串哈希
    • 6.1 字符串哈希(模版)
      • 代码
    • 6.2 兔子与兔子
      • 代码
  • 7.trie树
    • 7.1 字典树(模版)
      • 代码

1 单调栈

1.1 什么是单调栈

单调栈,顾名思义,就是具有单调性的栈。它依旧是⼀个栈结构,只不过⾥⾯存储的数据是递增或者
递减的。这种结构是很容易实现的(如下⾯的代码),但重点是维护⼀个单调栈的意义是什么?

单调栈解决的问题
单调栈能帮助我们解决以下四个问题:
• 寻找当前元素左侧,离它最近,并且⽐它⼤的元素在哪;
• 寻找当前元素左侧,离它最近,并且⽐它⼩的元素在哪;
• 寻找当前元素右侧,离它最近,并且⽐它⼤的元素在哪;
• 寻找当前元素右侧,离它最近,并且⽐它⼩的元素在哪。
虽然是四个问题,但是原理是⼀致的。因此,只要解决⼀个,举⼀反三就可以解决剩下的⼏个。
在这里插入图片描述
在这里插入图片描述

1.2 发射站

https://www.luogu.com.cn/problem/P1901

1.3 代码

在这里插入图片描述

2.单调队列

单调队列,顾名思义,就是存储的元素要么单调递增要么单调递减的队列。注意,这⾥的队列和普通的队列不⼀样,是⼀个双端队列。

⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题,以及优化动态规划。

2.1 滑动窗口 /【模板】单调队列

在这里插入图片描述

2.2 代码

在这里插入图片描述

2.3 质量检测

https://www.luogu.com.cn/problem/P2251

2.4 代码

在这里插入图片描述

3、并查集

3.1 双亲表⽰法

接下来要学习到的并查集,本质上就是⽤双亲表⽰法实现的森林。因此,我们先认识⼀下双亲表⽰
法。
在学习树这个数据结构的时,讲到树的存储⽅式有很多种:孩⼦表⽰法,双亲表⽰法、孩⼦双亲表⽰
法以及孩⼦兄弟表⽰法等。对⼀棵树⽽⾔,除了根节点外,其余每个结点⼀定有且仅有⼀个双亲,双
亲表⽰法就是根据这个特点存储树的,也就是把每个结点的双亲存下来。因此,我们可以采⽤数组来
存储每个结点的⽗亲结点的编号,这就实现了双亲表⽰法(so easy)。
在这里插入图片描述
但是,在实现并查集的时,我们⼀般让根节点⾃⼰指向⾃⼰。因此,上述存储就变成:
在这里插入图片描述

3.2 并查集的概念

在有些问题中,我们需要维护若⼲个集合,并且基于这些集合要频繁执⾏下⾯的操作:
• 查询操作:查找元素 x 属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表,查询的是
这个集合中的代表元素;
• 合并操作:将元素 x 所在的集合与元素 y 所在的集合合并成⼀个集合;(注意,合并的是元素所
在的集合,不是这两个元素!)
• 判断操作:判断元素 x 和 y 是否在同⼀个集合。

并查集(Union Find):是⼀种⽤于维护元素所属集合的数据结构,实现为⼀个森林,其中每棵树表
⽰⼀个集合,树中的节点表⽰对应集合中的元素,根节点来代表整个集合。

3.3 并查集的实现

#include<iostream>
using namespace std;const int N=2e5+10;
int n,k;
int f[N];int find(int x)
{if(f[x]==x) return x;return f[x]=find(f[x]);
}int main()
{cin>>n>>k;for(int i=1;i<=n;i++) f[i]=i;while(k--){int z,x,y;cin>>z>>x>>y;if(z==1){int xx=find(x),yy=find(y);f[xx]=yy;}else{if(find(x)==find(y))cout<<'Y'<<endl;elsecout<<'N'<<endl;}}return 0;
}

3.4 亲戚

https://www.luogu.com.cn/problem/P1551

代码

#include<iostream>
using namespace std;int n,m,p;
const int N=5010;
int f[N];int find(int x)
{if(f[x]==x) return x;return f[x]=find(f[x]);
}int main()
{cin>>n>>m>>p;for(int i=1;i<=n;i++) f[i]=i;while(m--){int x,y; cin>>x>>y;int xx=find(x),yy=find(y);f[yy]=xx;}while(p--){int x,y; cin>>x>>y;if(find(x)==find(y))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}

4. 扩展域并查集

在这里插入图片描述
在这里插入图片描述

4.1 团伙

https://www.luogu.com.cn/problem/P1892

在这里插入图片描述

代码

#include<iostream>
using namespace std;int n,m;
const int N=1e3+10;
int f[N*2];int find(int x)
{if(f[x]==x) return x;return f[x]=find(f[x]);
}void uni(int x,int y)
{int xx=find(x),yy=find(y);f[yy]=xx;
}int main()
{cin>>n>>m;for(int i=1;i<=2*n;i++) f[i]=i;while(m--){char ch;int x,y;cin>>ch>>x>>y;if(ch=='E'){uni(x,y+n);uni(y,x+n);}else{uni(x,y);}}int ret=0;for(int i=1;i<=n;i++){if(f[i]==i) ret++;}cout<<ret;return 0;
}

5、带权并查集

在这里插入图片描述

5.1 食物链

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码

#include <iostream>
using namespace std;int n,k;
const int N=5e4+10;
int f[N],d[N]; int find(int x)
{if(f[x]==x) return x;int t=find(f[x]);d[x]+=d[f[x]];return f[x]=t;
}void uni(int x,int y,int w)
{int fx=find(x),fy=find(y);if(fx!=fy){f[fx]=fy;d[fx]=d[y]+w-d[x];}
}int main() 
{cin>>n>>k;for(int i=1;i<=n;i++) f[i]=i;int ret=0;while(k--){int op,x,y; cin>>op>>x>>y;int fx=find(x),fy=find(y);if(x>n||y>n) ret++;else if(op==1){if(fx==fy&&((d[y]-d[x])%3+3)%3!=0) ret++;else uni(x,y,0);}else{if(fx==fy&&((d[y]-d[x])%3+3)%3!=1) ret++;else uni(x,y,2);}}cout<<ret;return 0;
}

5.2 银河英雄传说

https://www.luogu.com.cn/problem/P1196
在这里插入图片描述
在这里插入图片描述

代码

#include<iostream>
#include<cmath>
using namespace std;const int N=3e4+10;
int f[N],d[N],cnt[N];
int t;int find(int x)
{if(f[x]==x) return x;int t=find(f[x]);d[x]+=d[f[x]];return f[x]=t;
}void uni(int x,int y)
{int fx=find(x),fy=find(y);if(fx!=fy){f[fx]=fy;d[fx]=cnt[fy];cnt[fy]+=cnt[fx];}
}void quary(int x,int y)
{int fx=find(x),fy=find(y);if(fx!=fy) cout<<-1<<endl;else{cout<<abs(d[x]-d[y])-1<<endl;}
}int main()
{for(int i=1;i<=N;i++){f[i]=i;cnt[i]=1;}cin>>t;while(t--){char op; int x,y;cin>>op>>x>>y;if(op=='M'){uni(x,y);}else{quary(x,y);}}return 0;
}

6 字符串哈希

6.1 字符串哈希(模版)

代码

#include<iostream>
#include<algorithm>
using namespace std;typedef unsigned long long ULL;
const int N=1e4+10;
int n;
ULL p[N];
int k=131;ULL gethash(string &s)
{ULL ret=0;for(int i=1;i<=s.size();i++){ret=ret*k+s[i-1];}return ret;
}int main()
{cin>>n;for(int i=1;i<=n;i++){string s; cin>>s;p[i]=gethash(s);}sort(p+1,p+1+n);int ret=1;for(int i=2;i<=n;i++)if(p[i]!=p[i-1]) ret++;cout<<ret;return 0;} 

6.2 兔子与兔子

https://www.luogu.com.cn/problem/P10468

代码

#include<iostream>
using namespace std;const int N=1e6+10;
typedef unsigned long long ULL;
ULL f[N],p[N];
int m,n;
int k=131;
string s;void init_hash()
{p[0]=1;for(int i=1;i<=n;i++){f[i]=f[i-1]*k+s[i];p[i]=p[i-1]*k;}
}ULL gethash(int l,int r)
{return f[r]-f[l-1]*p[(r-l+1)];
}int main()
{cin>>s;cin>>m;n=s.size();s=" "+s;init_hash();while(m--){int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2;ULL x=gethash(l1,r1),y=gethash(l2,r2);if(x==y) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;} 

7.trie树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

7.1 字典树(模版)

https://www.luogu.com.cn/problem/P8306

代码

#include<iostream>
using namespace std;const int N=3e6+10;
int tree[N][62];
int p[N];
int n,q,indx;int get_num(char ch)
{if(ch>='a'&&ch<='z') return ch-'a';else if(ch>='A'&&ch<='Z') return ch-'A'+26;else return ch-'0'+52;
}void insert(string &s)
{int cur=0;p[cur]++;for(auto &c: s){int path=get_num(c);if(tree[cur][path]==0) tree[cur][path]=++indx;cur=tree[cur][path];p[cur]++;}
}int find(string &s)
{int cur=0;for(auto &c: s){int path=get_num(c);if(tree[cur][path]==0) return 0;cur=tree[cur][path];}return p[cur];
}int main()
{int T; cin>>T;while(T--){for(int i=0;i<=indx;i++)for(int j=0;j<62;j++)tree[i][j]=0;for(int i=0;i<=indx;i++) p[i]=0;indx=0;cin>>n>>q;while(n--){string s; cin>>s;insert(s);}while(q--){string s; cin>>s;cout<<find(s)<<endl;}}return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com