• 图论 - Trie树(字符串统计、最大异或对)


    前言

    本篇博客将介绍Trie树的常见应用,包括:Trie字符串统计、最大异或对。首先,我们要知道Trie树是什么?

    Trie树:是一种多叉树的结构,每个节点保存一个字符,一条路径表示一个字符串。例子:下图表示了字符串: him 、 her 、 cat 、 no 、 nova 构成的 Trie 树在这里插入图片描述

    Part 1:Trie字符串统计

    1.题目描述

    维护一个字符串集合,支持两种操作:

    1. I x 向集合中插入一个字符串 x;
    2. Q x 询问一个字符串在集合中出现了多少次。

    共有 N 个操作,所有输入的字符串总长度不超过 105,字符串仅包含小写英文字母。

    输入格式

    第一行包含整数 N,表示操作数。

    接下来 N 行,每行包含一个操作指令,指令为 I xQ x 中的一种。

    输出格式

    对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x 在集合中出现的次数。

    每个结果占一行。

    数据范围

    1≤N≤2∗104

    输入样例
    5
    I abc
    Q abc
    Q ab
    I ab
    Q ab
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    输出样例
    1
    0
    1
    
    • 1
    • 2
    • 3

    2.算法

    • 用数组来模拟Trie树
      在这里插入图片描述
    #include 
    
    using namespace std;
    
    const int N = 100010;
    //son[][]存储子节点的位置,分支最多26条;
    //cnt[]存储以某节点结尾的字符串个数(同时也起标记作用)
    //idx表示当前要插入的节点是第几个,每创建一个节点值+1
    int son[N][26], cnt[N], idx;
    char str[N];
    
    //插入字符串
    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];  //使“p指针”指向下一个节点
        }
        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];  //返回字符串出现的次数
    }
    
    int main()
    {
        int m;
        cin >> m;
    
        while(m--)
        {
            char op[2];
            scanf("%s%s", op, str);
    
            if(*op == 'I') insert(str);
            else printf("%d\n", query(str));
        }
    
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    Part 2:最大异或对

    1.题目描述

    在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?

    输入格式

    第一行输入一个整数 N。

    第二行输入 N 个整数 A1~AN。

    输出格式

    输出一个整数表示答案。

    数据范围

    1≤N≤105,
    0≤Ai<231

    输入样例
    3
    1 2 3
    
    • 1
    • 2
    输出样例
    3
    
    • 1

    2.算法

    • 字典树不单单可以高效存储和查找字符串集合,还可以存储二进制数字
    • 将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异
    #include
    #include
    using namespace std;
    const int N = 100010;
    //保存 Trie 树
    int son[N * 31][2];  
    int n, idx;
    
    void insert(int x)
    {
        int p = 0;//初始化指向根节点
        //从最高位开始,依次取出每一位
        for (int i = 31; i >= 0; i--)
        {   // 取出当前位
            int u = x >> i & 1;
             //如果树中不能走到当前数字
            //为当前数字创建新的节点,保存该数字
            if (!son[p][u])
                // 新节点编号为 idx + 1
                son[p][u] = ++idx; 
            p = son[p][u];
        }
    }
    
    int query(int x)
    {
        //指向根节点
        int p = 0;
        // 保存与 x 异或结果最大的那个数
        int ret = 0;
         //从最高位开始,依次取出 x 的每一位
        for (int i = 31; i >= 0; i--)
        {
            // 取出 x 的当前位
            int u = x >> i & 1;
            //如果树中能走到 !u,就走到!u
            if (son[p][!u]){
                //走到!u
                p = son[p][!u];
                //更新 x 异或的对象
                ret = ret * 2 + !u;
            }  
            //没有!u,就只能走到u了
            else{
                p = son[p][u];
                //更新 x 异或的对象
                ret = ret * 2 + u; 
            }
        }
        //计算异或结果
        ret = ret ^ x;
        return ret;
    }
    
    int main()
    {
        cin >> n;
        int maxXorNum = 0; 
        int x;
        for (int i = 0; i < n; i++)
        {
            cin >> x;
            insert(x);
            maxXorNum = max(maxXorNum, query(x));
        }
    
        cout << maxXorNum << endl;
    
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
  • 相关阅读:
    Mysql查询优化 -Explain 详解(上)
    力扣每日一题69:x的平方根
    易观分析联合中小银行联盟发布海南数字经济指数,敬请期待!
    y110.第六章 微服务、服务网格及Envoy实战 -- Envoy网格安全(二一)
    探索GIS+物联网应用场景 MapGIS IoT实时大数据解决方案
    Java14-线程、同步
    docker save 命令 docker load 命令 快速复制容器
    字符串子序列II
    【.net core】yisha框架imageupload组件多图上传修改
    C# PSO 粒子群优化算法 遗传算法 随机算法 求解复杂方程的最大、最小值
  • 原文地址:https://blog.csdn.net/2203_75327677/article/details/136418644