一言
逸一时,误一世。——夏夜银梦
数据结构基础:Trie树

所谓Trie树,又名字典树。


如图,每个节点代表一个字母,该树的单词集合为{"cat","her,"him","no","nova"}
要Trie树中查找单词主要是查找一条路径而不是一个节点。
利用Trie树还可以进行模糊查找,例如,查找ca,可以为用户查到cat并询问。因为有相同的前缀。

c++中传统方法实现Trie树:

sturct trie_node{
int count;//代表到该节点位置,构成单词的个数
struct trie_node* next[26];//因为一共有26个字母
}
struct trie_node* new_node()
{
    trie_node* newnode = new trie_node();
    newnode->count = 0;
    for(int i=0; i<26; i++)
        newnode->children[i] = NULL;
    return newnode;
}
void trie_insert(struct trie_node* root, char word[])
{
    struct trie_node* node = root;//临时指针

    for(int i=0;word[i]!='\0';i++)//遍历字符串
    {
        int index=word[i]-'a';//将a-z映射到0-26的索引
        if(node->children[index] == NULL)
        {
           node->children[index]=create_trie_node();
        }
        node = node->children[index];

    }
    node->count += 1;
}
int search(struct trie_node* root, char word[])
{
    trie_node* node = root;

     for(int i=0;word[i]!='\0';i++)//遍历字符串
    {
       int index=word[i]-'a';//将a-z映射到0-26的索引
        if(node->children[index] == NULL)
        {
          return 0;//该单词不存在
        }
        node = node->children[index];

    }
        return node->count;//返回该单词出现的次数
}

这里把上学期课设写的那个python版本也复制过来

Python实现Trie树

class trie_node:
    def __init__(self) -> None:
        self.chines=""
        self.child={}
        self.val=False#该节点是否构成单词
class Trie:
    def __init__(self) -> None:
        self.root=trie_node()
        self.num=0#贮存的单词数量

    def insert(self,word,chines) -> None:
        temp=self._search(word)
        if temp!=False:
            return False
        tempnode=self.root
        for i in word:
            if i not in tempnode.child:
                tempnode.child[i]=trie_node()
            tempnode=tempnode.child[i]
        tempnode.val=True
        tempnode.chines=chines
        self.num+=1

    def search_word(self,word):
        temp=self.search(word)
        if temp==False:
            #print("未查询到该单词")##这里明天得改一下,把这个写在外边,没必要写到这里,这里做测试用
            return False
        else:
            return temp

    def search(self,word):
        t=''
        possible=[]
        tempnode=self.root
        for i in word:
            #print(tempnode.child.keys())
            if tempnode.val==True:
                possible.append("你可能在找:{}:{}".format(t,tempnode.chines))#模糊查找
            if i not in tempnode.child:
                return possible
            tempnode=tempnode.child[i]
            t+=i
            #print(possible)
        if tempnode.val==True:
            return tempnode.chines
        elif len(possible)!=0:
            return possible
        else:
            return False
    def _search(self,word):
        tempnode=self.root
        for i in word:
            #print(tempnode.child.keys())
            if i not in tempnode.child:
                return False
            tempnode=tempnode.child[i]
        if tempnode.val==True:
            return tempnode
        else:
            return False

    def delete(self,words):
        temp=self._search(words)
        if temp==False:
        # print("未查询到该单词")
            return False
        else:
            self.num-=1
            temp.val=False
            #print("{} 已被成功删除".format(words+":"+temp.chines))

aciwng例题:Trie字符串统计

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

  1. I x 向集合中插入一个字符串 x;
  2. Q x 询问一个字符串在集合中出现了多少次。
    共有 N个操作,所有输入的字符串总长度不超过 10^5,字符串仅包含小写英文字母。
    输入格式
    第一行包含整数 N,表示操作数。
    接下来 N 行,每行包含一个操作指令,指令为 I x Q x 中的一种。
    输出格式
    对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x在集合中出现的次数。
    每个结果占一行。
    数据范围
    1≤N≤2∗10^4
    输入样例:

    5
    I abc
    Q abc
    Q ab
    I ab
    Q ab

    输出样例:

    1
    0
    1

    跟着y总很大的收获是把各种数据结构用数组模拟实现了一遍,是很新的思路。
    AC代码:


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000000;
int a[N];
int son[N*31][2],idx;//题目a[i]的范围是0到2^31次
void insert(int x)
{
    int t=0;
    for(int i=30;i>=0;i--)
    {
        int index=x>>i&1;//取出从右往左数第i位(从0开始数)的数字。
        if(!son[t][index])son[t][index]=++idx;
        t=son[t][index];//指向儿子
    }
}
int query(int x)
{
    int ans=0;
    int t=0;
    for(int i=30;i>=0;i--)
    {
        int index=x>>i&1;
        if(son[t][!index])//如果他儿子的反过来一位是存在的话,则走这一条路。
        {
            t=son[t][!index];
            ans=(ans<<1)+!index;//相当于在末尾加上!index,
                            //例如:5的二进制为0101,左移之后是01010, 
                            //加1,1的二进制为0001,加1之后为01011,加0的话亦然。
        }
        else
        {
            t=son[t][index];//反过来不存在,所以走已经存在的路
            ans=(ans<<1)+index;
        }
    }
    return ans;
}
int main()
{
    int ans=0;
    int n;
    cin>>n;
    for (int i = 0; i < n; i ++ )
    {
    scanf("%d", &a[i]);
    insert(a[i]);
    }
    for (int i = 0; i < n; i ++ )
    {
        int t=query(a[i]);
        ans=max(ans,t^a[i]);
    }
    cout<<ans;
    return 0;
}

例题2:最大异或对

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

输入格式
第一行输入一个整数 N。第二行输入 N 个整数 A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤10^5,
0≤Ai<2^31
输入样例:

3
1 2 3

输出样例:
3
两个数的异或怎么才能最大呢?
比如5: 二进制为0101,要想异或最大,必须从最高位开始,尽量和他不同,这样全取1,所以能和5异或起来最大的就是1010,也就是12。
我们将每个数的二进制从高位用Trie数存储起来,这样在找这个数的最大异或数时,从最高位开始,尽量找与他不同的,比如0101,从最高位开始遍历,第一位是1,先找第一位是0的数,如果有,那就第一位取0,如果没有我们就选1,然后往下走,以此类推,每次选与当前位不同的数,如果能选就选,如果不能选就走和他相同的。直到最后,得到最大的。


大概就这个意思
AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000000;
int a[N];
int son[N*31][2],idx;//题目a[i]的范围是0到2^31次
void insert(int x)
{
    int t=0;
    for(int i=30;i>=0;i--)
    {
        int index=x>>i&1;//取出从右往左数第i位(从0开始数)的数字。
        if(!son[t][index])son[t][index]=++idx;
        t=son[t][index];//指向儿子
    }
}
int query(int x)
{
    int ans=0;
    int t=0;
    for(int i=30;i>=0;i--)
    {
        int index=x>>i&1;
        if(son[t][!index])//如果他儿子的反过来一位是存在的话,则走这一条路。
        {
            t=son[t][!index];
            ans=(ans<<1)+!index;//相当于在末尾加上!index,
                            //例如:5的二进制为0101,左移之后是01010, 
                            //加1,1的二进制为0001,加1之后为01011,加0的话亦然。
        }
        else
        {
            t=son[t][index];//反过来不存在,所以走已经存在的路
            ans=(ans<<1)+index;
        }
    }
    return ans;

}
int main()
{
    int ans=0;
    int n;
    cin>>n;
    for (int i = 0; i < n; i ++ )
    {
         scanf("%d", &a[i]);
         insert(a[i]);

    }
    for (int i = 0; i < n; i ++ )
    {
        int t=query(a[i]);
        ans=max(ans,t^a[i]);
    }
    cout<<ans;
    return 0;

}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇