leetcode -- Count Numbers with Unique Digits
题目描述:
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])
给定数位n,返回n位数字集合中,数位各自不重复的数字。
分析:
使用a[n]数组保存n位数字时多少数字不重复。
a[1] = 10
a[2] = 9*9
a[3] = 9*9*8
a[4] = 9*9*8*7
....
a[k] = 9*...*[11-k]
此题为全排列问题,即对于给定数位X,a[x]为9*B[N].
其中B[N] = [M*(M-1)*(M-2)....],而M的值总为9。对于X,数列B[N]的个数为X-1
实现:
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])
给定数位n,返回n位数字集合中,数位各自不重复的数字。
分析:
使用a[n]数组保存n位数字时多少数字不重复。
a[1] = 10
a[2] = 9*9
a[3] = 9*9*8
a[4] = 9*9*8*7
....
a[k] = 9*...*[11-k]
此题为全排列问题,即对于给定数位X,a[x]为9*B[N].
其中B[N] = [M*(M-1)*(M-2)....],而M的值总为9。对于X,数列B[N]的个数为X-1
实现:
public int CountNumbersWithUniqueDigits(int n)
{
if(n == 0){
return 1;
}
if(n == 1){
return 10;
}
if(n == 2){
return 91;
}
var result = new int[n];
result[0] = 10;
result[1] = 81;// 9*9
for (var i = 2;i < n; i++){
var count = i;
var x = 9;
for (var j = 9; count > 0; count--){
x *=j ;
j--;
}
result[i] = x;
}
return result.Sum();
}