Problem
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])
题意
给出一个非负整数n，计算所有满足以下条件的x：
- 0 ≤ x < 10^n
- x中没有重复数字（如121就不满足,因为有两个1）
分析
本题可以有两种做法，一种是利用纯数学方法，计算排列数即可；另一种是利用回溯的思想，有点类似于LeetCode# 526: Beautiful Arrangement，将不同的数字放置在不同的位置，求得满足条件的放置方法数即可。
数学方法
题意可转化为，在1个(n = 0, 1)或n个(n ≥ 2)位置上放置0-9这十个数字，是高中时候就学过的排列问题。
- 对于n=0的情况，满足条件的数字只有
0，只有1个； - 对于n=1的情况，满足条件的数字有
0, 1, ..., 9，有10个； - 对于n=2的情况，对于一位数，满足条件的有10个；对于两位数，问题变成了，从0-9这十个数字中挑出两个分别放置在十位和个位，是A(2, 10)；但是要注意0不能放在十位，所以要去掉A(1, 9)个数字，最后的结果：
result[2] = A(2, 10) - A(1, 9) + result[1] - 对于n > 2的情况不再赘述。
回溯方法
//TODO
Code
数学方法
//Runtime: 0ms（精度不够）
class Solution {
private:
vector<int> fac; //fac[i] = i!
vector<int> result; //result[i] = result of i
void _calFac(){
fac.resize(11);
fac[0] = 1;
for (int i = 1; i <= 10; i++)
fac[i] = i * fac[i - 1];
return;
}
void _calRst(int n){
result.resize(n + 1);
result[0] = 1;
for (int i = 1; i <= n; i++)
result[i] = fac[10] / fac[10 - i] - fac[9] / fac[10 - i] + result[i - 1];
return;
}
public:
int countNumbersWithUniqueDigits(int n) {
if (n > 10) return 0;
_calFac();
_calRst(n);
return result[n];
}
};
Backtracking
//TODO
