440. 字典序的第K小数字 (字典序-十叉树的前序遍历)
程序员文章站
2022-03-16 08:25:24
...
LeetCode: 440. 字典序的第K小数字
题目解法: 字典序(树)
ddl 题解: 十叉树
最重要的能力就是迅速抽象问题、拆解问题的能力。
字典序(树):
根据每个数的前缀的大小来进行比较排序。
前缀小的排在前面
这样构建一颗 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;
}
上一篇: 类与对象基础1