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-99种选择第二位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的位数为dlog10(n)排列计算的时间复杂度为O(d)总体时间复杂度为O(d^2)3.2 空间复杂度只需要常数空间存储used数组递归深度为d总体空间复杂度为O(d)3.3 优化方向记忆化排列计算可以预计算阶乘表避免重复计算迭代实现改写递归为迭代减少函数调用开销位运算优化使用位掩码代替boolean数组记录已用数字4. 常见问题与调试技巧4.1 边界条件处理n0时应该返回0n10时直接返回01-9都没有重复数字注意数字首位不能为0的限制4.2 调试技巧小规模测试从n10开始逐步测试中间输出打印每一步的计算结果对比验证与暴力解法结果对比提示在面试中可以先提出暴力解法再优化为数位DP方案展示思考过程。5. 实际应用与变种5.1 实际应用场景这类问题在以下场景有实际应用密码强度检测限制重复数字序列号生成避免重复模式数据压缩利用数字唯一性5.2 相关变种题目计算不含连续相同数字的数目计算数字各位满足单调递增/递减的数目计算包含特定数字模式的数目6. 个人实现心得在实际编码中我发现以下几点特别重要数位处理顺序从高位到低位处理更符合直觉状态设计合理设计状态表示如used数组是关键排列计算单独提取为函数提高代码可读性边界检查最后别忘记检查n本身对于Java实现使用String处理数字比数学运算更直观。在性能要求高的场景可以改用数学方法处理数位。