440. 字典序的第K小数字

https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/

解法一：dfs暴力（超时）

先dfs回溯法求出字典序数组，然后返回k-1号元素：

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        self.nums = []
        for i in range(1, 10):  #第一位不能为0
            self.dfs(i, n)  #从第二位开始dfs回溯
        return self.nums[k-1]
    def dfs(self, cur, n):
        if cur > n:  #超出则剪枝
            return
        self.nums.append(cur)
        cur = cur * 10
        for i in range(10):
            self.dfs(cur + i, n)

解法二：

参考

https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/solution/ben-ti-shi-shang-zui-wan-zheng-ju-ti-de-shou-mo-sh/

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        p = 1   #工作节点
        prefix = 1  #初始前缀，在树中移动
        while(p < k):
            count = self.getNum(prefix, n)  
            #count-1为除去根后该树节点数
            if p + count-1 >= k:  #在子树
                prefix *= 10
                p += 1    #字典树中父节点之后是其第一子
            else:   #在下一棵树
                prefix += 1
                p += count    #字典树中结点的兄弟间的序号隔了一个子树
        #print(p, prefix)
        return prefix         
    
    def getNum(self, prefix, n):    #获得prefix为根的树总结点数
        cur = prefix
        next = prefix + 1
        count = 0
        while(cur <= n):
            count += min(next, n+1) - cur
            cur *= 10
            next *= 10
        return count