数据结构（二）__习题——Trie、并查集、堆、栈

前言

重学算法第6天，希望能坚持打卡不间断，从基础课开始直到学完提高课。

预计时长三个月内，明天再来！肝就完了

2月18日,day06 打卡

今日已学完y总的

算法基础课-2.4-Week3 习题课

共3题，知识点如下

Trie（单词查找树）：最大异或对

并查集：食物链

复习了

堆：模拟堆

额外补充1题合计4题

栈：表达式求值

Trie树 143. 最大异或对

思路：

异或：相同为0，不同为1，俗称不进位加法

暴力做法

优化

每次从高位往前找,每次尽量往与当前位不同的分支走(相同为0,不同为1)

如果有0和1都可选,就选高位开始不同的(异或后更大),相同的划掉

如果只有1个可以走那就没得选,

我们当前走的分支每次都比划去的大,所以直达走到最低位时,当前走的分支就是

异或后得到最大值的分支

可以用 trie 来存储每个数

把每个整数看成31位的二进制串

从根节点开始，每次尽量从与当前位不同的上面走,走到叶结点就找到了

trie 不光能存字符串，还能存整数，二进制数，

计算机内所有信息都是二进制表示，因此 trie 能存储所有信息

样例

可以边插入边查找

每次写代码前最好先把思路梳理一下

从前往后枚举，插入一个数，查询一个数

每次查询的是a[i]前面 和a[i] 异或 值最大的是啥

#include 
#include using namespace std;const int N = 100010, M = 31 * N;int n;
int a[N];
int son[M][2], idx;void insert(int x) {int p = 0;for (int i = 30; i >= 0; i--) { //从最高位开始,每次取出当前位int u = x >> i & 1; // 取出x的第i位是多少，前面位运算讲过if (!son[p][u]) son[p][u] = ++ idx; // 如果不存在就创建p = son[p][u]; // p走到儿子上去}
}int query(int x) {int p = 0, res = 0;for (int i = 30; i >= 0; i--) {int u = x >> i & 1; // 0或1 if (son[p][!u]) {p = son[p][!u]; // 另一个方向(与该位不等的)如果存在就走上去res = res * 2 + !u;} else {p = son[p][u];res = res * 2 + u; // *2 相当于左移一位,最后1位 置0,如果u为0加0,为1就加1}}return res;
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);int res = 0;for (int i = 0; i < n; i++) {insert(a[i]); // 先插入再查询可以避免为空，为空要进行特殊处理int t = query(a[i]); // t为与a[i] 异或 值最大的res = max(res, a[i] ^ t);}printf("%d\n", res);return 0;
}

res

并查集 240. 食物链

样例

环形，3被2吃，2被1吃，1被3吃

只要知道两个动物的关系，就放到一个集合里面,

一定可以推出同一集合中所有对应的关系(只有三种动物)

如：xy是同类，y被z吃，则x也被z吃

x被y吃，y被z吃，则z被x吃

如何确定关系？

记录每个点与根节点的关系

用每个点到根节点的距离来记录关系

可以分为3大类

距离的含义：表示第几代

y是0代，x吃y的就是1代，z吃x就是2代，如果k吃z就是3代

该题只有ABC三种，是循环的

A是0代，B吃A是1代，C吃B是2代，

第三代吃C，而A吃C，所以第三代就是第0代，即A

第四代吃A，而B吃A，所以第四代就是第2代，即B

所以用模表示即可 ABC

余1吃A —第1代，是B

余2吃B —第2代，是C

余0吃C —同类，是A

本来是存的到父节点的距离，路径压缩的时候更新成到根节点的距离即可

而只要知道到根节点的距离，就能根据余数判断出关系

#include using namespace std;const int N = 50010;int n, m; // m表示说话的次数
int p[N], d[N]; // p: 父节点, d: 距离int find(int x) {if (p[x] != x) {// 用t存储的原因：find之后d[p[x]里面存的就不是p[x]这个点了，而是根节点int t = find(p[x]); //定义1个变量存一下p[x]的根节点是谁d[x] += d[p[x]]; // 两段相加就是总距离p[x] = t; // 加完再让p[x] 指向根节点}return p[x];
}int main() {scanf("%d%d", &n, &m);//把每个点先初始化for (int i = 1; i <= n; i++) p[i] = i; //d=0,不需要初始化了,全局变量默认值为0int res = 0; while (m--) {int t, x, y; // t表示询问的种类(D)scanf("%d%d%d", &t, &x, &y);if (x > n || y > n) res++; // 当前的话中x或y比n大，是假话else { int px = find(x), py = find(y); // x, y的根节点if (t == 1) {// 若X和Y是同类// 若 x 与 y 在同一个集合中if (px == py && (d[x] - d[y]) % 3) res++; //两数到根节点距离之差 %3不为 0，说明不是同一类，是假话// 若 x 与 y 不在同一个集合中else if (px != py) {p[px] = py;  // 让py成为px的父节点，即把x所在集合的根节点插入到y所在集合根节点上d[px] = d[y] - d[x];}}else { // 若X吃Y , 即%3后，x要比y多1if (px == py && (d[x] - d[y] - 1) % 3) res++; // 若距离之差-1 %3不为 0，说明吃不掉，是假话else if (px != py) {p[px] = py;d[px] = d[y] + 1 - d[x];} }}}printf("%d\n", res);return 0;
}

距离图

不在一个集合中时

xy为同类，不在一个集合中时，（d[p(x)] + d(x) - d(y) ） %3 = 0 需要成立

即d[p(x)] = d(y) - d(x)

凡是涉及集合合并的都可以用并查集

考虑什么时候用啥数据结构时，

先看题目中的哪些操作可以进行优化，操作有什么样的特点

如：

寻找一堆数里的最小值或最大值-----用堆来做

维护有序链表—用平衡树来做

维护区间最大值，区间和等—可能要用树状数组或者线段树来做

并查集的题目不太容易看出来，需要多做题

堆 839. 模拟堆

该题难在需要支持随便的修改和插入，修改堆里的某一个元素

就需要存映射，即难在映射

交换的时候每个点的映射也需要交换

ph，左边指向右边

hp，右边指向左边

hp[a]，hp[b]就是a b指向左边点的，绿线

ph[hp[a]]就是左边点hp[a]指向 a 的

ph[hp[b]]就是左边点hp[b]指向 b 的

交换两条蓝色的线的指向 swap(ph[hp[a]], ph[hp[b]]);，变为虚线

交换绿色线的指向swap(hp[a],hp[b]);，变成虚线

最后交换a和b的值swap(h[a],h[b]);

最难的就是交换操作，其他的与堆没有区别