leetcode 440. 字典序的第K小数字【字典树】

深藏阁楼爱情的钟 2022-11-16 08:31 217阅读 0赞

[题解参考][Link 1]

**注意会数据溢出，特判或者采用long long**

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    using ll = long long;
    class Solution { 
    public:
    
        int findKthNumber(ll n, ll k) { 
            auto findp = [&]( ll p){ 
                ll ne = p+1;
                ll ret=0;
                while( p<=n){ 
                    ret += min(n+1,ne) - p;
                    p*=10;
                    ne*=10;
                }
                return ret;
            };
            
            ll cur = 1;
            ll cnt = 1;
            
            while(true){ 
                
                if(cnt == k){ 
                    break;
                }
                ll t = findp(cur);
                if(cnt + t > k ){ 
                    int ch = findp(cur*10);
                    cnt += 1;
                    cur*=10;
                }
                else{ 
                    cur++;
                    cnt += t;
                }
            }
            return cur;
        }
    };

![在这里插入图片描述][20210406200303123.png]

[Link 1]: https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/solution/ju-ran-shuang-100chu-hu-yi-liao-can-kao-liao-bie-r/
[20210406200303123.png]: /images/20221022/12541a26b1ae44179be0952754f997c9.png

发表评论取消回复

表情：

评论列表（有 0 条评论，217人围观）

还没有评论，来说两句吧...

相关阅读

相关字典序

一.字典序基础字典序（dictionary order），又称字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两

Dear 丶/ 2024年02月19日 16:38/ 0 赞/ 150 阅读

相关 LexicographicPermute(求字典序的下一个字典序)

伪代码算法 LexicographicPermute(n) //以字典序产生排列 //输入：一个正整数n //输出：在字典序下\{1,……，n\}所有排列的列表初

骑猪看日落/ 2024年02月17日 19:33/ 0 赞/ 132 阅读

相关 LeetCode(每日练习)-440. 字典序的第K小数字、129. 求根节点到叶节点数字之和、380. O(1) 时间插入、删除和获取随机元素

440. 字典序的第K小数字【题目描述】给定整数 n 和 k，返回 \[1, n\] 中字典序第 k 小的数字。示例 1: 输入: n = 13,

墨蓝/ 2023年09月29日 09:58/ 0 赞/ 62 阅读

相关贪心-字典序最小

问题描述：给定一个长度为n的字符串S，构造一个字符串T，长度也为n；起初，T是一个空字符串，随后反复进行以下操作： 1、从S的头部删除一个字符，加到T的尾部。 2

电玩女神/ 2023年07月17日 11:21/ 0 赞/ 66 阅读

相关字典序 Leetcode题目

1. [440. 字典序的第K小数字][440. _K] 给定整数 `n` 和 `k`，找到 `1` 到 `n` 中字典序第 `k` 小的数字。注意：1 ≤ k ≤ n

太过爱你忘了你带给我的痛/ 2022年12月27日 11:27/ 0 赞/ 237 阅读

相关 leetcode 440. 字典序的第K小数字【字典树】

[题解参考][Link 1] 注意会数据溢出，特判或者采用long long define debug(x) cout<<x<<": "<<(x)<<endl;

深藏阁楼爱情的钟/ 2022年11月16日 08:31/ 0 赞/ 218 阅读

相关字典序最小的子序列

给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件： 1、包含字符串中所有出现过的字符各1个。 2、是所有满足条件1的串中，字典序最小的。

约定不等于承诺〃/ 2022年06月12日 07:06/ 0 赞/ 281 阅读

相关 leetcode 440. K-th Smallest in Lexicographical Order 第k个字典序的数字+做不出来

Given integers n and k, find the lexicographically k-th smallest integer in the range fr

清疚/ 2022年06月04日 09:56/ 0 赞/ 153 阅读

相关 leetcode 386. Lexicographical Numbers 前K个字典序数组 + 字典序排序

Given an integer n, return 1 - n in lexicographical order. For example, given 13, retur

红太狼/ 2022年06月04日 05:51/ 0 赞/ 195 阅读

相关字典序算法

算法题目：给定一个正整数，实现一个方法来求出离该整数最近的大于自身的“换位数”。什么是换位数呢？就是把一个整数各个数位的数字进行全排列，从而得到新的整数。例如53241

野性酷女/ 2022年05月27日 01:08/ 0 赞/ 271 阅读