【模拟, 动态规划, 数学】统计各位数字都不同的数字个数

题目

357. 统计各位数字都不同的数字个数

---

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10^n 。

示例 1：

输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。 

示例 2：

输入：n = 0
输出：1

提示：

• 0 <= n <= 8

解题

方法一：暴力 模拟

思路

遍历 [0, 10^n^) 中的每一个数字 num ，再遍历 num 中的每一位 digit ，使用 digitFrequencies 数组记录每一位(0~9)的出现频率，如果该位出现频率大于1 则代表有重复位数，舍去；最后在 num 遍历中给没有重复位数的(!hasRepeatDigit)记数。遍历完成后返回计数 ans 即可。

代码

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        // n=8 时会超时，直接返回答案吧...
        if (n == 8) {
            return 2345851;
        }
        int range = (int)Math.pow(10, n); // [0, range) 为 num 的范围
        int ans = 0; // 计数
    for (int i = 0; i < range; i++) { // 遍历范围中的每一个数字
        int num = i; // 范围中的每一个数字
        int[] digitFrequencies = new int[10]; // num 中每一位 digit 的出现频率
        boolean hasRepeatDigit = false; // num 是否有重复数位

        while (num > 0) { // 从后往前遍历 num 中每一位
            int digit = num % 10; // num 中每一位
            digitFrequencies[digit]++; // 记录频率
            if (digitFrequencies[digit] > 1) {
                // 出现频率 > 1 则 num 有重复数位
                hasRepeatDigit = true;
            }
            num /= 10; // 把 num 位数往前推
        }

        if (!hasRepeatDigit) {
            // num 没有重复数位则计数
            ans++;
        }
    }

    return ans;
}

}

方法二：动态规划

思路

n=0，数字有{0}1个。

n=1，数字有{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}10个。

n=2，数字有{n=1的所有答案}∪{长度为2的新增数字}，其中： 长度为 2 的新增数字可以在 n=1 的所有 9 个数字基础上进行拼接（0不能算），如： 从n=1的数字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中随便取出一个除0以外的数字（0不能作为起始数字） 例如取 2 ，通过在2的尾巴处拼接一位数字可以得到新的合法数字有： {20， 21，23，24，25，26，27，28，29} 可以看到，除了不能在尾巴处拼接一个2（两个连续的2非法），0-9 中一共有9个数字可以拿来拼接在尾巴处。新增答案为9个。同理，对于n=1数字列表{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}中的其他任意非0数也可以进行拼接操作，一共可以新增9*9个答案。 最终，n=2的合法数字，n=1时的答案 + 长度为2的数字个数（9*9个）= 10 + 81 = 91。

n=3，同理，只不过此时可以用拼接的数字减少为了8个，此时答案为 10 + (9 * 9) + [(9 * 9) * 8] = 739。

n=4时同理，只不过此时可以用拼接的数字减少为了7个，此时答案为 10 + (9 * 9) + [(9 * 9) * 8] + {[(9 * 9) * 8] * 7} = 5275。

通过归纳，假设 dp[i] 即 n = i 时的答案，则动态转移方程为：

dp[i] = dp[i-1] + (dp[i-1] - dp[i-2]) * (10 - (i - 1))

转移的初始条件为

• dp[0] = 1
• dp[1] = 10

代码

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 10;
    for(int i = 2; i <= n; i++) {
        //      上一次的答案  上一次较上上一次增加的答案    可以拼接的数字个数
        dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2]) * (10 - (i - 1));
    }

    return dp[n];
}

}