leetcode440 字典序的第K小数字

思路：

字典树思想。

实现：

 1 class Solution {
 2 public:
 3     //前缀prefix下的节点数量
 4     using ll=long long;
 5     ll get_count(ll prefix,ll n){
 6         ll res=0;
 7         ll next=prefix+1;
 8         while(prefix<=n){
 9             res+=min(n+1,next)-prefix;
10             prefix*=10;
11             next*=10;
12         }
13         return res;
14     }
15     int findKthNumber(int n, int k) {
16         ll p=1;
17         ll cur=1;
18         while(cur<k){
19             ll tmp=get_count(p,n);
20             if(cur+tmp>k){
21                 p*=10;
22                 cur++;
23             }
24             else{
25                 cur+=tmp;
26                 p++;
27             }
28         }
29         return p;
30 
31     }
32 };