D
, a non-empty subset of {'1','2','3','4','5','6','7','8','9'}
. (Note that '0'
is not included.) Now, we write numbers using these digits, using each digit as many times as we want. For example, if D = {'1','3','5'}
, we may write numbers such as '13', '551', '1351315'
.
Return the number of positive integers that can be written (using the digits of D
) that are less than or equal to N
.
Example 1:
Input: D = ["1","3","5","7"], N = 100Output: 20Explanation:The 20 numbers that can be written are:1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
Example 2:
Input: D = ["1","4","9"], N = 1000000000Output: 29523Explanation:We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,81 four digit numbers, 243 five digit numbers, 729 six digit numbers,2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.In total, this is 29523 integers that can be written using the digits of D.
Note:
D
is a subset of digits'1'-'9'
in sorted order.1 <= N <= 10^9
- 对于N的百位数字3来说,D中的1小于N中的百位上的3,那么此时百位上固定为1,十位和个位上就可以是任意值了,即 1xx,共有 4^2 = 16 个。
- 对于N的百位数字3来说,D中的3等于N中的百位上的3,那么此时百位上固定为3,十位和个位的值还是不确定,此时就不能再继续遍历D中的数字了,因为之后的数字肯定大于3,但是我们可以继续尝试N的下一位。
- 对于N的十位数字6来说,D中的1小于N中的十位上的6,那么百位和十位分别固定为3和1,个位上就可以是任意值了,即 31x,共有 4 个。
- 对于N的十位数字6来说,D中的3小于N中的十位上的6,那么百位和十位分别固定为3和3,个位上就可以是任意值了,即 33x,共有 4 个。
- 对于N的十位数字6来说,D中的5小于N中的十位上的6,那么百位和十位分别固定为3和5,个位上就可以是任意值了,即 35x,共有 4 个。
- 对于N的十位数字6来说,D中的7大于N中的十位上的6,此时再也组不成小于N的数字了,直接返回最终的 20+16+4+4+4=48 个。
class Solution {public: int atMostNGivenDigitSet(vectorGithub 同步地址: 参考资料:& D, int N) { string str = to_string(N); int res = 0, n = D.size(), len = str.size(); for (int i = 1; i < len; ++i) res += pow(n, i); for (int i = 0; i < len; ++i) { bool hasSameNum = false; for (string &d : D) { if (d[0] < str[i]) res += pow(n, len - 1 - i); else if (d[0] == str[i]) hasSameNum = true; } if (!hasSameNum) return res; } return res + 1; }};