目錄
- 資料結構(2)acwing
- 1.trie樹
- 2.并查集（近乎O（1））
- 3.堆
資料結構(2)acwing
1.trie樹
- 快速存盤和查找字串的集合
- 結構特征：
- 例題：Trie字串統計 ？
2.并查集（近乎O（1））
- 思路
- 將兩個集合合并
- 詢問兩個元素是否在一個集合中
-
基本原理：
每個集合用一顆樹來表示，樹根的編號就是整個集合的編號，每個節點存盤他的父節點，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，直接上圖
優化：
1.路徑壓縮
- scanf使用%s會默認忽略“空格”和"回車"，不用%c
- 上代碼：
3.堆
- 概念：”小根堆“（顧名思義{根小于左右兒子}）----》為“完全二叉樹”（最后一行可以不滿，以上全滿），上圖
-
存盤方式（一維陣列存盤）
- x的左兒子：2x
- x的右兒子：2x+1
-
如何手寫一個堆？
-
插入一個數
heap[ ++ size] = x;up(size); -
求集合中最小值
heap[1]; -
洗掉最小值
heap[1] = heap[size];size --;down(1); -
洗掉任意一個元素
heap[k] = heap[size];size --; down(k);up(k); -
修改任意一個元素
heap[k] = x;down(k);up(k);
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288484.html
標籤：C++