欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

440. 字典序的第K小数字 (字典序-十叉树的前序遍历)

程序员文章站 2022-03-16 08:25:24
...

LeetCode: 440. 字典序的第K小数字

440. 字典序的第K小数字 (字典序-十叉树的前序遍历)


题目解法: 字典序(树)

ddl 题解: 十叉树


最重要的能力就是迅速抽象问题、拆解问题的能力。


字典序(树):

根据每个数的前缀的大小来进行比较排序。

前缀小的排在前面

440. 字典序的第K小数字 (字典序-十叉树的前序遍历)

这样构建一颗 10 叉树发现, 字典序排列也就是对这个 10 叉树的 前序遍历。

1, 10, 100, 101,…



AC Code

理解基本写在注释上了


    public int findKthNumber(int n, int k) {

        int pre = 1;
        int cnt = 1;
        while(cnt < k){
        	// 算出当前前缀到目标数 n 中间还有多少个数
            long count = getCount(pre, n);
            
            // 数太多了 >> ans 前缀太小 >>  还在这条前缀范围里, 继续变长(加 0), 数会减少
            if(cnt + count > k){
                pre *= 10;

                // 加一个 0, 也就是向后移动一位而已
                cnt++;

                // 使用 else if >>  需要看还能继续加0后移            
            } else if(cnt + count <= k){
                // 数不够了 >>  这个前缀无法满足了 >>  一直 +1 +1 靠近 k 的前缀
                pre++;

                // 竟然加上来都少于 k了,那么尽收囊中。
                cnt += count;
            }
        }

        return pre;
    }

	// 确定指定前缀下所有子节点数
    // pre 前缀
    public long getCount(int pre, int n){   
        long count = 0;
        // 算出 pre 为前缀下,有几个数
        for (long i = pre, next = pre + 1; i <= n ; i *= 10, next *= 10) {

            // 这里的 n + 1 >> 理解  >> 如果 i 不是 1 , 只要大于 1 , 之后的减法应该符合 2 ~ 10 (10 - 2 + 1) = 9 个数  
            count += (long)Math.min(next, n + 1) - i;
        }

        return count;
    }