题目

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

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

示例 1：

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

示例 2：

输入：n = 0
输出：1

提示：

  • 0 <= n <= 8

解题

题目分析

我们逐一考虑各种情况, 设函数d(t)d(t)的值为n=tn = t时的结果, 设函数f(t)f(t)为仅含有t位数字的各位数字都不同的数字x的个数

  • 当t = 0 时候, 0≤x<10\leq x < 1, 此时x只能选择0, 即有1种选择

    • 即d(0)=1d(0) = 1

  • 当t = 1 时候, 0≤x<100\leq x < 10, 此时x只能选择0~9, 即有10种选择

    • 即d(1)=10d(1)=10

  • 当t = 2 时候, 0≤x<1000 \leq x < 100, 此时有如下情况

    • 0≤x<100\leq x < 10: 该情况答案为d(1)d(1)

    • 10≤x<10010\leq x < 100: 该情况需要单独计算

      • 我们设最高位到最低位分别是第1位, 第2位,…

      • 对于第一位可以选择[1,9][1,9], 注意首位不能选择0, 有9种情况

      • 对于第二位可以选择[0,9][0, 9], 需要排除第一位已选的, 故有9种情况

      • 即f(2)=9∗9f(2)=9*9

    • 则d(2)=d(1)+f(2)d(2)=d(1)+f(2)

  • 我们可以推广到一般情况, 当t = n时候, 0≤x<10n0\leq x < 10^n

    • 0≤x<10n−10\leq x < 10^{n-1}: 该情况答案为d(n−1)d(n-1)
    • 10n−1≤x<10n10^{n-1} \leq x < 10^n: 该情况答案为f(n)=9∗A9d−1f(n) = 9 * A^{d-1}_9
    • 则d(n)=d(n−1)+f(n)d(n)=d(n-1)+f(n)

我们发现计算d(n)d(n)需要依赖d(n−1)d(n-1), 显然这是一个经典的动态规划与数学的排列组合结合的问题.

函数f(t)分析

函数f(t)f(t)表示仅含有t位数的各位数字都不同的数字个数.

  • 我们设最高位到最低位分别是第1位, 第2位,…

  • 对于第一位可以选择[1,9], 注意首位不能选择0, 有9种情况

  • 对于第二位可以选择[0, 9], 需要排除第一位已选的, 故有9种情况

  • 对于第三位可以选择[0, 9], 需要排除第一位,第二位已选的, 故有8种情况

  • 以此类推, 第四位有7种情况

  • 第t位有(9−t+2)(9-t+2)种情况

根据乘法原理, 需要对所有位的取值做乘法运算, 即

f(t)=9∗9∗8∗...∗(9−t+2)f(t) = 9*9*8*...*(9-t+2)

函数f(t)f(t)代码编写如下

1
2
3
4
5
6
7
int f(int t) {
        int ret = 9;
        for (int i = 2; i <= t; i++) {
            ret = ret * (9 - i + 2);
        }
        return ret;
}

函数d(t)分析

  • d(0)=1d(0) = 1

  • d(2)=10d(2) = 10

  • d(3)=d(2)+f(3)d(3) = d(2) + f(3)

  • …

  • d(t)=d(t−1)+f(t)d(t) = d(t-1) + f(t)

从上述分析可看出, 这是一个递归问题, 下一个解需要依赖上一个解, 为了解决重复计算的问题, 我们需要使用一个表来缓存之前的计算结果以减少重叠子问题的重复计算, 这就是动态规划中的记忆化搜索.

1
2
3
4
5
6
7
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 10;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + f(i);
}
// 此时dp[t]即为d(t)的

完整代码

常规代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
   public:
    // 只有d位数的情况
    int f(int t) {
        int ret = 9;
        for (int i = 2; i <= t; i++) {
            ret = ret * (9 - i + 2);
        }
        return ret;
    }

    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 2;
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 10;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + f(i);
        }
        return dp[n];
    }
};

打表

考虑到n的取值最多只有10种情况, 故我们可以将dp表直接将结果打表

1
2
3
4
5
6
7
8
class Solution1 {
   public:
    int countNumbersWithUniqueDigits(int n) {
        vector<int> dp{1,     10,     91,     739,     5275,
                       32491, 168571, 712891, 2345851, 5611771};
        return dp[n];
    }
};