LeetCode 1012. 至少有 1 位重复的数字
目录
题目描述
题意分析
统计
[1, n]里有多少个整数，它的十进制表示中至少有两位数字相同。「至少有一位重复」是个非常松的条件，正面统计要枚举「哪一位和哪一位重复」，各种情形互相重叠，容斥会写到崩溃。而它的补集——每一位都互不相同——却是个极其规整的条件：从高位往低位填数字时，只需保证新填的数字没被用过。所以第一步必然是正难则反，先求出无重复数字的个数
good，答案就是n - good。补集统计仍然不能一个个枚举：约束给的是
1 ≤ n ≤ 10^9，十亿次判断在题目时限内跑不完，而且这类题的标准形态就是「按位构造 + 数位上界限制」。十进制下最多 10 位，每位 10 种选择，真正的状态量极小。按位构造时，只有两件事会影响后面还能填什么：已经用掉了哪些数字，以及前面几位是否与
n完全相同（相同则当前位不能超过n的对应位，否则可以自由填 0 到 9）。前者因为只关心「用没用过」而不关心顺序，可以压成一个 10 位的二进制集合；后者是一个布尔标志。边界有两处必须想清楚。一是前导零：
5这个数在 3 位框架下写成005，那两个 0 不是「使用了数字 0」，不能占用集合，否则10、20这类含 0 的数会被误判成重复。二是数字 0 本身：按位构造统计的是[0, n]，而题目要的是[1, n]，所以要减掉 0 这一个。
解法：数位 DP 计数
核心思路
直接统计“至少有一位重复”会遇到大量重叠情况。它的补集更规整：先统计
[1,n]中各位数字互不相同的数，再用n减去这个数量。对
n从高位到低位构造数字，定义：
dfs(pos, mask, tight)：前pos位已经确定、已使用数字集合为mask、当前前缀是否仍与n的前缀相同，在此条件下补完剩余数位的合法方案数。
mask的第d位表示数字d是否已经出现在有效数字中；tight = true时，当前位最多取n的对应位；否则可取 0 到 9；mask == 0 && d == 0表示仍在跳过前导零，这个 0 不应写入mask；- 一旦数字已经开始，只有
d尚未出现在mask中时才能继续。状态不变量：进入
dfs(pos, mask, tight)时，mask精确记录已构造的有效前缀中出现过的数字，tight精确表示该前缀是否贴着上界。 按上述规则枚举下一位，会且只会生成不超过n、有效数位互不重复的十进制表示。到达末尾时返回 1，表示得到一种完整构造。全程选择前导零的路径对应数字 0，因此
dfs(0,0,true)统计的是[0,n]；减 1 才是[1,n]中无重复数字的数量。只有
tight = false的状态可以按(pos, mask)记忆化，因为此时后续上界固定为 9，结果与前缀具体取值无关。受限状态依赖n的当前数位，不能与同位置、同掩码的自由状态混用。
解题步骤
- 将
n转成从高位到低位排列的数位序列。- 建立
digits.length * 2^10的记忆化表，初值设为-1。- 从
dfs(0, 0, true)开始枚举当前位：
- 尚未开始且选择 0：保持
mask = 0；- 否则若该数字未使用：把对应位加入
mask；- 下一层的
tight为tight && d == limit。- 仅在
tight = false时读取和写入记忆化表。- 令
uniquePositive = dfs(0,0,true) - 1，返回n - uniquePositive。以
n = 20为例：
- 首位取前导零，可得到
0..9，共 10 个无重复数（包含 0）；- 首位取 1，末位可取除 1 外的 9 个数字，得到 9 个；
- 首位取 2 时受上界限制，末位只能取 0，得到
20。因此
[0,20]中共有 20 个无重复数，排除 0 后有 19 个，答案为20-19=1，唯一的重复数是 11。边界n=9时无重复正数恰有 9 个，答案自然为 0。
代码实现
import java.util.Arrays;
class Solution {
private char[] digits;
private int[][] memo;
public int numDupDigitsAtMostN(int n) {
digits = String.valueOf(n).toCharArray();
memo = new int[digits.length][1 << 10];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
int uniquePositive = dfs(0, 0, true) - 1;
return n - uniquePositive;
}
private int dfs(int pos, int mask, boolean tight) {
if (pos == digits.length) {
return 1;
}
if (!tight && memo[pos][mask] != -1) {
return memo[pos][mask];
}
int limit = tight ? digits[pos] - '0' : 9;
int ways = 0;
for (int d = 0; d <= limit; d++) {
boolean nextTight = tight && d == limit;
if (mask == 0 && d == 0) {
ways += dfs(pos + 1, 0, nextTight);
continue;
}
int bit = 1 << d;
if ((mask & bit) == 0) {
ways += dfs(pos + 1, mask | bit, nextTight);
}
}
if (!tight) {
memo[pos][mask] = ways;
}
return ways;
}
}
import "strconv"
func numDupDigitsAtMostN(n int) int {
digits := strconv.Itoa(n)
memo := make([][]int, len(digits))
for i := range memo {
memo[i] = make([]int, 1<<10)
for mask := range memo[i] {
memo[i][mask] = -1
}
}
var dfs func(pos, mask int, tight bool) int
dfs = func(pos, mask int, tight bool) int {
if pos == len(digits) {
return 1
}
if !tight && memo[pos][mask] != -1 {
return memo[pos][mask]
}
limit := 9
if tight {
limit = int(digits[pos] - '0')
}
ways := 0
for d := 0; d <= limit; d++ {
nextTight := tight && d == limit
if mask == 0 && d == 0 {
ways += dfs(pos+1, 0, nextTight)
continue
}
bit := 1 << d
if mask&bit == 0 {
ways += dfs(pos+1, mask|bit, nextTight)
}
}
if !tight {
memo[pos][mask] = ways
}
return ways
}
uniquePositive := dfs(0, 0, true) - 1
return n - uniquePositive
}
复杂度分析
设
L为n的十进制位数。
- 时间复杂度： $O(L \cdot 2^{10} \cdot 10)$。最多有 $L\cdot2^{10}$ 个可复用状态，每个状态枚举 10 个数字；每层至多一个受限分支，不改变数量级。
- 空间复杂度： $O(L \cdot 2^{10})$，用于记忆化表；递归栈深度为 $O(L)$。
关键点总结
- 用补集把“至少一位重复”转化为“所有有效数位互不相同”。
- 位掩码只记录数字是否使用过，不需要记录出现顺序；首个有效数位不可能是 0，所以数字一旦开始，
mask必然非零，mask == 0可以安全地兼作started == false，无需再加一维状态。tight是上界约束：只有此前贴着上界且当前位也取到上界，下一位才继续受限。- 记忆化仅缓存自由状态；状态定义、前导零语义和缓存范围必须保持一致。
- 递归结果包含数字 0，做补集前必须先将它排除。
易错点总结
- 把前导零记入
mask： 在三位框架里，数字 5 写作005；两个占位 0 不是真实数位，不能据此判重，也不能阻止10使用真实的数字 0。- 缓存受限状态却不把
tight纳入键： 例如n=210时，自由前缀12与受限前缀21可到达相同的(pos, mask)，但末位上界分别是 9 和 0，二者结果不能复用。- 错误传递
tight： 若当前位已经小于上界，后续位应永久自由；若当前位等于上界，后续仍须受限。少任一条件都会漏算或统计大于n的数。- 忘记排除全前导零路径：
dfs包含数字 0，直接用n-dfs(...)会让答案少 1；n=20会错误得到 0。- 掩码只开
1<<9： 十进制有 0 到 9 共 10 个数字，使用数字 9 时会越界；维度必须是1<<10。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 357. 统计各位数字都不同的数字个数 | 中等 | 上界固定为 $10^k$，没有 tight 维度，可以直接用排列数公式，是本题的简化版 |
| 902. 最大为 N 的数字组合 | 困难 | 可用数字被限定在给定集合内，业务状态从「用过哪些」变成「能否使用」，前导零处理方式不同 |
| 233. 数字 1 的个数 | 困难 | 统计的不是数的个数而是数字 1 出现的次数，DP 返回值要携带计数而非布尔式的方案数 |
| 剑指 Offer 43. 1～n 整数中 1 出现的次数 | 困难 | 与 233 同题，常用逐位贡献法求解，可与数位 DP 模板互相印证 |
| 面试题 17.06. 2出现的次数 | 困难 | 把 233 的目标数字换成 2，用来检验模板是否真的与具体数字解耦 |