LeetCode 题解工作台
统计各位数字都不同的数字个数
给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 n 。 示例 1： 输入： n = 2 输出： 91 解释： 答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x 示例 2： 输入： n = 0 输出： 1 提示： 0
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
这道题实际上是求在给定区间 中，满足条件的数的个数。条件与数的大小无关，而只与数的组成有关，因此可以使用数位 DP 的思想求解。数位 DP 中，数的大小对复杂度的影响很小。 对于区间 问题，我们一般会将其转化为 然后再减去 $[1,..l - 1]$ 的问题，即：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。
示例 1：
输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。
示例 2：
输入：n = 0 输出：1
提示：
0 <= n <= 8
解题思路
方法一：状态压缩 + 数位 DP
这道题实际上是求在给定区间 中，满足条件的数的个数。条件与数的大小无关，而只与数的组成有关，因此可以使用数位 DP 的思想求解。数位 DP 中，数的大小对复杂度的影响很小。
对于区间 问题，我们一般会将其转化为 然后再减去 的问题，即：
不过对于本题而言，我们只需要求出区间 的值即可。
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
我们根据题目信息，设计一个函数 ，其中：
- 数字 表示当前搜索到的位置，我们从高位开始搜索，即 表示最高位。
- 数字 表示当前数字的状态，即 的第 位为 表示数字 已经被使用过。
- 布尔值 表示当前是否只包含前导 。
函数的执行过程如下：
如果 超过了数字 的长度，即 ，说明搜索结束，直接返回 。
否则，我们从 到 枚举位置 的数字 ，对于每一个 ：
- 如果 的第 位为 ，说明数字 已经被使用过，直接跳过。
- 如果 为真且 ，说明当前数字只包含前导 ，递归到下一层时，此时 仍为真。
- 否则，我们递归到下一层，更新 的第 位为 ，并将 更新为假。
最后，我们将所有递归到下一层的结果累加，即为答案。
答案为 。
关于函数的实现细节，可以参考下面的代码。
时间复杂度 ，空间复杂度 。其中 为数字 的长度，而 。
相似题目：
class Solution:
def countNumbersWithUniqueDigits(self, n: int) -> int:
@cache
def dfs(i: int, mask: int, lead: bool) -> int:
if i < 0:
return 1
ans = 0
for j in range(10):
if mask >> j & 1:
continue
if lead and j == 0:
ans += dfs(i - 1, mask, True)
else:
ans += dfs(i - 1, mask | 1 << j, False)
return ans
return dfs(n - 1, 0, True)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates a good understanding of dynamic programming concepts and its application to state transitions.
- question_mark
The candidate recognizes the trade-offs between backtracking and dynamic programming, opting for the most efficient approach based on the problem constraints.
- question_mark
The candidate is aware of optimization techniques and can suggest mathematical shortcuts when applicable.
常见陷阱
外企场景- error
Failing to account for repeated digits when forming numbers, especially when the input size is large.
- error
Not considering edge cases such as n = 0, where the only valid number is 0.
- error
Using an inefficient brute-force approach, which may lead to timeouts or excessive computation for larger values of n.
进阶变体
外企场景- arrow_right_alt
How would the solution change if n were larger (e.g., n = 10)?
- arrow_right_alt
What is the effect of reducing the range from 0 to 10^n to a more limited range, such as 0 to 10^5?
- arrow_right_alt
Can you extend this approach to work with non-decimal bases or larger sets of digits?