首页/资讯中心/详情

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

LeetCode 902 最大为 N 的数字组合：python3 题解
📅 发布时间：2026/7/1 2:10:43

1. 题目解读

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

关键点：

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

示例分析：

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

2. 核心解题思路

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

  1. 位数少于n的数字：

    • 假设n有 � 位。任何位数 �<� 的数字，只要由digits组成，一定小于n。
    • 对于长度为 � 的数字，每一位都有len(digits)种选择。
    • 所以长度为 � 的数字共有len(digits)^k个。
    • 我们需要累加 �=1 到 �−1 的所有情况。

  2. 位数等于n的数字：

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

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

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

代码实现

from typing import List
class 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 = False
for 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 = True
break
else:
# 情况 C: 当前位 d 大于 n 的对应位 char
# 由于 digits 是有序的，后面的 d 肯定也大于 char
# 直接跳出内层循环，且不再继续匹配后续位
# 这里的 break 会触发下方 for-else 的 else 分支吗？不会，因为 break 了
# 但我们需要标记“无法完全匹配前缀”，所以直接返回当前 ans
return 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 += 1
return ans

复杂度分析

  • 时间复杂度：�(log⁡�⋅�)。其中 log⁡� 是n的位数，� 是digits的长度。由于 �≤9，可以看作 �(log⁡�)。
  • 空间复杂度：�(log⁡�)。用于存储n的字符串形式。

4. 解法二：数位动态规划 (Digit DP)

（我不太会数位 dp，也暂时懒得学了，所以没看这部分）

数位 DP 是解决“统计满足特定条件的数字个数”这类问题的通用模板。虽然对于这道题，数学法更简单，但学习 DP 思路对解决更复杂的变体（例如包含 0、包含特定限制等）很有帮助。

思路：

  1. 同样先处理位数少于 � 的情况（这部分 DP 处理起来比较麻烦，不如数学法直接，所以通常结合使用）。
  2. 使用 DFS + 记忆化搜索来统计位数等于 � 且 ≤� 的数字个数。
  3. 状态定义：dfs(index, is_limit)
    • index: 当前正在填第几位（从 0 开始）。
    • is_limit: 布尔值，表示当前位是否受到n的对应位限制。
      • 如果is_limit为True，当前位最大只能填s[index]。
      • 如果is_limit为False，当前位可以填digits中的任意值。

代码实现

from typing import List
from functools import lru_cache
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], n: int) -> 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[i]；否则可以是 '9' (实际上 digits 最大也就 '9')
upper = s[i] 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 位开始，初始状态是受限的 (因为要 <= n)
ans += dp(0, True)
return ans

复杂度分析

  • 时间复杂度：�(log⁡�⋅�)。状态数为 2⋅log⁡�，每个状态遍历 � 个数字。
  • 空间复杂度：�(log⁡�)。递归栈深度和记忆化缓存的大小。

5. 总结与对比

特性解法一：数学排列组合解法二：数位 DP
理解难度低，逻辑直观中，需要理解递归和状态限制
代码量少稍多
运行效率极高 (无递归开销)高 (有递归和缓存开销)
通用性针对此题特定优化适用于更复杂的数位限制问题
推荐程度⭐⭐⭐⭐⭐ (面试首选)⭐⭐⭐ (作为扩展知识)

建议：
在面试中，优先使用解法一（数学法）。它的逻辑清晰，不容易出错，且运行效率最高。只有当题目条件变得非常复杂（例如数字 0 的处理、相邻数字限制等）导致数学推导困难时，才考虑使用数位 DP。

易错点提示：

  1. 字符串比较：digits里是字符串，n转字符串后也是字符串。在 Python 中'1' < '3'是成立的，可以直接比较，不需要转int。
  2. 完全匹配：不要忘记如果n本身可以由digits组成，最后结果要 +1（解法一中循环结束后的ans += 1）。
  3. 位数不足：一定要先计算位数小于len(n)的所有情况，这部分是纯粹的排列组合。