basic datastructrue two
发布日期:2022-02-24 01:06:47 浏览次数:10 分类:技术文章

本文共 6844 字,大约阅读时间需要 22 分钟。

basic datastructrue two

trie树

trie树 , 又称字典树 , 是一种花 快速/高效 地 存储/查找 字符串集合的数据结构

结构 : 结点存放每个字符串的字母 , 从根节点往下进行存储 , 如果子节点的字母与要存储的结点的字母相同 , 则继续往下搜索 , 如果不相同 , 则另外开辟一个子节点存储该字母 .

ex : 在这里插入图片描述

可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子,1 -> 4 -> 8 -> 12 表示的就是字符串 caa 。

trie 的结构非常好懂,
我们用 表示结点 的 字符指向的下一个结点,或着说是结点 代表的字符串后面添加一个字符 形成的字符串的结点。(c的取值范围和字符集大小有关,不一定是 0 ~ 26。)
有时需要标记插入进 trie 的是哪些字符串,每次插入完成时在这个字符串所代表的节点处打上标记即可。
---- 转自oiwiki

模版 :

现在有 n 次操作 , 每次操作可以向一个字符串集合中添加一个字符串 或者 求一个字符串在这个集合中的个数 .

代码如下 :

// trie树 (字典树)#include 
using namespace std;const int N = 1000010 ;int son[N][26] , cnt[N] , idx ; // son 存储子节点 cnt存储当前字符串在集合中的个数 idx表示当前字符串的下标void insert(char str[]){
int p = 0 ; for(int i = 0; str[i] ; i ++ ) {
int u = str[i] - 'a' ; // 将每个字符转换成数字进行存储 0 -- 25 if(!son[p][u]) son[p][u] = ++ idx ; // 如果当前字符的子节点不包含其字母 则创建 p = son[p][u] ; // 传递给下面的节点 } cnt[p] ++ ; // 令当前下标对应的字符串 ++ 个数 + 1}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 ; cin >> n ; char str[N] , op[2] ; while ( n -- ) {
scanf("%s%s",op,str) ; if(op[0] == 'I') insert(str) ; else printf("%d\n",query(str)) ; } return 0;}

并查集

快速地进行如下操作 :

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合当中

基本原理 :

每个集合用一棵树来表示 . 树根的编号就是整个集合的编号 . 每个结点存储它的父节点 ,

p[x] 表示 x 的父结点 .

问题1 : 如何判断树根 if (p[x] == x)

问题2 : 如何求x的集合编号: while(p[x] != x) x = p[x]

问题3 : 如何合并两个集合 : px 是 x 的集合编号 py 是 y 的集合编号 p[x] = y

在问题2 中, 每次求 x 的编号都需要从x的当前结点沿着树向上走 , 等于遍历路径上的结点直到找到根节点为止 , 时间复杂度高 , 此时 , 我们可以进行如下优化 (路径压缩) :

在对 x 结点进行向上遍历查找的时候 , 对沿途的每一个结点修改其父节点直接为根结点 , 这样 , 当下次要对 该路径上的其他结点进行查找的时候 , 其就直接指向父节点 , 等于每条路径只需遍历一次 , 这样优化之后时间复杂度 由 O( n ) -> O( 1 )

用scanf读入字符的时候, 因为其会读入 空格 . 回车等 , 从而造成问题 , 这时可将其用字符串读入 op[2]

维护额外信息 : 初始化的时候给每个结点要维护的信息初始化 , 然后在合并的时候对维护的信息进行处理

基础模版 :

// 合并集合// 一共有 n 个数 编号 1 ~ n 现在要进行 m 个操作 操作共有两种:// 1 . M a b 将编号为 a 和 b 所在的两个集合合并 , 如果两个数已在一个集合中, 则忽略这个操作// 2 . Q a b 询问编号为 a 和 b 的两个数是否在一个集合中#include 
using namespace std;const int N = 100010 ;int p[N] ;int find(int x) // 返回 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 ++ ) {
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)] = p[find(b)] ; else {
if(find(a) == find(b)) puts("Yes") ; else puts("NO") ; } } return 0 ;}

变形 ( + 维护信息)

#include 
using namespace std;const int N = 100010 ;int p[N] , n , m , cnt[N] ;int find(int x){
if(p[x] != x) p[x] = p[find(p[x])] ; return p[x] ;}int main(){
scanf("%d%d",&n,&m) ; for(int i = 1;i <= n;i ++ ) {
p[i] = i; cnt[i] = 1 ;} while ( m -- ) {
char op[5] ; int a , b ; scanf("%s",op) ; if(op[0] == 'C') {
scanf("%d%d",&a,&b) ; if(a == b) continue ; else {
cnt[ find(b) ] += cnt[ find(a) ] ; p[find(a)] = p[find(b)] ; } } else if(op[1] == '1') {
scanf("%d%d",&a,&b) ; if(find(a) == find(b)) puts("YES") ; else puts("NO") ; } else {
scanf("%d",&a) ; printf("%d\n",cnt[find(a)]) ; } } return 0 ;}

如何手写一个堆 ?

  1. 插入一个数 heap[++ size] = x ; up(size) ;
  2. 求集合当中的最小值 heap[1] ;
  3. 删除最小值 heap[1] = heap[size] ; size – ; down(k) ; up(k) ;
  4. **下面两点 STL 中的堆无法直接实现 : **
  5. 删除任意一个元素 heap[k] = heap[size] ; size – ; down[k] ; up[k] ;
  6. 修改任意一个元素 heap[k] = x ; up(k) ; down(k) ;

堆是一个完全二叉树

小根堆 : 每一个结点小于等于其左右孩子结点 根节点为最小值

大根堆 : 每一个结点大于等于其左右孩子结点 根节点为最大值

存储 : 一维数组

x 的左孩子 -> 2x x的右孩子 -> 2x + 1

0 的左孩子结点还是 0 , 所以这里数组中的下标从 1 开始

up 和 down 操作的时间复杂度 log( n ) ---- 和树的高度成正比

建堆 :

如果 一个一个 一次插入 时间复杂度为 O( nlogn )

如果直接从 n/2 down 到 n 时间复杂度为 O( n )

模版代码 :

#include 
#include
using namespace std;const int N = 100010 ;int n , m , h[N] , cnt ;// 往下调整结点 void down(int x){
int t = x ; if(t * 2 <= cnt && h[t * 2] < h[t]) t = x * 2; // 注意这里是 x 不能直接更改 t 因为下一步也会用到 if(t * 2 + 1 <= cnt && h[t * 2 + 1] < h[t]) t = x * 2 + 1; if(t != x) {
swap(h[t],h[x]) ; down(t) ; }}// 往上调整节点void up(int x) {
while(x / 2 && h[x / 2] > h[x]) {
swap(h[x / 2] , h[x]) ; x /= 2 ; }}int main(){
scanf("%d%d",&n,&m) ; for(int i = 1;i <= n;i ++ ) scanf("%d",&h[i]) ; cnt = n ; for(int i = n / 2; i ; i -- ) down(i) ; // 从 n/2 开始下调整 时间复杂度 O(n) while (m --) {
printf("%d ",h[1]) ; h[1] = h[cnt] ; cnt -- ; down(1) ; } return 0 ;}

模拟堆 : 难点 : 映射的关系 反函数 常用于dijkstra算法

模版代码 :

// 维护一个集合 初始时集合为空 支持如下几种操作// 1. I x 插入一个数 x ;// 2. PM 输出当前集合中的最小值// 3. DM 删除当前集合中的最小值(当最小值不唯一时,删除最早插入的最小值)// 4. D k 删除第 k 个插入的数// 5. C k x 修改第 k 个插入的数 , 将其变为 x// 难点 : 如何找到第 k 个插入的数是什么 , 在树中求出某个结点是第几个插入的数// 常用于 dijkstra 算法的堆优化#include 
#include
#include
using namespace std;const int N = 100010 ;int h[N] , cnt ;int ph[N] ; // 存储的是第k个插入的点在堆里面的下标int hp[N] ; // 堆里面插入的点是第几个点 与 ph 互为反函数 构成一个映射的关系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 x){
int t = x ; if(t * 2 <= cnt && h[t * 2] < h[t]) t = x * 2 ; if(t * 2 + 1 <= cnt && h[t * 2 + 1] < h[t]) t = x * 2 + 1 ; if(t != x) {
heap_swap(t,x) ; down(t) ; }}void up(int x){
while (x / 2 && h[x / 2] > h[x]) {
heap_swap(x / 2 , x) ; x /= 2 ; }}int main(){
int n , m = 0 ; scanf("%d",&n) ; while (n --) {
int k , x ; char op[10] ; scanf("%s",op) ; if(!strcmp(op,"I")) {
scanf("%d",&x) ; m ++ ; cnt ++ ; ph[m] = cnt , hp[cnt] = m ; h[cnt] = x ; up(cnt) ; } else if(!strcmp(op,"PM")) printf("%d\n",h[1]) ; else if(!strcmp(op,"DM")) {
// 这里要加一个判定 防止 cnt = 1 的时候交换失败 cnt -- 2次才能成功 ; if(cnt == 1) {
heap_swap(cnt,0) ; cnt -- ;continue ;} heap_swap(1,cnt) ; cnt -- ; down(1) ; } else if(!strcmp(op,"D")) {
scanf("%d",&k) ; k = ph[k] ; // 这里也要加一个判定 防止 cnt = 1 的时候交换失败 cnt -- 2次才能成功 ; if(cnt == 1) {
heap_swap(0,cnt) ; cnt -- ; continue ; } 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 ;}

转载地址:https://blog.csdn.net/weixin_45877540/article/details/108409305 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:basic datastructrue one
下一篇:basic datastructrue three

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月12日 02时40分54秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

电梯运行仿真c语言代码,电梯调度算法模拟(示例代码) 2019-04-21
android组件动态接收数据库,Android开发——fragment中数据传递与刷新UI(更改控件)... 2019-04-21
云麦小米华为体脂秤怎么样_云康宝和华为智能体脂秤对比评测,实际体验告诉你哪款更好... 2019-04-21
linux 条件判断 取非_Linux awk 系列文章之 awk 多重条件判断 2019-04-21
c语言中如何将字符串的元素一个一个取出_C语言中常用的字符串操作函数 2019-04-21
2d游戏地图编辑器_王者荣耀:新版本爆料!地图编辑器“天工”即将开测,游戏怎么玩由你定!... 2019-04-21
.net framework服务启动后停止_dos命令net图文教程,start启动系统服务stop停止服务批处理脚本... 2019-04-21
8k分辨率需要多大带宽_超乎想象!用RTX3080显卡连索尼8K电视玩游戏感受如何?... 2019-04-21
win10怎么开启aptx_Win10未来的黑科技?微软SurfaceFleet大曝光 2019-04-21
creo视图管理器使用方法_学以致用之中望3D—浅谈使用中望3D的初步感受 2019-04-21
周育如的音标口诀大全_花鸟画口诀大全,实用! 2019-04-21
心电图计算心率公式_医学常用的计算公式口诀(内外妇儿),赶快收藏! 2019-04-21
select 移动端 第一个无法选中_Python爬虫微博(移动端)评论 2019-04-21
华为云welink成像是反的_华为发布智能办公神器WeLink,可连接会议室开会,还可一键遥控报销和智能翻译... 2019-04-21
唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱” 2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件 2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人... 2019-04-21
this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21