题目描述

我们有一个从小到大排序的数位集合 D，D 是 {'1','2','3','4','5','6','7','8','9'} 某个非空集合。（注意不包括 '0'。）

现在我们可以用这些数位拼成数字，可以任意多次的使用这些数位。例如，如果 D = {'1','3','5'}，我们可以拼成例如 '13'、'551'、'1351315'的数字。

返回可以由 D 拼成且不超过 N 的正整数的个数。

样例

输入： D = ["1","3","5","7"], N = 100
输出： 20
解释：
20 个数字可以如下：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77。

输入: D = ["1","4","9"], N = 1000000000
输出: 29523
解释: 
我们可以拼成的一位数有 3 个，两位数有 9 个，三位数有 27 个，
四位数有 81 个，五位数有 243 个，六位数有 729 个，七位数有 2187 个，
八位数有 6561 个，九位数有 19683 个。
总共有 29523 个整数可以由 `D` 拼成。

注意

• D 是数字 '1'-'9' 的有序子集。
• 1 <= N <= 10^9

算法

(数位统计) $O(\log N)$

1. 假设数字 N 有 L 位，D 总共有 n 个数字，那么低于 L 位数的所有数字都可以随意拼成，这一部分总共有 $\sum_{i=1}^{L-1}{n^i}$ 个整数可以拼成。
2. 接下来从数字 N 的最高位开始分析（第 L 位到第 1 位），如果 D 中没有数字小于等于当前位 s[i]，则可以直接返回答案；
3. 若 D 中有数字等于当前位 s[i]，且有 j 个数字小于当前位 s[i]，则当前答案统计 $j \cdot n^{i - 1}$；
4. 若 D 中没有数字等于当前为 s[i]，且有 j 个数字小于当前位 s[i]，则当前答案统计 $j \cdot n^{i - 1}$，然后返回答案。
5. 最后若退出了循环而没有返回，返回答案加一，这是因为最后等于 N 的数字需要被统计。

时间复杂度

• 每个数位被遍历常数次，故时间复杂度为 $O(\log N)$。

Tips

• 这类数位统计题的一般技巧是从高位开始，累加小于当前数字的所有情况，然后令当前位和限制的数字相同，继续往低位累加。

C++ 代码

class Solution {
public:

    int atMostNGivenDigitSet(vector<string>& D, int N) {
        int n = D.size(), ans = 0;
        string s = to_string(N);
        int l = s.length();
        vector<int> power(l, 1);

        for (int i = 1; i < l; i++)
            power[i] = power[i - 1] * n;

        for (int i = 1; i < l; i++)
            ans += power[i];

        for (int i = 0; i < l; i++) {
            int j;
            for (j = 0; j < n; j++)
                if (D[j][0] > s[i])
                    break;
            j--;
            if (j < 0)
                return ans;
            else if (D[j][0] < s[i]) {
                ans += (j + 1) * power[l - i - 1];
                return ans;
            }
            else if (D[j][0] == s[i])
                ans += j * power[l - i - 1];
        }

        return ans + 1;

    }
};