Count Numbers with Unique Digits

发表于 | 分类于

Count Numbers with Unique Digits

题目描述：

给定一个表示位数的数字n,返回n位数中所有位数均不相同的数字的个数。

例子：

具体描述见LeetCode357

解题思路：

除了n在0和1的情况下特殊对待以外。我们找到每种位数下的数字的可能性进行相加即可得到最后的结果。其中在cal函数中我们定义了res和j初始值均为9，表示首位的可能为1~9，次位的可能在选取1~9之后加上0依旧有9种可能。而后根据排列组合的公式即可得到我们的结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        int pre = 10;
        int next = 0;
        for (int i = 1; i < n; i++){
            next = pre + cal(i);
            pre = next;
        }
        return next;
    }
    int cal(int count){
        int res = 9;
        int j = 9;
        while(count != 0){
            res = res * j;
            j = j - 1;
            count--;
        }
        return res;
    }
};