当前位置：首页 > news >正文

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

news 2026/7/1 2:10:43

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×4=16 个)
三位数：必须 ≤100。由于最小能组成的三位数是 111，已经大于 100，所以三位数个数为 0。
总计：4+16=20。

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 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、包含特定限制等）很有帮助。

思路：

同样先处理位数少于 � 的情况（这部分 DP 处理起来比较麻烦，不如数学法直接，所以通常结合使用）。
使用 DFS + 记忆化搜索来统计位数等于 � 且 ≤� 的数字个数。
状态定义：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。

易错点提示：

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