LeetCode 902 最大为 N 的数字组合：python3 题解

题目链接：902 最大为 N 的数字组合

目录

• 1. 题目解读
  
• 2. 核心解题思路
  
• 3. 解法一：数学排列组合法（推荐）【⭐】
  
  
  
  • 代码实现
    
  • 复杂度分析
    
  
  
• 4. 解法二：数位动态规划 (Digit DP)
  
  
  
  • 代码实现
    
  • 复杂度分析
    
  
  
• 5. 总结与对比
  

1. 题目解读

题目大意：
给定一个允许使用的数字集合 digits（例如 ['1', '3', '5']），你可以使用这些数字任意次来组成新的正整数。
现在给定一个上限整数 n，请问能组成多少个 小于或等于 n 的正整数？
关键点：

• 数字可重复使用：这暗示了这是一个排列组合问题，或者可以使用动态规划。
  
• 上限限制：组成的数字必须 \(\le n\)。
  
• 无前导零：题目中 digits 只包含 '1' 到 '9'，所以不需要考虑 '0' 作为前导的问题，组成的数字天然合法。
  

示例分析：

• digits = ["1","3","5","7"], n = 100
  
• 一位数：1, 3, 5, 7 (共 4 个)
  
• 两位数：11, 13, ..., 77 (共 \(4 \times 4 = 16\) 个)
  
• 三位数：必须 \(\le 100\)。由于最小能组成的三位数是 111，已经大于 100，所以三位数个数为 0。
  
• 总计：\(4 + 16 = 20\)。
  

2. 核心解题思路

我们可以将问题拆分为两部分来统计：

• 位数少于 n 的数字：
  
  
  
  • 假设 n 有 \(L\) 位。任何位数 \(k < L\) 的数字，只要由 digits 组成，一定小于 n。
    
  • 对于长度为 \(k\) 的数字，每一位都有 len(digits) 种选择。
    
  • 所以长度为 \(k\) 的数字共有 len(digits)^k 个。
    
  • 我们需要累加 \(k = 1\) 到 \(L-1\) 的所有情况。
    
  
  
• 位数等于 n 的数字：
  
  
  
  • 这部分比较麻烦，因为必须满足 \(\le n\) 的限制。
    
  • 我们需要从高位到低位（从左到右）逐位确定数字。
    
  • 假设 n 的字符串形式为 \(S\)。
    
  • 在第 \(i\) 位时，我们尝试从 digits 中选一个数字 \(d\)：
    
    
    
    • 情况 A：\(d < S\)
      
      
      
      • 如果当前位选的数字比 n 的对应位小，那么后面的所有位可以任意选择 digits 中的数字。
        
      • 假设后面还有 \(rem\) 位，则有 len(digits)^rem 种组合。
        
      • 统计完这些后，当前位选更小的数字的情况就全部算完了。
        
      
      
    • 情况 B：\(d == S\)
      
      
      
      • 如果当前位选的数字和 n 的对应位相等，那么这一位暂时符合限制，但我们需要继续检查下一位（因为整体大小还没确定）。
        
      • 我们不能直接计算后面的组合数，必须进入下一轮循环。
        
      
      
    • 情况 C：\(d > S\)
      
      
      
      • 如果当前位选的数字比 n 的对应位大，那么组成的数字一定大于 n，不合法。
        
      • 由于 digits 是排序好的，后面的数字也会更大，可以直接停止当前位的遍历。
        
      
      
    
    
  • 特殊情况：如果我们可以一路匹配到最后一位（即 n 本身也可以由 digits 组成），那么 n 本身也是一个合法数字，需要额外 +1。
    
  
  

3. 解法一：数学排列组合法（推荐）【⭐】

这是最直接、效率最高的方法。利用上述思路，通过循环逐位计算。
代码实现

[code]from typing import Listclass Solution:    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:        # 将 n 转换为字符串，方便按位访问        s = str(n)        L = len(s)        D = len(digits)                ans = 0                # --- 第一部分：统计位数少于 L 的数字 ---        # 长度为 1 到 L-1 的数字，每一位都有 D 种选择        # 长度为 i 的数字共有 D^i 个        for i in range(1, L):            ans += D ** i                    # --- 第二部分：统计位数等于 L 的数字 ---        # 我们需要逐位比较，看能组成多少个  int:        s = str(n)        L = len(s)        D = len(digits)                # 1. 先统计位数少于 L 的情况 (同解法一)        ans = 0        for i in range(1, L):            ans += D ** i                    # 2. 使用数位 DP 统计位数等于 L 的情况        # @lru_cache 用于自动记忆化搜索，避免重复计算        @lru_cache(maxsize=None)        def dp(i: int, is_limit: bool) -> int:            # 递归终止条件：如果填完了所有位，说明找到了一个合法数字            if i == L:                return 1                        count = 0            # 确定当前位的上界            # 如果受限制，上界是 n 的当前位 s；否则可以是 '9' (实际上 digits 最大也就 '9')            upper = s if is_limit else '9'                        for d in digits:                # 如果当前数字大于上界，由于 digits 有序，后续数字也一定大于上界，直接停止                if d > upper:                    break                                # 递归下一位                # 新的 is_limit 取决于：当前是否受限 且 当前填的数字是否等于上界                count += dp(i + 1, is_limit and d == upper)                        return count        # 从第 0 位开始，初始状态是受限的 (因为要

这个好，看起来很实用

yyds。多谢分享