本文共 6844 字,大约阅读时间需要 22 分钟。
basic datastructrue two
trie树
trie树 , 又称字典树 , 是一种花 快速/高效 地 存储/查找 字符串集合的数据结构
结构 : 结点存放每个字符串的字母 , 从根节点往下进行存储 , 如果子节点的字母与要存储的结点的字母相同 , 则继续往下搜索 , 如果不相同 , 则另外开辟一个子节点存储该字母 .
ex :
可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子,1 -> 4 -> 8 -> 12 表示的就是字符串 caa 。
trie 的结构非常好懂, 我们用 表示结点 的 字符指向的下一个结点,或着说是结点 代表的字符串后面添加一个字符 形成的字符串的结点。(c的取值范围和字符集大小有关,不一定是 0 ~ 26。) 有时需要标记插入进 trie 的是哪些字符串,每次插入完成时在这个字符串所代表的节点处打上标记即可。 ---- 转自oiwiki
模版 :
现在有 n 次操作 , 每次操作可以向一个字符串集合中添加一个字符串 或者 求一个字符串在这个集合中的个数 .代码如下 :
// trie树 (字典树)#includeusing 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;}
并查集
快速地进行如下操作 :
- 将两个集合合并
- 询问两个元素是否在一个集合当中
基本原理 :
每个集合用一棵树来表示 . 树根的编号就是整个集合的编号 . 每个结点存储它的父节点 ,
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 的两个数是否在一个集合中#includeusing 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 ;}
变形 ( + 维护信息)
#includeusing 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 ;}
堆
如何手写一个堆 ?
- 插入一个数 heap[++ size] = x ; up(size) ;
- 求集合当中的最小值 heap[1] ;
- 删除最小值 heap[1] = heap[size] ; size – ; down(k) ; up(k) ;
- **下面两点 STL 中的堆无法直接实现 : **
- 删除任意一个元素 heap[k] = heap[size] ; size – ; down[k] ; up[k] ;
- 修改任意一个元素 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!