357. Count Numbers with Unique Digits （计算各位数字不都不相同的整数个数）

ゝ一纸荒年。 2022-07-14 00:39 40阅读 0赞

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

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]`)

Hint:

1.  A direct way is to use the backtracking approach.
2.  Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
3.  This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
4.  Let f(k) = count of numbers with unique digits with length equals k.
5.  f(1) = 10, ..., f(k) = 9 \* 9 \* 8 \* ... (9 - k + 2) \[The first factor is 9 because a number cannot start with 0\].

**题目大意：给定整数n，计算\[0，10^n)范围内，各位数字都不相同的整数的个数。例如，123是各位数字都不相同的整数，而11，121就不是。**

**解题思路：**

当n=0时，结果为1，即 \{0\}；

当n=1时，即查找满足条件的一位数，结果为10，即 \{0,1,2,3,4,5,6,7,8,9\}；

当n=2时，即查找满足条件的一位数和两位数，一位数的个数为10，满足条件的两位数即从1到9的某一个数字后面接一个不相同的数字，个数为9\*9，那么结果为10+9\*9；

当n=3时，即查找满足条件的一位数、两位数和三位数，一位数和两位数的个数为10+9\*9，满足条件的三位数即上面求得的81个满足条件的两位数后面接一个不相同的数字，个数为9\*9\*8，那么结果为10+9\*9+9\*9\*8；

……

当n>10以后，便找不到一个各位数字都不相同的数字了。

代码如下：（0ms，beats 12.25%）

public class Solution {
        public int countNumbersWithUniqueDigits(int n) {
            if (n == 0)
    			return 1;
    		int sum = 10;
    		int add = 9;
    		int i;
    		for (i = 1; i < n; i++) {
    			sum += add * (10 - i);
    			add *= (10 - i);
    		}
    		return sum;
        }
    }