在线免费看黄色片,亚洲特级毛片精品久久,69操视频,精品国产卡一卡二,www,操逼,日本无码色情三级播放免费看电影 ,色哟哟――国产精品,免费能看的黄色

最近復(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è)置一個標(biāo)志，用來表示該節(jié)點是否是一個字符串的結(jié)尾，本例中用青色填充進(jìn)行標(biāo)記。
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é)點標(biāo)記為字符串結(jié)束標(biāo)志，完成 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é)點標(biāo)記為字符串結(jié)束標(biāo)志，完成 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é)點標(biāo)記為字符串結(jié)束標(biāo)志，完成 cat 字符串插入。

4. 插入 no:

根節(jié)點不存在子節(jié)點 n，因此創(chuàng)建子節(jié)點 n。
在節(jié)點 n 的基礎(chǔ)上插入第二個字符 o。
節(jié)點 n 不存在子節(jié)點 o，創(chuàng)建子節(jié)點 o。并將該節(jié)點標(biāo)記為字符串結(jié)束標(biāo)志，完成 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é)點標(biāo)記為字符串結(jié)束標(biāo)志，完成 nova 字符串插入。

黑臉面試官

如何刪除一個字符串？

猿六? ??

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

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

情況二：待刪除字符串末尾不是葉節(jié)點。將字符串標(biāo)志位置為 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 個字符串分別進(jìn)行匹配，效率較低。

如果將這 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; //標(biāo)志，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é)尾標(biāo)志位置為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;//情況二，將標(biāo)志位置為0    while (!stkt.empty())    {        trie_node* q;        q = stkt.top();        if (q->isKey == 1)//情況三，如果標(biāo)志位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;?//標(biāo)志，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樹的核心思想是空間換時間，利用字符串的公共前綴來減少無謂的字符串比較以達(dá)到提高查詢效率的目的。

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

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

缺點：空間消耗比較大。

黑臉面試官

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

猿六

恩恩，謝謝黑臉面試官。

黑臉面試官

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

什么是 Trie 樹？

什么是 Trie 樹？