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])
題意
給出一個(gè)非負(fù)整數(shù)n秦踪，計(jì)算所有滿足以下條件的x：
- 0 ≤ x < 10^n
- x中沒(méi)有重復(fù)數(shù)字（如121就不滿足,因?yàn)橛袃蓚€(gè)1）
分析
本題可以有兩種做法胳螟，一種是利用純數(shù)學(xué)方法驼壶，計(jì)算排列數(shù)即可墓律；另一種是利用回溯的思想，有點(diǎn)類似于LeetCode# 526: Beautiful Arrangement瓣铣，將不同的數(shù)字放置在不同的位置，求得滿足條件的放置方法數(shù)即可。
數(shù)學(xué)方法
題意可轉(zhuǎn)化為笨使，在1個(gè)(n = 0, 1)或n個(gè)(n ≥ 2)位置上放置0-9這十個(gè)數(shù)字，是高中時(shí)候就學(xué)過(guò)的排列問(wèn)題僚害。
- 對(duì)于n=0的情況硫椰，滿足條件的數(shù)字只有
0，只有1個(gè)萨蚕； - 對(duì)于n=1的情況靶草，滿足條件的數(shù)字有
0, 1, ..., 9，有10個(gè)岳遥； - 對(duì)于n=2的情況奕翔，對(duì)于一位數(shù)，滿足條件的有10個(gè)浩蓉；對(duì)于兩位數(shù)派继，問(wèn)題變成了，從0-9這十個(gè)數(shù)字中挑出兩個(gè)分別放置在十位和個(gè)位捻艳，是A(2, 10)驾窟；但是要注意0不能放在十位，所以要去掉A(1, 9)個(gè)數(shù)字认轨，最后的結(jié)果：
result[2] = A(2, 10) - A(1, 9) + result[1] - 對(duì)于n > 2的情況不再贅述绅络。
回溯方法
//TODO
Code
數(shù)學(xué)方法
//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
