LeetCode 题解工作台
统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。 给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。 示例 1： 输入： n = 20 输出： 19 解释： 1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。 示例 2：…
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
这道题实际上是求在给定区间 中，满足条件的数的个数。条件与数的大小无关，而只与数的组成有关，因此可以使用数位 DP 的思想求解。数位 DP 中，数的大小对复杂度的影响很小。 对于区间 问题，我们一般会将其转化为 然后再减去 $[1,..l - 1]$ 的问题，即：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20 输出：19 解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：
输入：n = 5 输出：5 解释：1 到 5 所有整数都是特殊整数。
示例 3：
输入：n = 135 输出：110 解释：从 1 到 135 总共有 110 个整数是特殊整数。 不特殊的部分数字为：22 ，114 和 131 。
提示：
1 <= n <= 2 * 109
解题思路
方法一：状态压缩 + 数位 DP
这道题实际上是求在给定区间 中，满足条件的数的个数。条件与数的大小无关，而只与数的组成有关，因此可以使用数位 DP 的思想求解。数位 DP 中，数的大小对复杂度的影响很小。
对于区间 问题，我们一般会将其转化为 然后再减去 的问题，即：
不过对于本题而言，我们只需要求出区间 的值即可。
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
我们根据题目信息，设计一个函数 ，其中：
- 数字 表示当前搜索到的位置，我们从高位开始搜索，即 表示最高位。
- 数字 表示当前数字的状态，即 的第 位为 表示数字 已经被使用过。
- 布尔值 表示当前是否只包含前导 。
- 布尔值 表示当前是否受到上界的限制。
函数的执行过程如下：
如果 超过了数字 的长度，说明搜索结束，如果此时 为真，说明当前数字只包含前导 ，直接返回 ，否则返回 。
如果 为假且 为假且 的状态已经被记忆化，直接返回记忆化的结果。
否则，我们计算当前数字的上界 ，如果 为真， 为当前数字的第 位，否则 。
然后我们遍历 ，对于每个数字 ，如果 的第 位为 ，说明数字 已经被使用过，直接跳过。否则，如果 为真且 ，说明当前数字只包含前导 ，递归搜索下一位，否则递归搜索下一位并更新 的状态。
最后，如果 为假且 为假，将当前状态记忆化。
最终返回答案。
时间复杂度 ，空间复杂度 。其中 为数字 的长度，而 。
相似题目：
class Solution:
def countSpecialNumbers(self, n: int) -> int:
@cache
def dfs(i: int, mask: int, lead: bool, limit: bool) -> int:
if i >= len(s):
return int(lead ^ 1)
up = int(s[i]) if limit else 9
ans = 0
for j in range(up + 1):
if mask >> j & 1:
continue
if lead and j == 0:
ans += dfs(i + 1, mask, True, limit and j == up)
else:
ans += dfs(i + 1, mask | 1 << j, False, limit and j == up)
return ans
s = str(n)
return dfs(0, 0, True, True)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluate the candidate's understanding of dynamic programming and recursion.
- question_mark
Assess if the candidate can handle large input sizes efficiently.
- question_mark
Test the candidate's ability to reduce a brute-force approach to a more optimized solution using state transitions.
常见陷阱
外企场景- error
Forgetting to memoize intermediate results, leading to redundant calculations.
- error
Incorrectly handling leading zeros or invalid digits.
- error
Failing to consider all digit positions, which can result in incorrect counts.
进阶变体
外企场景- arrow_right_alt
Extend the problem to count special integers within a range [m, n].
- arrow_right_alt
Count the number of special integers that can be formed by rearranging the digits of n.
- arrow_right_alt
Modify the problem to include additional constraints, such as excluding certain digits.