1. 问题背景与需求分析LeetCode 1012题至少有1位重复的数字是一个典型的数位动态规划问题。题目要求我们计算小于等于给定整数n的所有数字中至少有一位数字重复出现的数字个数。这个问题看似简单但实际考察了多种编程技巧和数学思维。从函数签名public int numDupDigitsAtMostN(int n)可以看出这是一个Java实现的方法。题目属于数位统计类问题与排列组合、动态规划等算法密切相关。这类问题在实际面试中经常出现因为它能很好地考察候选人对数字处理、递归思维和数学建模的能力。2. 问题理解与数学建模2.1 问题转化思路直接计算至少有一位重复的数字数量比较困难我们可以采用补集的思想总数 无重复数字的个数 至少有一位重复的数字个数因此 至少有一位重复的数字个数 总数 - 无重复数字的个数其中总数就是n本身无重复数字的个数可以通过排列组合计算得出2.2 无重复数字的计数方法计算小于等于n且所有数字都不重复的数字数量可以分为两种情况数字位数小于n的位数可以直接用排列公式计算数字位数等于n的位数需要逐位比较确保生成的数字不大于n例如对于n3561位数1-9共9个2位数9×981个第一位1-9第二位0-9但不能与第一位重复3位数需要特殊处理确保不大于356且各位不重复3. 算法设计与实现3.1 动态规划解法我们可以使用数位DP的方法来解决这个问题。主要思路是将数字拆分成各个数位然后从高位到低位进行递归处理。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]; total countNumbers(s, 0, used); return n - total; } private int countNumbers(String s, int index, boolean[] used) { if (index s.length()) { return 1; } int digit s.charAt(index) - 0; int count 0; for (int i 0; i digit; i) { if (!used[i]) { if (i 0 index 0) continue; // 第一位不能为0 count permutation(9 - index, s.length() - index - 1); } } if (!used[digit]) { used[digit] true; count countNumbers(s, index 1, used); } return count; } private int permutation(int n, int k) { int res 1; for (int i 0; i k; i) { res * (n - i); } return res; }3.2 算法复杂度分析时间复杂度O(log n)因为我们需要处理n的每一位数字空间复杂度O(log n)用于存储数字的每一位和递归调用栈4. 关键点解析与优化4.1 排列计算的优化在计算排列数时我们可以预计算阶乘或者使用动态规划来优化。对于本题给定的n范围(1 n 10^9)直接计算排列数已经足够高效。4.2 边界条件处理需要特别注意以下边界条件数字0的处理0本身没有重复数字但题目要求的是正整数数字位数变化时的处理如从99到100的过渡数字中已经出现重复时的处理可以提前终止递归4.3 记忆化搜索的应用虽然本题的递归深度不大但对于更大的n可以考虑使用记忆化搜索来优化性能。不过对于LeetCode的测试用例范围简单的递归实现已经足够。5. 测试用例与验证为了验证算法的正确性我们需要设计各种边界情况的测试用例Test public void testNumDupDigitsAtMostN() { Solution solution new Solution(); assertEquals(1, solution.numDupDigitsAtMostN(11)); // 11 assertEquals(0, solution.numDupDigitsAtMostN(1)); // 无重复 assertEquals(10, solution.numDupDigitsAtMostN(20)); // 11,22 assertEquals(262, solution.numDupDigitsAtMostN(1000)); assertEquals(994388230, solution.numDupDigitsAtMostN(1000000000)); }6. 实际应用与扩展6.1 实际应用场景这类数位统计问题在实际中有多种应用密码强度检查确保密码中有重复字符身份证号/电话号码验证检查是否有连续重复数字数据清洗识别和处理可能有误的重复数字记录6.2 问题变种基于本题可以衍生出多种变种问题恰好有k位重复的数字个数连续重复数字的数字个数特定模式的重复数字如AABB、ABAB等6.3 性能优化方向对于更大的n如10^18可以考虑非递归实现更高效的排列计算并行处理不同数位7. 常见错误与调试技巧在实现这类数位DP问题时容易犯以下错误忽略前导零的处理第一位不能为0但其他位可以重复数字的判断不完整需要全局记录已使用的数字排列计算错误特别是部分排列的情况边界条件处理不当如n本身是否包含重复数字调试时可以打印中间结果观察递归过程对小规模测试用例手动计算验证使用IDE的调试功能逐步跟踪执行8. 算法比较与替代方案除了数位DP这个问题还可以用其他方法解决8.1 暴力法对于小范围的n可以直接暴力检查每个数字是否有重复public int numDupDigitsAtMostN(int n) { int count 0; for (int i 1; i n; i) { if (hasDuplicate(i)) { count; } } return count; } private boolean hasDuplicate(int num) { boolean[] digits new boolean[10]; while (num 0) { int d num % 10; if (digits[d]) { return true; } digits[d] true; num / 10; } return false; }这种方法时间复杂度为O(n log n)对于大n效率太低。8.2 数学组合法可以完全用数学组合公式计算无重复数字的个数避免递归public int numDupDigitsAtMostN(int n) { String s String.valueOf(n); int len s.length(); int total 0; // 计算位数小于len的 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; if (i len - 1) total; } return n - total; }这种方法避免了递归性能更稳定。9. 语言特性与实现细节9.1 Java实现注意事项整数转字符串处理数位比数学运算更直观boolean数组比HashSet更高效注意int的范围限制题目保证n10^9不会溢出9.2 其他语言实现差异在Python中可以利用其强大的内置函数简化实现def numDupDigitsAtMostN(self, n: int) - int: s str(n) # 计算无重复的数字个数 lru_cache(maxsizeNone) def dp(pos, tight, mask, is_num): if pos len(s): return int(is_num) limit int(s[pos]) if tight else 9 total 0 if not is_num: total dp(pos 1, False, mask, False) for d in range(0 if is_num else 1, limit 1): new_tight tight and (d limit) new_mask mask | (1 d) if is_num else (1 d) if (mask (1 d)) 0: total dp(pos 1, new_tight, new_mask, True) return total return n - dp(0, True, 0, False)Python的实现更简洁但原理相同。10. 总结与个人心得解决这类数位DP问题的关键在于理解问题并正确建模将大问题分解为子问题选择合适的算法策略这里使用数位DP排列组合处理好边界条件和特殊情况如前导零、数字重复等优化实现细节如使用位运算代替集合操作在实际编码面试中建议先解释思路再写代码用具体例子说明算法过程主动讨论时间/空间复杂度考虑边界情况和测试用例通过这道题目我们可以深入理解数位DP的应用场景和实现技巧这对于解决类似的数字统计问题非常有帮助。