LeetCode 题解工作台
最大为 N 的数字组合
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5'] ，我们可以写数字，如 '13' , '551' , 和 '1351315' 。 返回 可以生成的小于或等于给定整数 n 的正整数的个数 …
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
这道题实际上是求在给定区间 中，由 `digits` 中的数字生成的正整数的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。 对于区间 问题，我们一般会将其转化为 然后再减去 $[1,..l - 1]$ 的问题，即：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 1：
输入：digits = ["1","3","5","7"], n = 100 输出：20 解释： 可写出的 20 个数字是： 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：
输入：digits = ["1","4","9"], n = 1000000000 输出：29523 解释： 我们可以写 3 个一位数字，9 个两位数字，27 个三位数字， 81 个四位数字，243 个五位数字，729 个六位数字， 2187 个七位数字，6561 个八位数字和 19683 个九位数字。 总共，可以使用D中的数字写出 29523 个整数。
示例 3:
输入：digits = ["7"], n = 8 输出：1
提示：
1 <= digits.length <= 9digits[i].length == 1digits[i]是从'1'到'9'的数digits中的所有值都 不同digits按 非递减顺序 排列1 <= n <= 109
解题思路
方法一：数位 DP
这道题实际上是求在给定区间 中，由 digits 中的数字生成的正整数的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。
对于区间 问题，我们一般会将其转化为 然后再减去 的问题，即：
不过对于本题而言，我们只需要求出区间 的值即可。
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
基本步骤如下：
我们将数字 转化为字符串 ，记字符串 的长度为 。
接下来，我们设计一个函数 ，表示当前处理到字符串的第 位，到最后一位的方案数。其中：
- 数字 表示当前处理到字符串 的第 位；
- 布尔值 表示是否只包含前导零；
- 布尔值 表示当前位置是否受到上界的限制。
函数的执行过程如下：
如果 大于等于 ，说明我们已经处理完了所有的位数，此时如果 为真，说明当前的数字是前导零，我们应当返回 ；否则，我们应当返回 。
否则，我们计算当前位置的上界 ，如果 为真，则 为 对应的数字，否则 为 。
然后，我们在 的范围内枚举当前位置的数字 ，如果 为 且 为真，我们递归计算 ；否则，如果 在 中，我们递归计算 。累加所有的结果即为答案。
最后，我们返回 即可。
时间复杂度 ，空间复杂度 。其中 。
相似题目：
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
@cache
def dfs(i: int, lead: int, limit: bool) -> int:
if i >= len(s):
return lead ^ 1
up = int(s[i]) if limit else 9
ans = 0
for j in range(up + 1):
if j == 0 and lead:
ans += dfs(i + 1, 1, limit and j == up)
elif j in nums:
ans += dfs(i + 1, 0, limit and j == up)
return ans
s = str(n)
nums = {int(x) for x in digits}
return dfs(0, 1, True)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\log N) |
| 空间 | O(\log N) |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to break down the problem into sub-problems based on the number of digits and constraints.
- question_mark
Assess how well the candidate can implement dynamic programming and apply the state transition efficiently.
- question_mark
Gauge the candidate’s understanding of optimization techniques like binary search within dynamic programming solutions.
常见陷阱
外企场景- error
Misunderstanding the digit-wise approach, resulting in an inefficient solution that doesn't properly account for each digit's contribution to the overall count.
- error
Not correctly handling the constraint of being less than or equal to n when transitioning between states, leading to over-counting of invalid numbers.
- error
Failure to optimize the solution using binary search, leading to unnecessary brute-force calculations.
进阶变体
外企场景- arrow_right_alt
Consider cases where digits have only one element, which limits the number of possible numbers.
- arrow_right_alt
Handle very large n values efficiently, ensuring the solution scales to n values close to 10^9.
- arrow_right_alt
Test the algorithm with various sets of digits, including edge cases like the smallest possible n.