Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input: n: 13 k: 2 Output: 10 Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 1思路：其实就是在遍历trie树，要么往右走，要么往下走
然后考虑到数据量很大，不要遍历，而是求出子树有多少个值小于maxValue，然后再决定怎么走
子树有多个值有点trick，比如1-2，maxValue=13的情况下，1-2的子树有（1-2）+（10-13）
再比如1-2，maxValue=1300的情况下，1-2的子树有（1-2）+（10-20）+（100-200）+（1000-1300）
class Solution: def findKthNumber(self, n, k): """ :type n: int :type k: int :rtype: int """ def count(l,r,maxV): res = 0 while l <= maxV: res += min(maxV+1,r) - l l *= 10 r *= 10 return res # k==1 is the answer res = 1 while k > 1: cnt = count(res, res+1, n) if k >= cnt+1: k -= cnt res += 1 else: k -= 1 res *= 10 return res s=Solution() print(s.findKthNumber(13, 2)) print(s.findKthNumber(10000, 10000))