Hard

题目描述

给定一个按 非递减顺序 排列的数字数组 digits。你可以用 digits[i] 来写数字。例如，如果 digits = ['1','3','5']，我们可以写数字如 '13', '551', 和 '1351315'。

返回可以生成的小于或等于给定整数 n 的正整数的个数。

示例 1：

输入：digits = ["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。

示例 2：

输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字，和 19683 个九位数字。
总共，这就是 29523 个可以用数字数组写出的整数。

示例 3：

输入：digits = ["7"], n = 8
输出：1

提示：

  • 1 <= digits.length <= 9
  • digits[i].length == 1
  • digits[i] 是从 '1' 到 '9' 的数字
  • digits 中的所有值都 唯一
  • digits 按 非递减顺序 排列
  • 1 <= n <= 10^9

解题思路

这道题需要计算用给定数字集合能构成的小于等于 n 的正整数个数。我们可以分两部分考虑：

1. 位数小于 n 的数字 对于位数小于 n 的数字，每一位都可以任选 digits 中的数字，因此 k 位数的个数为 digits.length^k。

2. 位数等于 n 的数字 这是关键部分，需要使用数位 DP 的思想。我们从最高位开始逐位考虑：

  • 对于第 i 位，统计 digits 中小于当前位数字的个数，这些数字可以任意组合后续位
  • 如果当前位数字在 digits 中存在且等于 n 对应位的数字，则继续考虑下一位
  • 否则，当前分支结束

核心思路：

  • 先计算位数小于 n 的所有可能数字个数
  • 再用数位 DP 计算位数等于 n 且小于等于 n 的数字个数
  • 两部分相加得到最终答案

时间复杂度主要取决于 n 的位数，空间复杂度为常数级别。

代码实现

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string s = to_string(n);
        int len = s.length();
        int digitCount = digits.size();
        
        // 计算位数小于n的数字个数
        int result = 0;
        for (int i = 1; i < len; i++) {
            result += pow(digitCount, i);
        }
        
        // 计算位数等于n的数字个数
        for (int i = 0; i < len; i++) {
            int count = 0;
            for (const string& digit : digits) {
                if (digit[0] < s[i]) {
                    count++;
                } else if (digit[0] == s[i]) {
                    break;
                } else {
                    return result + count * pow(digitCount, len - i - 1);
                }
            }
            result += count * pow(digitCount, len - i - 1);
            
            // 检查当前位是否匹配
            bool found = false;
            for (const string& digit : digits) {
                if (digit[0] == s[i]) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return result;
            }
        }
        
        return result + 1; // 包含n本身
    }
};

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        s = str(n)
        length = len(s)
        digit_count = len(digits)
        
        # 计算位数小于n的数字个数
        result = sum(digit_count ** i for i in range(1, length))
        
        # 计算位数等于n的数字个数
        for i in range(length):
            count = sum(1 for digit in digits if digit < s[i])
            result += count * (digit_count ** (length - i - 1))
            
            # 如果当前位不在digits中，直接返回
            if s[i] not in digits:
                return result
        
        return result + 1  # 包含n本身

public class Solution {
    public int AtMostNGivenDigitSet(string[] digits, int n) {
        string s = n.ToString();
        int length = s.Length;
        int digitCount = digits.Length;
        
        // 计算位数小于n的数字个数
        int result = 0;
        for (int i = 1; i < length; i++) {
            result += (int)Math.Pow(digitCount, i);
        }
        
        // 计算位数等于n的数字个数
        for (int i = 0; i < length; i++) {
            int count = 0;
            foreach (string digit in digits) {
                if (digit[0] < s[i]) {
                    count++;
                } else {
                    break;
                }
            }
            result += count * (int)Math.Pow(digitCount, length - i - 1);
            
            // 检查当前位是否匹配
            bool found = false;
            foreach (string digit in digits) {
                if (digit[0] == s[i]) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return result;
            }
        }
        
        return result + 1; // 包含n本身
    }
}

var atMostNGivenDigitSet = function(digits, n) {
    const s = n.toString();
    const length = s.length;
    const digitCount = digits.length;
    
    // 计算位数小于n的数字个数
    let result = 0;
    for (let i = 1; i < length; i++) {
        result += Math.pow(digitCount, i);
    }
    
    // 计算位数等于n的数字个数
    for (let i = 0; i < length; i++) {
        let count = 0;
        for (const digit of digits) {
            if (digit < s[i]) {
                count++;
            } else {
                break;
            }
        }
        result += count * Math.pow(digitCount, length - i - 1);
        
        // 检查当前位是否匹配
        if (!digits.includes(s[i])) {
            return result;
        }
    }
    
    return result + 1; // 包含n本身
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(log n × d)
空间复杂度O(log n)

其中 d 是 digits 数组的长度，log n 是 n 的位数。