精华内容
下载资源
问答
  • Trie算法

    2019-05-06 22:50:24
    思路:本题如果采用异或操作时间指定会超时,所以就需要优化,我们可以换一种方法去思考这个问题,可以把所有的A[i]的写成二进制,把这些二进制用Trie来存储,在查找第A[i]的异或的最大值的时候,我们可以从头开始找...

    题目:最大异或对

    题意:给你n个数,让你求出任意两个数的异或值的最大值。
    思路:本题如果采用异或操作时间指定会超时,所以就需要优化,我们可以换一种方法去思考这个问题,可以把所有的A[i]的写成二进制,把这些二进制用Trie来存储,在查找第A[i]的异或的最大值的时候,我们可以从头开始找的时候如果有跟A[i]的二进制相反的那么就找相反的,如果没有相反的就找相同的。
    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+10;
    const int N  = 3e7+10;
    int a[maxn];
    int trie[N][2];
    int tot = 0;
    void Insert(int val){//建树
         int rt = 0;
         for(int i = 30; ~i; i--){
            int x = val>>i&1;//取最高位
            if(!trie[rt][x]){
                trie[rt][x] = ++tot;
            }
            rt = trie[rt][x];
         }
    }
    int query(int val){
        int rt = 0, res = 0;
        for(int i = 30; ~i; i--){
            int x = val >> i&1;
            if(trie[rt][!x]){//如果有相反的
                res += 1 << i;
                rt = trie[rt][!x];
            }
            else rt = trie[rt][x];//没有相反的
        }
        return res;
    }
    int main(){
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            Insert(a[i]);
        }
        int res = 0;
        for(int i = 1; i <= n; i++){
            res = max(res, query(a[i]));
        }
        printf("%d\n", res);
    
    }
    
    

    题目: 前缀统计

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6+10;
    int trie[maxn][26];
    int sum[maxn], tot = 0;
    char str[maxn];
    void Insert(char *s, int rt)
    {
        int len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            int x = s[i] - 'a';
            if(!trie[rt][x])
            {
                trie[rt][x] = ++tot;
            }
            rt = trie[rt][x];
    
        }
        sum[rt]++;
    }
    int query(char *s, int rt)
    {
        int len = strlen(s);
        int ans = 0;
        for(int i = 0; i < len; i++)
        {
            int x = s[i] - 'a';
            if(!trie[rt][x])return ans;
            if(trie[rt][x]) ans += sum[trie[rt][x]];
            rt = trie[rt][x];
        }
        return ans;
    }
    int main()
    {
        int n, m;
        scanf("%d %d", &n, &m);
        while(n--)
        {
            scanf("%s", str);
            Insert(str, 0);
        }
        while(m--)
        {
            scanf("%s", str);
            printf("%d\n",query(str, 0));
        }
        return 0;
    }
    
    

    题目:最长异或值路径

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 101000;
    const int N  = 1000000;
    int a[maxn];
    int trie[N][2];
    int tot = 0;
    int head[N];
    struct Node
    {
        int v, w, next;
    } e[N];
    int k = 1;
    void add(int u, int v, int w)
    {
        e[k].v = v;
        e[k].w = w;
        e[k].next = head[u];
        head[u] = k++;
    }
    void Insert(int val)
    {
        int rt = 0;
        for(int i = 30; ~i; i--)
        {
            int x = val>>i&1;
            if(!trie[rt][x])
            {
                trie[rt][x] = ++tot;
            }
            rt = trie[rt][x];
        }
    }
    int query(int val)
    {
        int rt = 0, res = 0;
        for(int i = 30; ~i; i--)
        {
            int x = val >> i&1;
            if(trie[rt][!x])
            {
                res += 1 << i;
                rt = trie[rt][!x];
            }
            else rt = trie[rt][x];
        }
        return res;
    }
    void dfs(int u, int fa, int sum)
    {
        a[u] = sum;
        for(int i = head[u]; ~i; i = e[i].next)
        {
            int v = e[i].v;
            if(v != fa)dfs(v, u, sum^e[i].w);
        }
    }
    int main()
    {
        int n;
        scanf("%d", &n);
        memset(head, -1, sizeof(head));
        for(int i = 1; i <= n-1; i++)
        {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }
        dfs(0, -1, 0);
        int res = 0;
        for(int i = 0; i < n; i++)Insert(a[i]);
        for(int i = 0; i < n; i++)
        {
            res = max(res, query(a[i]));
        }
        printf("%d\n", res);
    
    }
    
    
    
    展开全文
  • Trie算法先对给定的字符串进行归集,形成一个多叉树形结构。使用字符导航方式作匹配查找。trie算法有很多变种,以最左(前缀)匹配为例进行说明。优点使用字符导航查找方式,能最大限度减少字符比较过程,常被用在词频...

    Trie算法

    先对给定的字符串进行归集,形成一个多叉树形结构。

    f55696289b90f12d33cf49b088eb86b1.png

    使用字符导航方式作匹配查找。

    trie算法有很多变种,以最左(前缀)匹配为例进行说明。

    优点

    使用字符导航查找方式,能最大限度减少字符比较过程,常被用在词频统计和字符串排序方面。

    trie算法对文本只需遍历一次,将时间复杂度降到O(n)。

    Java示例

    数据结构class Node {

    Map next;

    }

    样本数据处理public void add(String text) {

    if (text != null) {

    char[] ca = text.toCharArray();

    Node root = this;

    for (char c : ca) {

    root = root.put(c);

    }

    }

    }

    对样本进行拆解public Node put(char c) {

    emptySafe();

    Node node = next.get(c);

    if (node == null) {

    node = new Node();

    next.put(c, node);

    }

    return node;

    }

    对数据作归集public void emptySafe() {

    if (next == null) {

    next = new HashMap(5);

    }

    }

    检索算法public boolean exist(String text) {

    if (emptyCheck(text)) {

    return false;

    }

    char[] ca = text.toCharArray();

    Node root = this;

    for (char c : ca) {

    if (root.next != null) {

    Node node = root.next.get(c);

    if (node != null) {

    root = node;

    }

    if (root.next == null) {

    return true;

    }

    }

    }

    return false;

    }

    不管是前缀或是包含查找,过程都是顺藤摸瓜。

    查找在遇到未匹配的字符时,回到样本数据的根节点,对其它样本做匹配。

    举例说明:

    有两个样本数据:

    /abc、bcd,

    被检索字符串:

    /ab/bcd

    以最左(前缀)匹配查找是不能匹配上的。

    在“包含”查找中,查找路径会因为/ab误入歧途,因此,需要在匹配无结果时回到根节点,以便匹配到bcd。

    最左(前缀)匹配,较为简单就不再赘述。public boolean prefix(String text) {

    if (emptyCheck(text)) {

    return false;

    }

    char[] ca = text.toCharArray();

    Node root = this;

    for (char c : ca) {

    Node node = root.next.get(c);

    if (node == null) {

    return false;

    }

    root = node;

    if (root.next == null) {

    return true;

    }

    }

    return false;

    }

    public boolean emptyCheck(String text) {

    return (next == null || next.isEmpty() || text == null || text.isEmpty());

    }

    说明

    示例中,对样本数据的唯一要求是,不能存在包含关系,如:ab、abc,对这种情况的查找,若最终期望匹配abc是没有问题的,但不能匹配到ab。

    da89e61828b4268245bdb12fd9b921d1.png

    展开全文
  • Trie算法总结

    2019-01-02 18:22:00
     对于Trie类的题目,如果题目要求对多个字符串同时进行处理且有和DFS/BFS结合(这一般是hard题的难度),或者和前缀有关的操作,就应该要考虑到使用Trie的可能性。如果说常规DFS/BFS对字符串处理的解法效率不能达到...

    基本思想:

      对于Trie类的题目,如果题目要求对多个字符串同时进行处理且有和DFS/BFS结合(这一般是hard题的难度),或者和前缀有关的操作,就应该要考虑到使用Trie的可能性。如果说常规DFS/BFS对字符串处理的解法效率不能达到目标,但又不至于超时,很大可能性就会使用Trie这种数据结构,具体实现可参见Leetcode 208,不过一般情况下只需要insert函数即可,常规代码如下,针对具体问题可能会有不同的操作函数。

     1 struct TrieNode{
     2     TrieNode *next[26];
     3     bool isEnd;
     4     TrieNode():isEnd(false){
     5         for(int i = 0;i != 26;++i)
     6             next[i] = NULL;
     7     }
     8 };
     9 class TrieTree{
    10 public:
    11     TrieTree(){
    12         root = new TrieNode();
    13     }
    14     
    15     void insert(string word) {
    16         TrieNode *current = root;
    17         for(int i = 0;i != word.size();++i){
    18             if(current->next[word[i]-'a'] == NULL)
    19                 current->next[word[i]-'a'] = new TrieNode();
    20             current = current->next[word[i]-'a'];
    21         }
    22         current->isEnd = true;
    23     }
    24     struct TrieNode *getRoot(){
    25         return root;
    26     }
    27 private:
    28     TrieNode *root;
    29 };

     

    转载于:https://www.cnblogs.com/haoweizh/p/10210411.html

    展开全文
  • 数组模拟:ACWing835.Trie字符串统计2.链表:力扣208.实现Trie(前缀树) 一、应用场景 Trie (发音为 “try”) 或前缀树、字典树是一种树数据结构,用于检索字符串数据集中的键。这一高效的数据结构有多种应用: 简单...

    一、应用场景

    Trie (发音为 “try”) 或前缀树字典树是一种树数据结构,用于检索字符串数据集中的键。这一高效的数据结构有多种应用:

    在这里插入图片描述
    简单来说,Trie在字符串集合中查找某个字符串的时候,是十分高效的。Trie 树只需要 O(m)的时间复杂度,其中 m 为键长。比如,需要在1万个单词中查找一个单词(三个字母),那时间复杂度就是O(3)。

    二、理解逻辑过程

    在这里插入图片描述
    上面这个Trie树存储了这些单词:cat,dog,deer,panda。和以往把字符串整个存储不同,Trie树存储每个字符。Trie树是一个多叉树,如果字符串都是小写英文字母,那每个结点最多有26个孩子。

    三、例题与模板

    1.数组模拟:ACWing835.Trie字符串统计

    在这里插入图片描述
    代码有详细注释,且与后面的链表表示的代码十分对应。

    (1)读取输入

    #include<iostream>
    #include<string>
    using namespace std;
    
    const int N=2*1e4+10;
    
    //这个N,是结点个数。怎么确定结点个数?(输入的字符串总长度,即所有字符的长度)
    
    int son[N][26]={0};//每个结点需要存储26个孩子,每个孩子中存储了26个孩子的索引
    int cnt[N]={0};//以当前这个结点结尾的单词的个数。代替了"isEnd"的bool值,因为一个单词可能出现多次。
    int idx=0;//当前用到的下标。下标是0的点,即根结点是空结点
    
    char str[N];
    int main(){
        int n=0;
        scanf("%d",&n);
        while(n--){
            char op[2];
            scanf("%s%s",op,str);
            if(op[0]=='I')insert(str);
            else if(op[0]=='Q')printf("%d\n",query(str));
        }
        return 0;
    }
    

    (2)插入操作

    void insert(char str[]){
        int p=0;//p指向根结点。
        for(int i=0;str[i];i++){//char数组存储的字符串,结尾是'\0',可以用来判断是否到了结尾。NULL,0,'\0'都是一样的,都是值0。
            int u=str[i]-'a';//映射到0-25
            if(!son[p][u]){//p结点没有u孩子
                 son[p][u]=++idx;//指定结点p的u孩子的地址
            }
            //p结点的u孩子存在。取得p结点u孩子的地址。下次循环,可以通过p得到u孩子。再去检测u孩子有没有新孩子。
            //循环结束后,指向最后一个字符。
            p=son[p][u];//
        }
        //往p地址里面的cnt+1
        cnt[p]++;
    }
    

    【举例】

    理解idx,需要想象一个虚拟的数组,它是顺序存储了所有新结点的地址。0存储的是根结点。我们可以根据此数组的索引,找到对应的字符

     0  1   2   3   4   5   6   7   8   9   10 ...   N-1
       'a' 'b' 'c' 'd' ...
    

    比如先存 abc

    son[0]['a'-'a']=1; 即son[0][0]=1。 根节点的第一个孩子('a')的索引是1
    son[1]['b'-'a']=2; 即son[1][1]=2。 第二个结点的第二个孩子('b')的索引是2
    son[2]['c'-'a']=3; 即son[2][2]=3。 第三个结点的地三个孩子('c')的索引是3
    cnt[3]+=1;
    

    再存一个 ad

    因为son[0][0]存在,所以可以得到p=1
    son[1]['d'-'a']=4;即son[1][3]=4。a结点的第四个孩子('d')的索引是4
    cnt[4]+=1;
    

    这里理解的关键是:我们根本没有存储这一串字符。我们存储了所有结点的地址,只不过都存在父结点那里罢了。

    (3)查询

    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];//p指向最后一个字符,返回以此字符结尾的单词个数
    }
    

    2.链表:力扣208.实现Trie(前缀树)

    在这里插入图片描述

    class Trie {
    private:
        bool isEnd;
        Trie* next[26];
    public:
    
        /** Initialize your data structure here. */
        Trie() {
            isEnd=false;
            memset(next,0,sizeof(next));
            //# include <string.h>
            //void *memset(void *s, int c, unsigned long n);
            //memset函数:将指针变量 s 所指向的前 n 字节的内存单元用一个“整数” c 替换。
        }
        
        /** Inserts a word into the trie. */
        void insert(string word) {
            Trie* node=this;
            for(char c:word){
                if(node->next[c-'a']==NULL){
                    node->next[c-'a']=new Trie();
                }
                node=node->next[c-'a'];
            }
            node->isEnd=true;
        }
        
        /** Returns if the word is in the trie. */
        bool search(string word) {
            Trie* node=this;
            for(char c:word){
                if(node->next[c-'a']==NULL)return false;
                node=node->next[c-'a'];
            }
            //结束之后,node指向最后一个字符代表的结点
            return node->isEnd;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
            Trie* node=this;
            for(char c:prefix){
                if(node->next[c-'a']==NULL)return false;
                node=node->next[c-'a'];
            }
            //结束之后,node指向最后一个字符代表的结点
            return true;
        }
    };
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie* obj = new Trie();
     * obj->insert(word);
     * bool param_2 = obj->search(word);
     * bool param_3 = obj->startsWith(prefix);
     */
    

    四、Trie在其他方面的应用

    1.存二进制数:ACWing143.最大异或对

    在这里插入图片描述
    思路

    • 异或:也可以叫做“不进位加法”。
      在这里插入图片描述
    • 时间复杂度:算法题一般要求1s或2s,这个时候我们可以根据N的值来判断应该达到的时间复杂度,从而去选择对应的算法。比如这个题目,N=105N=10^5,这个量级我们需要达到O(N)O(N)O(logn)O(logn)。可以参考下图:
      在这里插入图片描述
    • 暴力解法:很明显这个解法时间复杂度为O(n2)O(n^2),我们需要进行优化。我们可以固定住第一层循环,快速找到每个数对应的最大异或值的数。

    在这里插入图片描述

    • 使用Trie树:每次,我们要寻找一个数最大的异或值。比如这个数为100100101010100100101010,怎么让才能让异或值更大呢?从最高位开始,如果是“1”,我们就要找一个“0”,如果是“0”,我们就要找一个“1”。我们把每个数都看做一个31位的二进制数,把这31位存到Trie树中。我们可以以O(31)O(31)的速度,找到这个数对应的异或对。

    代码

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int N=1e5+10,M=30*N;//有N个数字,一共有M个二进制位
    
    int son[M][2]={0};
    int a[N]={0};
    int idx=0;
    
    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];
        }
    }
    
    int query(int x){
        int p=0;
        int res=0;//用来记录和当前x异或后的最大值
        for(int i=30;i>=0;i--){
            int u=x>>i&1;
            if(son[p][!u]){//如果u是0,我们就要找1
                p=son[p][!u];
                res=(res<<1)+1;
                ///*2相当左移一位  然后如果找到对应位上不同的数res+1 例如    001
                ///                                                          010 
                                                                     --->011  
            }else{
                p=son[p][u];
                res=(res<<1)+0;
            }
        }
        return res;
    }
    
    int main(){
        int n=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            insert(a[i]);
        }
        
        //找到每个数字与其他数字异或的最大值
        int res=-1;
        for(int i=0;i<n;i++){
            res=max(res,query(a[i]));
        }
        printf("%d",res);
    }
    

    取二进制数第k位的值:

    x>>k&1
    

    这是一个常用算法哦,我发现自己有点忘了,待我复习一下之后写博客总结总结。

    展开全文
  • 字典树Trie 算法模板

    2020-04-28 19:17:55
    小白也能看懂的视频讲解 单词查找树,利用字符串的公共前缀来减少查询时间 复杂度为O(n) 利用数组来建树 const int N; //树的最大节点数 const int M=26; //数的子节点的数目 举例26为小写... //trie树数组 存...
  • 链表和Trie算法

    2017-11-01 17:56:34
    * tire 算法 * 数据结构链表 * @param cont * @return */ public B create(String cont){ int index=0; if (root == null) { root = new B(cont.charAt(0)); } B cuur=null; cuur=root; while(true){ ...
  • 字典树Trie算法

    2013-08-29 16:22:03
    Trie树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共...
  • double-array trie算法实现

    千次阅读 2013-06-29 22:29:01
    以下是公司同事编程大赛代码,后续会把详细分析加上,优化代码结构 #include #include #include #include #include #include #include #include .../
  • "[奸笑]": "enjoy95", "[捂脸]": "enjoy96", "[机智]": "enjoy97" } trie.js 核心算法 function Trie(){ this.words = 0; this.empty = 1; this.index = 0; this.children = {}; } Trie.prototype = { insert: ...
  • Trie算法

    千次阅读 2015-03-11 22:16:05
    第一眼看到Trie算法,首先明白的就是他一定是用树形结构实现的算法。后来实现完整个算法才知道其实他也是压缩树,类似于哈弗曼编码和CF-Tree,因为树中保留了公共的前缀,减少了不必要的重复存储空间。所以查询...
  • 理论分析表明,HashTrie算法的空间复杂度为O(|P|),与模式串集合的规模|P|线性相关,与字符集大小σ无关,优于经典多模式串匹配算法AC的空间复杂度O(|P|σlog|P|)。在随机数据集和真实数据集(Snort、ClamAV和URL)...
  • 算法入门之Trie

    2013-08-25 10:26:27
    字典树入门: Trie树(前缀树)又称字典树,通过树形结构来构造各个字符串,通过数字式,形成一个体系, root根节点,连接各个子节点...Trie算法技巧: 1.构造树形,初始化。信息包含:每段字符统计个数ncount,树结
  • Trie字典树算法

    2016-11-03 20:22:57
    特性 Trie树属于树形结构,查询效率比红黑树和哈希表都要快。假设有这么一种应用场景:有若干个英文单词,需要快速查找某个单词是否存在于字典中。使用Trie时先从根节点开始查找,直至匹配到给出字符串的最后一个...
  • 基于Trie算法中具有计数BloomFilter的高效IP地址查找

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,587
精华内容 1,034
关键字:

trie算法