字典树（前缀树）Trie用法--附加例题

什么是字典树？

字典树也叫做前缀树，是处理大量长字符串比较有效的方法之一，其原理就是通过树这一数据结构类型，把每个字母当成一个节点，共用同一个初始节点开始遍历，更快速方便地找到目标字符串，接下来就和小编一起了解一下实现原理叭（doge）

字典树的实现原理

用一个trie类来构建这个字典树，通过子节点数组（保存26个字母）来作为索引寻找子节点，同时在这个类中加上一个bool型判断是否为单词，以下是简单的构建方法

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;//节点的值
        private boolean haveSon;
 
        TrieNode()
        {
            num=1;
            son=new TrieNode[SIZE];
            isEnd=false;
            haveSon=false;
        }
    }
 
//建立字典树

（以上部分内容来自百度百科）

废话不多说直接来道力扣练手题

有兴趣的朋友先试试

这道题按字典序排列一些数字，我心想打出排序规则然后无脑dfs不就行，然后做了一下发现wa了两个点，听见师兄在喊用字典树前缀树打出来，我就灵鸡一冻，想到可以用字典树来查询，不过这道题有几个比较坑的点，就是构建树的时候需要使用数字，比如从1开始，要找10到19的数字，就得储存10和20作为开始和结尾数，比如first=cur*10；那么last=（cur+1）*10；而且最后一个树不一定是整十的树，储存的时候还需要考虑边界问题，浅浅实现5分钟再debug2小时就能把这道题a出来，真是良心好题

class Solution {
typedef long long ll;
public:
    int findKthNumber(int n, int k) {
        ll num,cur,first,last;

        cur = 1;
        --k;
        while(k > 0){
            num=0;
            first=cur;
            last= cur+1;
            while( first <= n ){
                num+=min((ll)n+1ll,last)-first;

                first*=10;
                last*=10;

            }
            if(num <= k){
                ++cur;
                k-=num;
            }
            else{
                cur*=10;
                --k;
            }
        }
        return cur;
    }
};