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

1. 题目解读题目大意给定一个允许使用的数字集合digits例如[1, 3, 5]你可以使用这些数字任意次来组成新的正整数。现在给定一个上限整数n请问能组成多少个小于或等于n的正整数关键点数字可重复使用这暗示了这是一个排列组合问题或者可以使用动态规划。上限限制组成的数字必须 ≤。无前导零题目中digits只包含 1 到 9所以不需要考虑 0 作为前导的问题组成的数字天然合法。示例分析digits [1,3,5,7], n 100一位数1, 3, 5, 7 (共 4 个)两位数11, 13, ..., 77 (共 4×416 个)三位数必须 ≤100。由于最小能组成的三位数是 111已经大于 100所以三位数个数为 0。总计41620。2. 核心解题思路我们可以将问题拆分为两部分来统计位数少于n的数字假设n有 位。任何位数 的数字只要由digits组成一定小于n。对于长度为 的数字每一位都有len(digits)种选择。所以长度为 的数字共有len(digits)^k个。我们需要累加 1 到 −1 的所有情况。位数等于n的数字这部分比较麻烦因为必须满足 ≤ 的限制。我们需要从高位到低位从左到右逐位确定数字。假设n的字符串形式为 。在第 位时我们尝试从digits中选一个数字 情况 A[]如果当前位选的数字比n的对应位小那么后面的所有位可以任意选择digits中的数字。假设后面还有 位则有len(digits)^rem种组合。统计完这些后当前位选更小的数字的情况就全部算完了。情况 B[]如果当前位选的数字和n的对应位相等那么这一位暂时符合限制但我们需要继续检查下一位因为整体大小还没确定。我们不能直接计算后面的组合数必须进入下一轮循环。情况 C[]如果当前位选的数字比n的对应位大那么组成的数字一定大于n不合法。由于digits是排序好的后面的数字也会更大可以直接停止当前位的遍历。特殊情况如果我们可以一路匹配到最后一位即n本身也可以由digits组成那么n本身也是一个合法数字需要额外 1。3. 解法一数学排列组合法推荐【⭐】这是最直接、效率最高的方法。利用上述思路通过循环逐位计算。代码实现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 的数字 ---# 我们需要逐位比较看能组成多少个 n 的数for i, char in enumerate(s):# 遍历允许的数字集合# is_break Falsefor d in digits:if d char:# 情况 A: 当前位 d 小于 n 的对应位 char# 那么后面的所有位 (L - 1 - i) 都可以任意填ans D ** (L - 1 - i)elif d char:# 情况 B: 当前位 d 等于 n 的对应位 char# 这一位确定了但还需要看下一位是否满足限制# 所以跳出内层循环继续外层循环处理下一位# is_break Truebreakelse:# 情况 C: 当前位 d 大于 n 的对应位 char# 由于 digits 是有序的后面的 d 肯定也大于 char# 直接跳出内层循环且不再继续匹配后续位# 这里的 break 会触发下方 for-else 的 else 分支吗不会因为 break 了# 但我们需要标记“无法完全匹配前缀”所以直接返回当前 ansreturn ans# Python 特有的 for-else 语法# 如果内层 for 循环正常结束没有遇到 break说明没有找到 d char# 这意味着 s[i] 比 digits 里面所有数都更大所以统计到第 i 位就可以结束了# 所以直接返回当前的统计结果else: # 或者 if not is_break:return ans# --- 第三部分处理完全相等的情况 ---# 如果代码能运行到这里说明 s 的每一位都能在 digits 中找到# 也就是说 n 本身也是可以由 digits 组成的需要加上这 1 个ans 1return ans复杂度分析时间复杂度(log⁡⋅)。其中 log⁡ 是n的位数 是digits的长度。由于 ≤9可以看作 (log⁡)。空间复杂度(log⁡)。用于存储n的字符串形式。4. 解法二数位动态规划 (Digit DP)我不太会数位 dp也暂时懒得学了所以没看这部分数位 DP 是解决“统计满足特定条件的数字个数”这类问题的通用模板。虽然对于这道题数学法更简单但学习 DP 思路对解决更复杂的变体例如包含 0、包含特定限制等很有帮助。思路同样先处理位数少于 的情况这部分 DP 处理起来比较麻烦不如数学法直接所以通常结合使用。使用 DFS 记忆化搜索来统计位数等于 且 ≤ 的数字个数。状态定义dfs(index, is_limit)index: 当前正在填第几位从 0 开始。is_limit: 布尔值表示当前位是否受到n的对应位限制。如果is_limit为True当前位最大只能填s[index]。如果is_limit为False当前位可以填digits中的任意值。代码实现from typing import Listfrom functools import lru_cacheclass Solution:def atMostNGivenDigitSet(self, digits: List[str], n: int) - int:s str(n)L len(s)D len(digits)# 1. 先统计位数少于 L 的情况 (同解法一)ans 0for i in range(1, L):ans D ** i# 2. 使用数位 DP 统计位数等于 L 的情况# lru_cache 用于自动记忆化搜索避免重复计算lru_cache(maxsizeNone)def dp(i: int, is_limit: bool) - int:# 递归终止条件如果填完了所有位说明找到了一个合法数字if i L:return 1count 0# 确定当前位的上界# 如果受限制上界是 n 的当前位 s[i]否则可以是 9 (实际上 digits 最大也就 9)upper s[i] if is_limit else 9for d in digits:# 如果当前数字大于上界由于 digits 有序后续数字也一定大于上界直接停止if d upper:break# 递归下一位# 新的 is_limit 取决于当前是否受限 且 当前填的数字是否等于上界count dp(i 1, is_limit and d upper)return count# 从第 0 位开始初始状态是受限的 (因为要 n)ans dp(0, True)return ans复杂度分析时间复杂度(log⁡⋅)。状态数为 2⋅log⁡每个状态遍历 个数字。空间复杂度(log⁡)。递归栈深度和记忆化缓存的大小。5. 总结与对比特性解法一数学排列组合解法二数位 DP理解难度低逻辑直观中需要理解递归和状态限制代码量少稍多运行效率极高 (无递归开销)高 (有递归和缓存开销)通用性针对此题特定优化适用于更复杂的数位限制问题推荐程度⭐⭐⭐⭐⭐ (面试首选)⭐⭐⭐ (作为扩展知识)建议在面试中优先使用解法一数学法。它的逻辑清晰不容易出错且运行效率最高。只有当题目条件变得非常复杂例如数字 0 的处理、相邻数字限制等导致数学推导困难时才考虑使用数位 DP。易错点提示字符串比较digits里是字符串n转字符串后也是字符串。在 Python 中1 3是成立的可以直接比较不需要转int。完全匹配不要忘记如果n本身可以由digits组成最后结果要 1解法一中循环结束后的ans 1。位数不足一定要先计算位数小于len(n)的所有情况这部分是纯粹的排列组合。