LeetCode 题解系列(1012)：至少有 1 位重复的数字

题目描述:

给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数的个数。
示例 1：

输入：20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：

输入：100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：

输入：1000
输出：262  

提示：

1 <= N <= 10^9

解法一: 数位DP

1. 求数字N有多少个重复的数字，可以将其转换为求数字N有多少个不重复的数字，因为求不重复的数字可以更好地使用排列组合来求解。
2. 现在的目的是将这个数字分解成可以按一定规律计算其所有不重复数位的排列组合。
3. 假设数字有 k 位，将数字分为两种情况，k 位是 0 和 k 位不是 0 分别进行求种数。
4. 对于 k 位是 0，即位数小于 k，此时的最高位 m 只能选择 1~9，后面m-1位每位选择种数是9xA(i,9)。
5. 对于 k 位不是 0，从最高位开始计算，比如最高位取 3，那么 1~2 后面的组合就是 A(k-1,9)；然后确定了最高位是 3，进行下一位最高位和非最高位的判断。

时间复杂度: O(N); 辅助空间复杂度: O(N)

class Solution {
    // 求重复数字的个数=总数字个数-非重复数字个数
    public int numDupDigitsAtMostN(int N) {
        return N - dp(N);
    }
    // 求 n 的非重复数字个数
    public int dp(int n) {
        List<Integer> digits = new ArrayList<>();
        // 将 n 的每位数拆解，添加进列表
        while (n > 0) {
            digits.add(n % 10);
            n /= 10;
        }
        // k 是 n 的位数
        int k = digits.size();

        int[] used = new int[10];
        int total = 0;
        // 最高位是 0 时的不重复个数
        for (int i = 1; i < k; i++) {
            // 9*A(9,i-1)
            total += 9 * A(9, i - 1);
        }

        for (int i = k - 1; i >= 0; i--) {
            int num = digits.get(i);

            for (int j = i == k - 1 ? 1 : 0; j < num; j++) {
                if (used[j] != 0) {
                    continue;
                }
                total += A(10 - (k - i), i);
            }

            if (++used[num] > 1) {
                break;
            }

            if (i == 0) {
                total += 1;
            }
        }
        return total;
    }

    public int fact(int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        return n * fact(n - 1);
    }

    public int A(int m, int n) {
        return fact(m) / fact(m - n);
    }
}