用织梦建设网站,手机怎样做网站,wordpress动态cdn,wordpress主题切换不了文章和代码已经归档至【Github仓库#xff1a;https://github.com/timerring/algorithms-notes 】或者公众号【AIShareLab】回复 算法笔记 也可获取。 文章目录 Trie树#xff08;字典树#xff09;基本思想例题 Trie字符串统计code关于idx的理解 模板总结应用 最大异或对分… 文章和代码已经归档至【Github仓库https://github.com/timerring/algorithms-notes 】或者公众号【AIShareLab】回复 算法笔记 也可获取。 文章目录 Trie树字典树基本思想例题 Trie字符串统计code关于idx的理解 模板总结应用 最大异或对分析 Trie树字典树
Trie树是用来快速存储和查找 字符串集合的数据结构。某个字符串集合对应的有根树。树的每条边上对应有恰好一个字符每个顶点代表从根到该节点的路径所对应的字符串将所有经过的边上的字符按顺序连接起来。利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较查询效率比哈希树高。
基本思想
存储若干字符串通常样本中的字符较少然后根据字符串中字符出现的先后顺序建立树把具有相同前缀的字符串按照其前缀归类在一个分支中并且需要在字符串的最后一个位置进行标记表明到此为一个完整的字符串。 查找时只需要寻找是否有匹配的序列并且是否已标记结尾即可。 例题 Trie字符串统计
维护一个字符串集合支持两种操作
I x 向集合中插入一个字符串 xQ x 询问一个字符串在集合中出现了多少次。
共有 N 个操作输入的字符串总长度不超过 1 0 5 10^5 105字符串仅包含小写英文字母。
输入格式
第一行包含整数 N表示操作数。
接下来 N 行每行包含一个操作指令指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x都要输出一个整数作为结果表示 x 在集合中出现的次数。
每个结果占一行。
数据范围 1 ≤ N ≤ 2 ∗ 1 0 4 1≤N≤2∗10^4 1≤N≤2∗104
输入样例
5
I abc
Q abc
Q ab
I ab
Q ab输出样例
1
0
1code
#includeiostream
using namespace std;const int N 100010;
// 下标0代表根节点和空节点cnt用于计数idx代表当前的节点和单链表一样相当于是一个独一无二的递增编号son[N][26]每个节点最多有26条边小写英文字母
int son[N][26], cnt[N], idx;
char str[N];
// 插入
void insert(char str[])
{int p 0;// 根节点// 遍历字符串cpp中str最后一位是\0for(int i 0; str[i]; i ){// 映射字母a-z为0-25int u str[i] - a;// 若不存在该节点则创建一个if(!son[p][u]) son[p][u] idx;// 走到该子节点p son[p][u];}cnt[p] ;// 标记该子节点存在的单词个数 记住这里p son[p][u];
}
// 查询
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()
{//ios::sync_with_stdio(false);//cin.tie(0);int n;scanf(%d, n);while(n --){char op[2];scanf(%s%s, op, str);if(op[0] I) insert(str);else printf(%d\n, query(str));}return 0;
}关于idx的理解
不管是链表Trie树还是堆他们的基本单元都是一个个结点连接构成的可以成为“链”式结构。这个结点包含两个基本的属性本身的值和指向下一个结点的指针。按道理应该按照结构体的方式来实现这些数据结构的但是做算法题一般用数组模拟主要是因为比较快。
原来这两个属性都是以结构体的方式联系在一起的现在如果用数组模拟如何才能把这两个属性联系起来呢如何区分各个结点呢答案是采用idx。
idx的操作总是 idx这就保证了不同的idx值对应不同的结点这样就可以利用idx把结构体内两个属性联系在一起了。因此idx可以理解为结点。
idx相当于一个分配器如果需要加入新的结点就用idx分配出一个下标,输入字符串的总长度不超过 1 0 5 10^5 105因此最多会用到 1 0 5 10^5 105个idx。
Trie树中有个二维数组 son[N][26]表示当前结点的儿子如果没有的话可以等于idx。Trie树本质上是一颗多叉树对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如son[1][0]2表示1结点的一个值为a的子结点为结点2;如果son[1][0] 0则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。当然这里2仅仅是一个节点的编号而已。
参考https://www.acwing.com/solution/content/5673/
模板总结
int son[N][26], cnt[N], idx;
// 0号点既是根节点又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
void insert(char *str)
{int p 0;for (int i 0; str[i]; i ){int u str[i] - a;if (!son[p][u]) son[p][u] idx;p son[p][u];}cnt[p] ;
}// 查询字符串出现的次数
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];
}应用 最大异或对
在给定的 N个整数 A 1 A_1 A1 A 2 A_2 A2…… A N A_N AN 中选出两个进行 x o r xor xor异或运算一般异或运算是按位计算的得到的结果最大是多少
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A 1 A_1 A1 A N A_N AN。
输出格式
输出一个整数表示答案。
数据范围 1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105 0 ≤ A i 2 31 0≤A_i2^{31} 0≤Ai231
输入样例
3
1 2 3输出样例
3分析
首先是暴力做法BF O ( n 2 ) O(n^2) O(n2)
for (int i 0; i n; i)
{for (int j 0; j i; j){// 但其实 a[i] ^ a[j] a[j] ^ a[i], 所以内层循环 j i // 因为 a[i] ^ a[i] 0 所以事先把返回值初始化成0 不用判断相等的情况}
}异或也可以理解为不进位加法相同的话异或值为0。Trie树不仅可以存储整数也可以存储二进制数。而计算机中所有文件都是以二进制的形式保存的换句话说Trie数可以存储任何文件。异或后最大这需要寻找出与原数每位不同的数为保证最大值需要从最高位开始依次寻找过程如下所示 可以不用先全部插入因为这是有顺序的避免多次枚举 a j a_j aj 和 a i a_i ai 以及 a i a_i ai 和 a j a_j aj 的情况。因此可以先查找再插入可能最开始的情况下要写一个特判,因为最开始没有可以查找的内容当然也可以先插入再查找可能存在的问题就是每次自己和自己异或是0没有意义。
#include iostream
#include algorithmusing namespace std;
// N是整数个数M是树的总宽度
const int N 100010, M 3100010;int n;
int a[N], son[M][2], idx;void insert(int x)
{int p 0;for (int i 30; i 0; i -- ){// 从高到低依次取每一位int u x i 1;// 没有该节点则插入该节点if (!son[p][u]) son[p][u] idx;// 指针指向下一层p son[p][u];}
}int query(int x)
{int p 0, res 0;for (int i 30; i 0; i -- ){// 从最大位开始找int u x i 1;// 如果当前层有对应的不相同的数,p指针就指到不同数的地址if (son[p][!u]){p son[p][!u];// 因为这一位不同异或后为1这里向前移位并且保留相反数即可。res res * 2 !u;}else {p son[p][u];// 如果没有相异的数则只能向前移一位然后保留该数即可。res res * 2 u;}}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]);// 最后再进行异或处理res max(res, a[i] ^ t);}printf(%d\n, res);return 0;
}同时这里关于代码有两个思路一个是上面这种query需要寻找的对应的异或的整数最后 max(res, a[i] ^ t) 得到结果。
此外还可以直接在 query 中提前进行比较计算最后直接比较结果即可 max(res, t)过程如下
int query(int x)
{int p 0, res 0;for (int i 30; i 0; i -- ){// 从最大位开始找int u x i 1;// 如果当前层有对应的不相同的数,p指针就指到不同数的地址if (son[p][!u]){p son[p][!u];// 因为这一位不同异或后为1只需要向前移并且加1即可res res * 2 1;}else {p son[p][u];// 这一位相同xor后为0向前移一位然后置0即可。res res * 2 0;}}return res;
}
