Count-Numbers-with-Unique-Digits

LeetCode
,

第70天。

今天的题目是Count Numbers with Unique Digits:

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

先解释一下题目，所谓的unique digits就是这个数字中不包含相同的数字。

理解到这个的话，我们就从n=2开始考虑。

其实只需要一点排列组合的知识就可以发现如果它是个2位数,那么就会有9*9,第一个之所以是9，是因为，0不能出现在最高位，后面的那个是就是因为他不能和前面那个数字相同。如果是个3位数，那就是9*9*8,那个8是因为不能和前面两位出现的数字。

然后其实我们这里只得出来n位数的情况，但是它要的范围是0 < x < 10^n。这样的话，如果n=3,我们就需要求出1位数的个数、2位数的个数、3位数的个数，然后他们的和就是答案了。

我们可以写成动态规划的形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countNumbersWithUniqueDigits(int n) {
    int *dp = new int[n+1];
    dp[0] = 1;
    int k = 9;
    int a = 9;
    for(int i = 1;i <= n && a > 0;i++) {
        dp[i] = k + dp[i-1];
        k *= a;
        a--;
    }
    int ret = dp[n];
    delete dp;
    return ret;
}