每日一题做题记录，参考官方和三叶的题解

题目要求

阅读理解

• “你可以用任意次数digits[i]来写的数字”……这个翻译也太奇怪了吧【(′д｀ )…彡…彡】
  • 原文：You can write numbers using each digits[i]digits[i]digits[i] as many times as we want
  • 意译：任意次数使用每个digits[i]digits[i]digits[i]来组成一个整数
• 也就是说要找用给出的数字能够构造出多少个小于nnn的数。

思路：数位DP

• 起始先转存字符串数组digitsdigitsdigits为数字数组numsnumsnums（长度为mmm），然后逐位转存nnn为listlistlist（长度为lenlenlen）用于后续判断；
• 然后开始构造目标数字，可根据构造目标的位数分为两类：
  • =len=len=len
    • 由高到低逐位判断list[i]list[i]list[i]，将其记为curcurcur；
    • 在numsnumsnums中找到不大于curcurcur的数；
      • 由于numsnumsnums有序，所以用二分找到最右边（最大）满足的数即可，设其下标为rrr。
    • 根据nums[r]nums[r]nums[r]与curcurcur的大小判断后续操作，当前在构造目标的第ppp位（从高向低）：
      • 若nums[r]>curnums[r]>curnums[r]>cur，意味着无法构造合法数字了，所以结束；
      • 若nums[r]=curnums[r]=curnums[r]=cur，构造目标根据当前位的选择可分为两部分：
        • 由位于rrr之前（小于nums[r]nums[r]nums[r]）的数构造出一堆一定小于nnn的数，这些数共有r×mlen−pr\times m^{len-p}r×mlen−p个【当前位有rrr种选择，之后的每一位都有mmm种选择】；
        • 而当前位为nums[r]nums[r]nums[r]时还需继续判断下一位的情况。
      • 若nums[r]<curnums[r]<curnums[r]<cur，当前位为位于rrr及其之前的数任选，其余位置在mmm个数中任选，共可构造(r+1)×mlen−p(r+1)\times m^{len-p}(r+1)×mlen−p个。
  • <len<len<len
    • 此时构造的数一定合法，只需要把不同位数的构造结果加起来即可，每个数位上都有mmm种选择，合计∑i=1len−1mi\sum^{len-1}_{i=1}m^i∑i=1len−1​mi。

Java

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        // 转存digits
        int[] nums = new int[digits.length];
        for (int i = 0; i < digits.length; i++)
            nums[i] = Integer.parseInt(digits[i]);
        // 转存n
        List<Integer> list = new ArrayList<>();
        while (n != 0) {
            list.add(n % 10);
            n /= 10;
        }

        int len = list.size(), m = nums.length, res = 0;
        // 目标数位数 = len
        for (int i = len - 1, p = 1; i >= 0; i--, p++) {
            int cur = list.get(i);
            int l = 0, r = m - 1;
            while (l < r) { // 二分找合适的digits[r]
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= cur)
                    l = mid;
                else
                    r = mid - 1;
            }
            // 是否继续向后
            if (nums[r] > cur)
                break;
            else if (nums[r] == cur) {
                res += r * (int)Math.pow(m, (len - p));
                if (i == 0) // 构造至最后一位
                    res++; // 加上nums[r]做该位的可能
            }
            else if (nums[r] < cur) {
                res += (r + 1) * (int)Math.pow(m, (len - p));
                break;
            }
        }
        // 目标数位数 < len
        for (int i = len - 1; i > 0; i--)
            res += Math.pow(m, i);
        return res;
    }
}

• 时间复杂度：O(log⁡n)O(\log n)O(logn)，由于二分最大范围是1∼91\sim 91∼9可忽略，所以整体复杂度仅与nnn的位数有关
• 空间复杂度：O(C)O(C)O(C)，转存给出数据

C++

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        // 转存digits
        vector<int> nums;
        for (int i = 0; i < digits.size(); i++)
            nums.emplace_back(stoi(digits[i]));
        // 转存n
        vector<int> list;
        while (n != 0) {
            list.emplace_back(n % 10);
            n /= 10;
        }

        int len = list.size(), m = nums.size(), res = 0;
        // 目标数位数 = len
        for (int i = len - 1, p = 1; i >= 0; i--, p++) {
            int cur = list[i];
            int l = 0, r = m - 1;
            while (l < r) { // 二分找合适的digits[r]
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= cur)
                    l = mid;
                else
                    r = mid - 1;
            }
            // 是否继续向后
            if (nums[r] > cur)
                break;
            else if (nums[r] == cur) {
                res += r * (int)pow(m, (len - p));
                if (i == 0) // 构造至最后一位
                    res++; // 加上nums[r]做该位的可能
            }
            else if (nums[r] < cur) {
                res += (r + 1) * (int)pow(m, (len - p));
                break;
            }
        }
        // 目标数位数 < len
        for (int i = len - 1; i > 0; i--)
            res += pow(m, i);
        return res;
    }
};

• 时间复杂度：O(log⁡n)O(\log n)O(logn)，由于二分最大范围是1∼91\sim 91∼9可忽略，所以整体复杂度仅与nnn的位数有关
• 空间复杂度：O(C)O(C)O(C)，转存给出数据

总结

• 今日模板修改之给标题加上题目链接~
• 持续偷懒之不想写Rust，看到那一堆容器就知道肯定搞不出来来回借用克隆；
• get了数位DP的方法，还是很简单的；
  • 由本题其实可以推广到计算任意区间内的合法数字数量，因为容斥原理所以直接res in [l,r]=dp(r)−dp(l)res\ in\ [l,r]=dp(r)-dp(l)res in [l,r]=dp(r)−dp(l)。

欢迎指正与讨论！