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. 解法一：数学排列组合法（推荐）【⭐】
这是最直接、效率最高的方法。利用上述思路，通过循环逐位计算。
代码实现
from typing import Listclass Solution: def atMostNGivenDigitSet(self, digits: List, 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。多谢分享
页:
[1]