定义一个“模板串”为一个由数字字符和′?”组成的字符串。我们可以通过将问号替换成数字字符来得到正整数。显然，一个模板串可能会和多个正整数匹配。例如: “1?2”可以和102或者132等正整数匹配。请注意，匹配的正整数不能包含前导零，例如”??1”可以匹配101，但不能匹配001。小红拿到了一个模板串，她想知道，和这个模板串匹配的正整数中，第k小的是多少?
输入描述
第一行输入一个正整数t，代表询问次数。接下来的2* t行，每两行为一次询问: 第一行输入一个字符串，仅由数字字符和?’组成。第二行输入一个正整数k，代表询问的是第k小。
1≤t ≤ 10^4 1≤k≤10 ^9
字符串长度不超过30。
输出描述
输出t行，每行输出一个答案。如果一共都没有k个匹配的正整数，则输出-1。否则输出第小的匹配的正整数。
示例：
1 | 输入： |
分析：
难度：容易
- 思维
这种方法的时间复杂度为 $O(k \log n)$，其中 $k$ 为模板串中问号的个数，$n$ 为最大的匹配数字。
具体地，我们可以将第 $k$ 个数字转化为字符串，然后将该字符串中的每个数字依次替换原字符串中的问号。如果第一个数字为 $0$，则需要将其替换为 $1$。需要注意的是，如果字符串中问号的个数少于数字的位数，则无法匹配该数字，此时需要特判并输出 $-1$。
代码
1 |
- java
1 |
- Python
1 |
- Golang
1 |