1. 问题背景与需求分析

LeetCode 1012题"至少有1位重复的数字"是一个典型的数位动态规划问题。题目要求我们计算小于等于给定整数n的所有数字中，至少有一位数字重复出现的数字个数。这个问题看似简单，但实际考察了多种编程技巧和数学思维。

从函数签名public int numDupDigitsAtMostN(int n)可以看出，这是一个Java实现的方法。题目属于数位统计类问题，与排列组合、动态规划等算法密切相关。这类问题在实际面试中经常出现，因为它能很好地考察候选人对数字处理、递归思维和数学建模的能力。

2. 问题理解与数学建模

2.1 问题转化思路

直接计算"至少有一位重复"的数字数量比较困难，我们可以采用补集的思想：

总数 = 无重复数字的个数 + 至少有一位重复的数字个数

因此： 至少有一位重复的数字个数 = 总数 - 无重复数字的个数

其中：

• 总数就是n本身
• 无重复数字的个数可以通过排列组合计算得出

2.2 无重复数字的计数方法

计算小于等于n且所有数字都不重复的数字数量，可以分为两种情况：

1. 数字位数小于n的位数：可以直接用排列公式计算
2. 数字位数等于n的位数：需要逐位比较，确保生成的数字不大于n

例如，对于n=356：

• 1位数：1-9共9个
• 2位数：9×9=81个（第一位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 边界条件处理

需要特别注意以下边界条件：

1. 数字0的处理：0本身没有重复数字，但题目要求的是正整数
2. 数字位数变化时的处理：如从99到100的过渡
3. 数字中已经出现重复时的处理：可以提前终止递归

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 实际应用场景

这类数位统计问题在实际中有多种应用：

1. 密码强度检查：确保密码中有重复字符
2. 身份证号/电话号码验证：检查是否有连续重复数字
3. 数据清洗：识别和处理可能有误的重复数字记录

6.2 问题变种

基于本题可以衍生出多种变种问题：

1. 恰好有k位重复的数字个数
2. 连续重复数字的数字个数
3. 特定模式的重复数字（如AABB、ABAB等）

6.3 性能优化方向

对于更大的n（如10^18），可以考虑：

1. 非递归实现
2. 更高效的排列计算
3. 并行处理不同数位

7. 常见错误与调试技巧

在实现这类数位DP问题时，容易犯以下错误：

1. 忽略前导零的处理：第一位不能为0，但其他位可以
2. 重复数字的判断不完整：需要全局记录已使用的数字
3. 排列计算错误：特别是部分排列的情况
4. 边界条件处理不当：如n本身是否包含重复数字

调试时可以：

1. 打印中间结果，观察递归过程
2. 对小规模测试用例手动计算验证
3. 使用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实现注意事项

1. 整数转字符串处理数位比数学运算更直观
2. boolean数组比HashSet更高效
3. 注意int的范围限制，题目保证n<=10^9，不会溢出

9.2 其他语言实现差异

在Python中，可以利用其强大的内置函数简化实现：

def numDupDigitsAtMostN(self, n: int) -> int: s = str(n) # 计算无重复的数字个数 @lru_cache(maxsize=None) 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问题的关键在于：

1. 理解问题并正确建模：将大问题分解为子问题
2. 选择合适的算法策略：这里使用数位DP+排列组合
3. 处理好边界条件和特殊情况：如前导零、数字重复等
4. 优化实现细节：如使用位运算代替集合操作

在实际编码面试中，建议：

1. 先解释思路再写代码
2. 用具体例子说明算法过程
3. 主动讨论时间/空间复杂度
4. 考虑边界情况和测试用例

通过这道题目，我们可以深入理解数位DP的应用场景和实现技巧，这对于解决类似的数字统计问题非常有帮助。