LeetCode386 - LexicogarphicalNumbers
记录详细的思考过程，从此题加深对相关数据结构的理解，记录总结自己的思维误区。
审题
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].
输入可能到达 5,000,000.
思考过程
首先是理解题意问题，想到先在有序的1-9里面插入，想到插入排序。但是和插入排序不同的是，会递归插入。此时想到树。再想，前段时间看海量数据处理的时候用到的Tire树（写文章去查的时候才知道Tire树又称字典树，如果知道了看到“词典”就该想到了，不会绕那么远了orz）
Tire Tree（又称字典树、单词查找树）
哈希树的变种，典型应用是用于统计、排序和保存大量的字符串（不仅限于字符串），经常常用于统计、查找搜索引擎中用于分词，词频统计（TF/IDF）,自动补全机制等。查询效率比哈希树高。
核心思想是利用公共前缀来减少查询时间。
除根节点外，每个结点都包含一个字符。
从根到某结点，所有经过的字符组成的字符串即该结点对应的字符串
每个节点最多含有26个子节点。树的高度仅仅由最长单词的长度决定，不由文件篇幅决定。
以此想到应该用一个类似的，结点只存数字的树来解决这个问题。根为空，第一层只有1-9，往后孩子都是0-9，只有n所在的那一组孩子不是全的，类似完全n叉树。那么就可以用类似根左右的方式把树遍历。
但第一层是1-9，以后是0-9，需要特殊处理。而且用树的遍历是O(n)，考虑到输入到5000000，可能不合适。
这里其实误解了一个问题。之前只是粗略的看了Tire树，没有仔细想明白它如何去遍历，虽然逻辑上是每个节点只存一个字母，但实际上是把所有孩子放在一个数组里的（注意到哈希树的变种了吗？因为忽略了这个又绕了一大圈(｡í _ ì｡)），下面代码来自com.suning.search.test.tree.trie
public class Trie
{
private int SIZE=26;
private TrieNode root;//字典树的根
Trie() //初始化字典树
{
root=new TrieNode();
}
private class TrieNode //字典树节点
{
private int num;//有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
private TrieNode[] son;//！就这个！
private boolean isEnd;//是不是叶子
private char val;//节点的值
TrieNode()
{
num=1;
son=new TrieNode[SIZE];
isEnd=false;
}
}
public void insert(String str) //在字典树中插入一个单词
{
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码，字母转换为0-25坐标
//这也可以看作是哈希变种
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的递归遍历，需要考虑的就是如何判断是叶子结点及递归停止条件。
因为是从1-n都存在，即除了n所在的那组，其余组全满。所以这里考虑不构建树就直接按遍历模式输出
private void lexicalInt(int current, int maxNumber,List<Integer> list) {
//相当于限定范围,省去创建数组
int childCount = current == 1 ? 9 : 10;
//根据情况for循环9次或10次或maxNumber的个位次数
for(int i = current; i < childCount && i < maxNumber;i++) {
list.add(Integer.valueOf(i));
//最左孩子都是双亲的10倍
lexicalInt(10*current, maxNumber, list);
current++;
}
}
拓展
Tire遍历的应用
// 遍历经过此节点的单词.
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);
}
//在字典树中查找一个完全匹配的单词.
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;
}
//计算单词前缀的数量
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;
}
思维误区
首先，在最初认识题意的时候，看到5000000，给自己举了很复杂的例子。画了很多层的树。实际上是自己给自己找麻烦。例子并不是越复杂越好，题目给的例子一般都是适中的。要拿题目的例子先画出数据结构的图出来，避免主观解读，导致误会。
再者，当例外情况过多时，就要考虑这个实现思路是不是有问题。而不是把步骤拆的零零散散，自己设计的算法只能处理其中的一部分。其余的还要暴力解决。
最后，数据结构不一定非要构建出来才能用。可以只作为代码步骤的分析工具。
