LeetCode 1012. 至少有 1 位重复的数字
题目描述
题意分析
统计闭区间
1..n内，有至少一个十进制数字重复出现的正整数数量。重复不要求相邻，同一个数即使包含多种重复数字，也只统计这个整数一次。直接逐个判断到
n会做大量重复工作。区间内共有n个正整数，可以先统计每个数位都不重复的正整数，再用总数减去它们，得到目标数量。
解法：数位 DP 计数
核心思路
[!blue]
把候选数补成与
n相同的位数，从最高位向最低位构造。状态dfs(pos, mask, tight)表示：当前处理第pos位，前面真实数位使用过的数字集合为mask，前缀是否仍与n一致由tight表示，返回这些条件下剩余部分的合法填法数。
mask的第d位记录数字d是否用过。当前位选择数字d时，若它已经出现就跳过；否则将这一位加入掩码再处理下一位。这个限制让递归只产生数位互不重复的数。位数不足的候选通过前导零补齐，但这些零不是真实数位，不能占用数字
0。mask == 0表示还没有开始有效数字，此时选择零仍保留空掩码；一旦选了首个非零数字，掩码就不再为空，之后的零也必须像其他真实数字一样登记并去重。还要限制候选不超过
n。tight为真时，当前位最多选到n的对应数字；选相同数字就继续受限，选更小数字后，整个数已经小于n，后面的位都可以自由选0..9。原先已经自由的状态不会再次变成受限。自由状态的未来只取决于位置和已用数字，与此前数字的排列顺序无关，因此只按
pos、mask记忆化即可。受限状态的后续范围不同，不能存入这张省略了tight的缓存。填完全部位置时得到一种构造，返回
1。其中全选前导零的唯一路径代表数字0，不属于1..n，所以先把递归计数减一，再从n中扣除其余无重复正整数。固定长度的补零方式是唯一的，不会让同一个短数被重复统计。
解题步骤
- 将
n转成数位序列，建立按位置和掩码索引的缓存，初值为-1表示未计算。- 从
dfs(0, 0, true)开始；全部位置处理完时返回一种构造。- 根据
tight确定当前可选数字上界，逐个枚举数字。- 尚未开始且选零时保持空掩码；其他情况只允许尚未使用的数字，并更新掩码。
- 根据是否继续贴合上界更新
tight，累加下一位置的填法数；仅缓存自由状态。- 递归总数减去代表零的一种构造，再用
n减去无重复正整数数目。
代码实现
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);
}
// 递归包含数字 0，先扣除它，再用补集得到重复数字的数量。
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;
// 前导零不是真实数位，不占用数字 0 的掩码。
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
// 前导零不是真实数位，不占用数字 0 的掩码。
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
}
// 递归包含数字 0，先扣除它，再用补集得到重复数字的数量。
uniquePositive := dfs(0, 0, true) - 1
return n - uniquePositive
}
复杂度分析
- 时间复杂度：设十进制位数为 L，时间为 $O(L\cdot2^{10}\cdot10)$，每个状态最多枚举 10 个数字。
- 空间复杂度：$O(L\cdot2^{10})$，用于记忆化表；递归深度为 L。
关键点总结
[!green]
- 补集让“至少一位重复”变成构造时逐位禁止重复，避免给同一个重复数反复计数。
- 空掩码已经表示尚未开始有效数字，不需要再增加一个重复的开始标记。
- 前导零负责统一位数，真实零参与去重，两者取决于有效数字是否已经开始。
- 缓存键只有位置和掩码，因此只能复用不再受上界限制的状态。
易错点总结
[!yellow]
- 前导零写入掩码，会提前占用数字零，并把多个补位零误判为重复，漏掉较短的合法整数。
- 忘记扣除全前导零路径，会把不在计数区间内的零也算进无重复正整数。
- 某一位已经选得更小，后续仍按
n限制，会遗漏本来已经低于上界的构造。- 把受限结果存到只含
pos、mask的缓存，会与后续完全自由的同形状态混用。mask只需记录是否使用，不应把不同前缀顺序也并入键，否则会失去相同剩余问题的复用。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 357. 统计各位数字都不同的数字个数 | 中等 | 重复数码数量可由总数减无重复数码数量得到，本题上界任意，需要处理与上界相等的前缀。 |
| 902. 最大为 N 的数字组合 | 困难 | 同样按数位限制计数，原题限制可用数字集合，本题用访问掩码限制数码重复。 |