欧洲性爱在线,日日干天天干天天操B日日操B天天吊,国产永久免费观看,日韩1级片,男人干女人网站,在线观看黄色豆花视频免费网站,成人毛片免费视频,草草网

最近復(fù)習(xí)了 Trie 樹的相關(guān)知識，有了更加深刻的理解。想去打會游戲放松下，突然接到了面試官的電話。

黑臉面試官

猿同學(xué)，看你簡歷上說熟悉數(shù)據(jù)結(jié)構(gòu)，說說你對 Trie 樹的理解。

猿六? ??

Trie 樹是一種數(shù)據(jù)結(jié)構(gòu)，它又叫字典樹。

Trie 樹是一種多叉樹的結(jié)構(gòu)，每個節(jié)點保存一個字符，一條路徑上的所有節(jié)點保存一個字符串。

下圖表示了字符串：him 、 her 、 cat 、 no 、 nova 構(gòu)成的 Trie 樹。

從圖中可以看出 Trie 樹包含以下性質(zhì)：

根節(jié)點不包含字符，其他節(jié)點包含一個字符。
從根節(jié)點到某一節(jié)點經(jīng)過的字符連接起來構(gòu)成一個字符串。如圖中的 him 、 her 、 cat 、 no 、 nova。
一個字符串與 Trie 樹中的一條路徑對應(yīng)。
在實現(xiàn)過程中，會在葉節(jié)點中設(shè)置一個標志，用來表示該節(jié)點是否是一個字符串的結(jié)尾，本例中用青色填充進行標記。
Trie 樹中每個節(jié)點存儲一個字符，從根節(jié)點到葉節(jié)點的一條路徑存儲一個字符串。另外，有公共前綴的字符串，他們的公共前綴會共用節(jié)點。如 her、 him 共用 h 節(jié)點。

黑臉面試官

如何生成 Trie 樹？

猿六? ??

Trie 樹的生成過程，就是不斷將字符串插入樹中。

以插入字符串 him 、 her 、 cat 、 no 、 nova 為例，過程如下：

1. 插入 him :

根節(jié)點不存在子節(jié)點 h，因此創(chuàng)建子節(jié)點 h。
在節(jié)點 h 的基礎(chǔ)上插入第二個字符 i。
節(jié)點 h 不存在子節(jié)點 i，創(chuàng)建子節(jié)點 i。
在節(jié)點 i 的基礎(chǔ)上插入第三個字符 m。
節(jié)點 i 不存在子節(jié)點 m，創(chuàng)建子節(jié)點 m。并將該節(jié)點標記為字符串結(jié)束標志，完成 him 字符串插入。

2. 插入 her :

根節(jié)點存在子節(jié)點 h。不用重新創(chuàng)建子節(jié)點 h。
在節(jié)點 h 的基礎(chǔ)上插入第二個字符 e。
節(jié)點 h 不存在子節(jié)點 e，創(chuàng)建子節(jié)點 e。
在節(jié)點 e 的基礎(chǔ)上插入第三個字符 r。
節(jié)點 e 不存在子節(jié)點 r，創(chuàng)建子節(jié)點 r。并將該節(jié)點標記為字符串結(jié)束標志，完成 her 字符串插入。

3. 插入 cat：

根節(jié)點不存在子節(jié)點 c，因此創(chuàng)建子節(jié)點 c。
在節(jié)點 c 的基礎(chǔ)上插入第二個字符 a。
節(jié)點 c 不存在子節(jié)點 a，創(chuàng)建子節(jié)點 a。
在節(jié)點 a 的基礎(chǔ)上插入第三個字符 ?t。
節(jié)點 a 不存在子節(jié)點 t，創(chuàng)建子節(jié)點 t。并將該節(jié)點標記為字符串結(jié)束標志，完成 cat 字符串插入。

4. 插入 no:

根節(jié)點不存在子節(jié)點 n，因此創(chuàng)建子節(jié)點 n。
在節(jié)點 n 的基礎(chǔ)上插入第二個字符 o。
節(jié)點 n 不存在子節(jié)點 o，創(chuàng)建子節(jié)點 o。并將該節(jié)點標記為字符串結(jié)束標志，完成 no 字符串插入。

5. 插入 nova:

根節(jié)點存在子節(jié)點 n，不用重新創(chuàng)建子節(jié)點 n。
在節(jié)點 n 的基礎(chǔ)上插入第二個字符 o。
節(jié)點 n 存在子節(jié)點 o，不用重新創(chuàng)建子節(jié)點 o。
在節(jié)點 o 的基礎(chǔ)上插入第三個字符 ?v。
節(jié)點 o 不存在子節(jié)點 v，創(chuàng)建子節(jié)點 v。
在節(jié)點 v 的基礎(chǔ)上插入第四個字符 ?a。
節(jié)點 v 不存在子節(jié)點 a，創(chuàng)建子節(jié)點 a。并將該節(jié)點標記為字符串結(jié)束標志，完成 nova 字符串插入。

黑臉面試官

如何刪除一個字符串？

猿六? ??

刪除一個字符串需要考慮的地方較多。

情況一：待刪除的字符串末尾為葉節(jié)點，且與其它字符串無公共前綴。將節(jié)點逐一刪除即可，例如刪除 cat。

情況二：待刪除字符串末尾不是葉節(jié)點。將字符串標志位置為 false 即可，例如刪除 no 。

情況三：待刪除字符串末尾為葉節(jié)點，并且中間有其它單詞。逐一刪除節(jié)點，直到待刪除節(jié)點是另一個字符串的結(jié)尾為止，例如刪除 nova。

情況四：待刪除字符串某一節(jié)點還有其它子節(jié)點。逐一刪除節(jié)點，如果待刪除節(jié)點還有其它子節(jié)點，則停止刪除，例如刪除 him。

黑臉面試官

Trie 樹有什么用？

猿六? ??

Trie 樹又叫字典樹。字典是用來查字的，Trie ?樹最基本的作用是在樹上查找字符串。

例如有 5 個字符串：him 、 her 、 cat 、 ?no 、 nova ?，F(xiàn)在要查找 catch 是否存在。如果使用暴力的方法，需要用 catch 與這 5 個字符串分別進行匹配，效率較低。

如果將這 5 個字符串存儲成 Trie 的結(jié)構(gòu)，只需要順著路徑依次比較，比較完 cat 之后，沒有節(jié)點與 c 匹配，所以字符串集合中不存在 catch。

黑臉面試官

寫一下 Trie 樹實現(xiàn)插入，檢索，刪除字符串的代碼。

//實現(xiàn)?Trie?樹節(jié)點結(jié)構(gòu)struct trie_node{    int isKey = 0; //標志，0：不是字符串結(jié)尾，1：是字符串結(jié)尾    trie_node* child[26] = {nullptr}; //指向子節(jié)點指針};
//插入字符串：void insert(string s, trie_node* root){    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';????????if?(!p->child[n])//沒有對應(yīng)子節(jié)點，創(chuàng)建        {            trie_node* q =new trie_node;            p->child[n] = q;          }        p = p->child[n];    }????p->isKey?=?1;//字符串結(jié)尾標志位置為1}
//檢索字符串bool search(string s, trie_node* root){    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        if (!p->child[n])            return 0;        p = p->child[n];    }    if (p->isKey)        return 1;    return 0;}//刪除字符串：void remove(string s, trie_node* root){    if (!search(s, root))        return;    stack stkt;//存儲路徑上節(jié)點    stack<int> stkc;//存儲待刪除字符串    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        stkc.push(n);        stkt.push(p->child[n]);        p = p->child[n];    }    p->isKey = 0;//情況二，將標志位置為0    while (!stkt.empty())    {        trie_node* q;        q = stkt.top();        if (q->isKey == 1)//情況三，如果標志位1，停止            return;        for (int i = 0; i < 26; i++)//情況四，如果還有其他字符串公用此前綴，停止        {            if (q->child[i])                return;        }         delete q;//刪除節(jié)點        stkt.pop();        stkt.top()->child[stkc.top()] = nullptr;//刪除邊        stkc.pop();    }}

黑臉面試官

Trie 樹還有其他用途嗎？

猿六? ??

可以用來詞頻統(tǒng)計

詞頻統(tǒng)計

在構(gòu)造樹的過程中，已經(jīng)將所有字符串遍歷了一遍?？梢栽?Trie 樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)中，增加一個 count 來計數(shù)。對于每個字符串的插入操作，若已存在，計數(shù)加 1，若不存在，插入后 count 置為 1。

要統(tǒng)計某個字符串出現(xiàn)的次數(shù)，只需要找到字符串結(jié)尾對應(yīng)的節(jié)點，輸出對應(yīng)節(jié)點的 count 值即可。

//重寫?Trie?樹節(jié)點結(jié)構(gòu)struct trie_node{????int?isKey?=?0;?//標志，0：不是字符串結(jié)尾，1：是字符串結(jié)尾????int?count?=?0;//記錄出現(xiàn)次數(shù)    trie_node* child[26] = {nullptr}; //指向子節(jié)點指針};
//重寫插入字符串：void insert(string s, trie_node* root){    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        if (!p->child[n])        {            trie_node* q =new trie_node;            q->count += 1;            p->child[n] = q;          }        p = p->child[n];    }    p->isKey = 1;}
//實現(xiàn)詞頻統(tǒng)計int count(string s, trie_node* root){    if(!search(s,root))        return 0;    trie_node* p = root;    for (auto c : s)    {        int n = c - 'a';        p = p->child[n];    }    return p->count;}

黑臉面試官

說說 Trie 樹的優(yōu)缺點。

猿六? ??

Trie樹的核心思想是空間換時間，利用字符串的公共前綴來減少無謂的字符串比較以達到提高查詢效率的目的。

Trie樹和哈希表一樣，利用空間換取時間。

優(yōu)點：插入和查詢的效率很高，都為O(m)。其中 m 是待插入/查詢的字符串的長度。

缺點：空間消耗比較大。

黑臉面試官

恩，今天先到這，等下一輪面試吧。

猿六

恩恩，謝謝黑臉面試官。

黑臉面試官

你說誰臉黑，你沒下一次面試了。

什么是 Trie 樹？

什么是 Trie 樹？