1. 问题解析：LeetCode 1012至少有1位重复的数字
这道题目要求我们计算从1到n的所有整数中，至少有一位数字重复出现的数字个数。这类问题在算法竞赛和面试中属于经典题型，主要考察数位动态规划（Digit DP）和组合数学的应用能力。
1.1 问题重述与转化
题目给出的函数签名为：
public int numDupDigitsAtMostN(int n)直接计算"至少有一位重复"的数字数量比较困难，更聪明的做法是采用补集思想：
- 总数：n本身
- 无重复数字的数目：计算所有数字都不相同的数字个数
- 结果 = 总数 - 无重复数字的数目
这种转化将问题简化为计算"所有数字都不相同"的数字个数，这正是数位DP擅长的领域。
1.2 数位DP基础概念
数位DP是一种专门用于解决数字各位上数字满足特定条件问题的动态规划方法。其核心思想是：
- 将数字按位拆分处理
- 记忆化已计算的状态
- 通过限制条件控制数字范围
对于本题，我们需要记录以下状态：
- 当前处理到的数位位置
- 已经使用的数字集合
- 是否已经小于n的前缀（决定当前位的选择范围）
2. 解决方案设计与实现
2.1 组合数学解法
我们可以将问题分解为计算所有位数不超过n的数字中不含重复数字的数目。对于k位数，不含重复数字的数目计算如下：
- 第一位：1-9（9种选择）
- 第二位：0-9除去第一位（9种选择）
- 第三位：0-9除去前两位（8种选择）
- ...
- 第k位：0-9除去前k-1位（10-(k-1)种选择）
因此，k位数中不含重复数字的数目为： 9 × 9 × 8 × ... × (10 - k + 1)
2.2 数位DP实现细节
以下是Java实现的详细解析：
public int numDupDigitsAtMostN(int n) { String s = String.valueOf(n); int len = s.length(); // 计算位数小于len的无重复数字数目 int total = 0; for (int i = 1; i < len; i++) { total += 9 * permutation(9, i - 1); } // 计算位数等于len的无重复数字数目 boolean[] used = new boolean[10]; for (int i = 0; i < len; i++) { int digit = s.charAt(i) - '0'; for (int j = (i == 0 ? 1 : 0); j < digit; j++) { if (!used[j]) { total += permutation(9 - i, len - i - 1); } } if (used[digit]) break; used[digit] = true; } // 加上n本身是否无重复 boolean noDup = true; for (int i = 0; i < 10; i++) { if (count[i] > 1) { noDup = false; break; } } if (noDup) total++; return n - total; } private int permutation(int n, int k) { if (k == 0) return 1; return n * permutation(n - 1, k - 1); }2.3 关键步骤解析
- 数字转换：将n转换为字符串，便于逐位处理
- 小于位数的计算：对于所有位数小于n的数字，直接使用排列组合公式计算
- 等于位数的计算：
- 从最高位开始处理
- 对于每一位，考虑所有小于当前数字的选择
- 使用used数组记录已经使用的数字
- 计算剩余位的排列可能性
- 检查n本身：最后需要单独检查n是否不含重复数字
3. 复杂度分析与优化
3.1 时间复杂度
- 数字n的位数为d=log10(n)
- 排列计算的时间复杂度为O(d)
- 总体时间复杂度为O(d^2)
3.2 空间复杂度
- 只需要常数空间存储used数组
- 递归深度为d
- 总体空间复杂度为O(d)
3.3 优化方向
- 记忆化排列计算：可以预计算阶乘表，避免重复计算
- 迭代实现：改写递归为迭代，减少函数调用开销
- 位运算优化：使用位掩码代替boolean数组记录已用数字
4. 常见问题与调试技巧
4.1 边界条件处理
- n=0时应该返回0
- n<10时直接返回0（1-9都没有重复数字）
- 注意数字首位不能为0的限制
4.2 调试技巧
- 小规模测试：从n=10开始逐步测试
- 中间输出：打印每一步的计算结果
- 对比验证：与暴力解法结果对比
提示：在面试中，可以先提出暴力解法，再优化为数位DP方案，展示思考过程。
5. 实际应用与变种
5.1 实际应用场景
这类问题在以下场景有实际应用：
- 密码强度检测（限制重复数字）
- 序列号生成（避免重复模式）
- 数据压缩（利用数字唯一性）
5.2 相关变种题目
- 计算不含连续相同数字的数目
- 计算数字各位满足单调递增/递减的数目
- 计算包含特定数字模式的数目
6. 个人实现心得
在实际编码中，我发现以下几点特别重要：
- 数位处理顺序：从高位到低位处理更符合直觉
- 状态设计：合理设计状态表示（如used数组）是关键
- 排列计算：单独提取为函数提高代码可读性
- 边界检查：最后别忘记检查n本身
对于Java实现，使用String处理数字比数学运算更直观。在性能要求高的场景，可以改用数学方法处理数位。
