Cinte's Leetcode Record
0%

357. 计算各个位数不同的数字个数

Posted on Edited on In Disqus:
Symbols count in article: 533 Reading time ≈ 1 mins.

357. 计算各个位数不同的数字个数

数学方法

第一位如果取0，那结果就是n=n-1时候的结果

第一位如果取1~9，第二位可以取0，所以有9种取法，第三位有8种，依此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0)
            return 1;
        if(n > 10)
            return 0;
        int a = 10, pre = 9;
        for(int i = 2; i <= n; ++i)
            a += pre *= (11 - i);
        return a;
    }
};

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0)
            return 1;
        int a = 0, sum = 1, tmp = 0;
        for(int i = 2; i <= n; ++i)
        {
            a = a * 10 + (9 * sum - a) * (i - 1); // 每一种不重复的数字剩下有i-1位，这i-1种可能性
            sum *= 10;
            tmp += a;
        }
        return sum * 10 - tmp;
    }
};