成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

208-實(shí)現(xiàn) Trie (前綴樹)

antyiwei / 1177人閱讀

摘要：前言前綴樹是一種很常用的數(shù)據(jù)結(jié)構(gòu)，例如我們常用的數(shù)據(jù)庫索引。而關(guān)于前綴樹的介紹，由于中國有關(guān)于前綴樹的教程，我就不班門弄斧了，我的答案也是參考教程的思路去解答，希望可以給大家一個參考。下面是原題目實(shí)現(xiàn)一個前綴樹，包含和這三個操作。

前言

前綴樹是一種很常用的數(shù)據(jù)結(jié)構(gòu)，例如我們常用的數(shù)據(jù)庫索引。而關(guān)于前綴樹的介紹，由于LeetCode中國有關(guān)于前綴樹的教程，我就不班門弄斧了，我的答案也是參考教程的思路去解答，希望可以給大家一個參考。下面是原題目：

實(shí)現(xiàn)一個 Trie (前綴樹)，包含 insert, search, 和 startsWith 這三個操作。
示例:
Trie trie = new Trie();


trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true
說明:


你可以假設(shè)所有的輸入都是由小寫字母 a-z 構(gòu)成的。
保證所有輸入均為非空字符串。
解題思路

樹是由節(jié)點(diǎn)組成，節(jié)點(diǎn)定義應(yīng)該包含節(jié)點(diǎn)值(前綴樹的定義，值應(yīng)該為一個字符char)和葉子節(jié)點(diǎn)的指針，但是為了識別是否為一個單詞的最后一個字符，所以增加一個boolean變量識別。

由于已知輸入為全小寫(a-z)的字母，所以可以使用一個長度為26的數(shù)組存儲葉子節(jié)點(diǎn)。且由于a-z的ASCII碼是連續(xù)的，其ASCII是從97-123，所以可以直接使用 ASCII碼-97=對應(yīng)節(jié)點(diǎn)的數(shù)組下標(biāo)。

基于數(shù)組實(shí)現(xiàn)的前綴樹 
class Trie {
    /**
     * 當(dāng)前節(jié)點(diǎn)的值
     */
    public char value;
    /**
     * a-z有26個字母，需要訪問時(shí)由于a的ASCII碼為97，所以所有字母訪問的對應(yīng)下表皆為 字母的ASCII碼-97
     */
    public Trie[] children=new Trie[26];
    /**
     * 標(biāo)識此節(jié)點(diǎn)是否為某個單詞的結(jié)束節(jié)點(diǎn)
     */
    public boolean endAsWord=false;
    
    public Trie() {
        
    }
    /**
     * 插入一個單詞
     * @param word 單詞
     */
    public void insert(String word) {
        if(word!=null){
            //分解成字符數(shù)組
            char[] charArr=word.toCharArray();
            //模擬指針操作,記錄當(dāng)前訪問到的樹的節(jié)點(diǎn)
            Trie currentNode=this;
            for(int i=0;i

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76527.html

相關(guān)文章

  • javascript 前綴Trie

    摘要：很容易看出，前綴最壞情況下的查找也快過二叉搜索樹。這種壓縮后的被喚作前綴壓縮，或直接叫前綴樹，字典樹。最長公共前綴和的最長公共前綴是，遍歷字典樹到字母時(shí)，此時(shí)這些單詞的公共前綴是。 引子 前綴Trie, 又叫字符Tire, trie來自單詞retrieval, 一開始念作tree，后來改念try， 畢竟它與樹是不一樣的東西。網(wǎng)上許多文章都搞混了trie與樹。 trie是通過邊來儲存字符...

    xiaochao 評論0 收藏0

  • [Leetcode] Implement Trie 實(shí)現(xiàn)前綴樹

    摘要：壓縮前綴樹其實(shí)就是將所有只有一個子節(jié)點(diǎn)的節(jié)點(diǎn)合并成一個，以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

    jsliang 評論0 收藏0

  • 以太坊數(shù)據(jù)結(jié)構(gòu)MPT

    摘要：是以太坊存儲數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu)，它是由和結(jié)合的一種樹形結(jié)構(gòu)，理解有助于我們更好的理解以太坊的數(shù)據(jù)存儲。所以就有了樹壓縮前綴樹，后面會介紹到，也被稱為，中文名稱默克爾樹，主要用于數(shù)據(jù)集較大時(shí)的文件校驗(yàn)。 ??MPT(Merkle Patricia Tries)是以太坊存儲數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu)，它是由Merkle Tree和Patricia Tree結(jié)合的一種樹形結(jié)構(gòu)，理解MPT有助于我們更...

    Honwhy 評論0 收藏0

  • 以太坊源碼分析--MPT樹

    摘要：是以太坊中存儲區(qū)塊數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu)，它和融合一個樹形結(jié)構(gòu)，理解結(jié)構(gòu)對之后學(xué)習(xí)以太坊區(qū)塊以及智能合約狀態(tài)存儲結(jié)構(gòu)的模塊源碼很有幫助。 MPT(Merkle Patricia Tries)是以太坊中存儲區(qū)塊數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu)，它Merkle Tree和Patricia Tree融合一個樹形結(jié)構(gòu)，理解MPT結(jié)構(gòu)對之后學(xué)習(xí)以太坊區(qū)塊header以及智能合約狀態(tài)存儲結(jié)構(gòu)的模塊源碼很有幫助。 首...

    roadtogeek 評論0 收藏0

  • Trie樹 php 實(shí)現(xiàn)敏感詞過濾

    摘要：在樹中，每個節(jié)點(diǎn)表示一個狀態(tài)，每條邊表示一個字符，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過的邊即表示一個詞條。查找一個詞條最多耗費(fèi)的時(shí)間只受詞條長度影響，因此的查找性能是很高的，跟哈希算法的性能相當(dāng)。 Last-Modified: 2019年5月10日15:25:35 參考文章 c++ 使用map實(shí)現(xiàn)Trie樹 關(guān)鍵詞過濾擴(kuò)展，用于檢查一段文本中是否出現(xiàn)敏感詞，基于Double-Array Trie...

    王笑朝 評論0 收藏0

發(fā)表評論

0條評論

antyiwei

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<