LeetCode386 - LexicogarphicalNumbers

? 記錄詳細(xì)的思考過程，從此題加深對(duì)相關(guān)數(shù)據(jù)結(jié)構(gòu)的理解，記錄總結(jié)自己的思維誤區(qū)。

審題

Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

lexicographical adj. 辭典編纂的

?給定n，將1-n按字典序排序

例如n = 13, 返回: [1,10,11,12,13,2,3,4,5,6,7,8,9].

輸入可能到達(dá) 5,000,000.

思考過程

? 首先是理解題意問題，想到先在有序的1-9里面插入，想到插入排序。但是和插入排序不同的是，會(huì)遞歸插入。此時(shí)想到樹。再想，前段時(shí)間看海量數(shù)據(jù)處理的時(shí)候用到的Tire樹（寫文章去查的時(shí)候才知道Tire樹又稱字典樹，如果知道了看到“詞典”就該想到了，不會(huì)繞那么遠(yuǎn)了orz）

Tire Tree（又稱字典樹、單詞查找樹）

哈希樹的變種，典型應(yīng)用是用于統(tǒng)計(jì)、排序和保存大量的字符串（不僅限于字符串），經(jīng)常常用于統(tǒng)計(jì)、查找搜索引擎中用于分詞，詞頻統(tǒng)計(jì)（TF/IDF）,自動(dòng)補(bǔ)全機(jī)制等。查詢效率比哈希樹高。

核心思想是利用公共前綴來減少查詢時(shí)間。

除根節(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都包含一個(gè)字符。

從根到某結(jié)點(diǎn)，所有經(jīng)過的字符組成的字符串即該結(jié)點(diǎn)對(duì)應(yīng)的字符串

每個(gè)節(jié)點(diǎn)最多含有26個(gè)子節(jié)點(diǎn)。樹的高度僅僅由最長(zhǎng)單詞的長(zhǎng)度決定，不由文件篇幅決定。

? 以此想到應(yīng)該用一個(gè)類似的，結(jié)點(diǎn)只存數(shù)字的樹來解決這個(gè)問題。根為空，第一層只有1-9，往后孩子都是0-9，只有n所在的那一組孩子不是全的，類似完全n叉樹。那么就可以用類似根左右的方式把樹遍歷。

? 但第一層是1-9，以后是0-9，需要特殊處理。而且用樹的遍歷是O(n)，考慮到輸入到5000000，可能不合適。

? 這里其實(shí)誤解了一個(gè)問題。之前只是粗略的看了Tire樹，沒有仔細(xì)想明白它如何去遍歷，雖然邏輯上是每個(gè)節(jié)點(diǎn)只存一個(gè)字母，但實(shí)際上是把所有孩子放在一個(gè)數(shù)組里的（注意到哈希樹的變種了嗎？因?yàn)楹雎粤诉@個(gè)又繞了一大圈(?í _ ì?)），下面代碼來自com.suning.search.test.tree.trie

public class Trie
{
    private int SIZE=26;
    private TrieNode root;//字典樹的根
 
    Trie() //初始化字典樹
    {
        root=new TrieNode();
    }
 
    private class TrieNode //字典樹節(jié)點(diǎn)
    {
        private int num;//有多少單詞通過這個(gè)節(jié)點(diǎn),即由根至該節(jié)點(diǎn)組成的字符串模式出現(xiàn)的次數(shù)
        private TrieNode[]  son;//！就這個(gè)！
        private boolean isEnd;//是不是葉子
        private char val;//節(jié)點(diǎn)的值
 
        TrieNode()
        {
            num=1;
            son=new TrieNode[SIZE];
            isEnd=false;
        }
    }
 public void insert(String str) //在字典樹中插入一個(gè)單詞
    {
        if(str==null||str.length()==0)
        {
            return;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(int i=0,len=str.length(); i<len; i++)
        {
            //利用ASCII碼，字母轉(zhuǎn)換為0-25坐標(biāo)
            //這也可以看作是哈希變種
            int pos=letters[i]-'a';
            if(node.son[pos]==null)
            {
                node.son[pos]=newTrieNode();
                node.son[pos].val=letters[i];
            }
            else
            {
                node.son[pos].num++;
            }
            node=node.son[pos];
        }
        node.isEnd=true;
    }
    //前序遍歷字典樹.
    public void preTraverse(TrieNodenode)
    {
        if(node!=null)
        {
            System.out.print(node.val+"-");
for(TrieNodechild:node.son)
            {
                preTraverse(child);
            }
        }
    }

解決

? 這道題看到這兒也就基本出來了，參照Tire的遞歸遍歷，需要考慮的就是如何判斷是葉子結(jié)點(diǎn)及遞歸停止條件。

? 因?yàn)槭菑?-n都存在，即除了n所在的那組，其余組全滿。所以這里考慮不構(gòu)建樹就直接按遍歷模式輸出

private void lexicalInt(int current, int maxNumber,List<Integer> list) {
        //相當(dāng)于限定范圍,省去創(chuàng)建數(shù)組
        int childCount = current == 1 ? 9 : 10;
        //根據(jù)情況for循環(huán)9次或10次或maxNumber的個(gè)位次數(shù)
        for(int i = current; i < childCount && i < maxNumber;i++) {
            list.add(Integer.valueOf(i));
            //最左孩子都是雙親的10倍
            lexicalInt(10*current, maxNumber, list);
            current++;
        }
    }

拓展

Tire遍歷的應(yīng)用

// 遍歷經(jīng)過此節(jié)點(diǎn)的單詞.
    public void preTraverse(TrieNode node, String prefix)
    {
        if (!node.isEnd)
        {
for (TrieNode child : node.son)
            {
                if (child!=null)
                {
                    preTraverse(child, prefix+child.val);
                }
            }
            return;
        }
        System.out.println(prefix);
    }
 //在字典樹中查找一個(gè)完全匹配的單詞.
    public boolean has(Stringstr)
    {
        if(str==null||str.length()==0)
        {
            return false;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(inti=0,len=str.length(); i<len; i++)
        {
            intpos=letters[i]-'a';
            if(node.son[pos]!=null)
            {
                node=node.son[pos];
            }
            else
            {
                return false;
            }
        }
        return node.isEnd;
    }
//打印指定前綴的單詞
    public String hasPrefix(String prefix)
    {
        if (prefix == null || prefix.length() == 0)
        {
            return null;
        }
        TrieNode node = root;
        char[] letters = prefix.toCharArray();
        for (int i = 0, len = prefix.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)
            {
                return null;
            }
            else
            {
                node = node.son[pos];
            }
        }
        preTraverse(node, prefix);
        return null;
    }

//計(jì)算單詞前綴的數(shù)量
    public int countPrefix(Stringprefix)
    {
        if(prefix==null||prefix.length()==0)
        {
            return-1;
        }
        TrieNode node=root;
        char[]letters=prefix.toCharArray();
        for(inti=0,len=prefix.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]==null)
            {
                return 0;
            }
            else
            {
                node=node.son[pos];
            }
        }
        return node.num;
    }

思維誤區(qū)

? 首先，在最初認(rèn)識(shí)題意的時(shí)候，看到5000000，給自己舉了很復(fù)雜的例子。畫了很多層的樹。實(shí)際上是自己給自己找麻煩。例子并不是越復(fù)雜越好，題目給的例子一般都是適中的。要拿題目的例子先畫出數(shù)據(jù)結(jié)構(gòu)的圖出來，避免主觀解讀，導(dǎo)致誤會(huì)。

? 再者，當(dāng)例外情況過多時(shí)，就要考慮這個(gè)實(shí)現(xiàn)思路是不是有問題。而不是把步驟拆的零零散散，自己設(shè)計(jì)的算法只能處理其中的一部分。其余的還要暴力解決。

? 最后，數(shù)據(jù)結(jié)構(gòu)不一定非要構(gòu)建出來才能用?？梢灾蛔鳛榇a步驟的分析工具。