【回溯-数字全排列&&dfs】leet 440. 字典序的第K小数字

给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

提示:

• 1 <= k <= n <= 109

  class Solution {
    public int findKthNumber(int n, int k) {
        int r = 1; //当k=1的时候，答案就是 r
        while (k > 1) { //所以k从>1开始
            long t = count(r, n); 
            if (t < k) {
                k -= t; r++;
            } else {
                k--; r *= 10;
            }
        }
        return r;

    }

    public long count(long r,int n){ //在以r为节点的树上找<=n的节点的数量
        long next=r+1;
        long total=0;
        while(r<=n){
            total+=Math.min(n+1,next)-r; //r层节点个数. 含有n 或 next-1，不含有next
            r=r*10;
            next=next*10;
        }
        return total;
    }
}