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])
题目：意思很明确，找出0 到10的n次方内没有重复数字构成的元素个数，11，101这类都不合格
思路：这道题目十分具有代表性，暴力解法当然是可以的，但是根据题目标签的提示，可以用backtrack和dynamic programming,这个两个算法很值得深入学习一番，看到许多书籍提到过
1，首先是backtrack，学名回溯算法，基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
下面解法的思路是，对给定的数的范围0 ≤ x < 10^n,我们先区间内求1打头的，接着求2打头的.....到9打头的符合规则的数的数量，1打头里面
我们分别求11，12，13....19打头的，如此递归，设置一个boolean数组管理哪个数字为应该规避的，应该规避的数字设为true
public int countNumbersWithUniqueDigits(int n) {
if (n > 10) {
return countNumbersWithUniqueDigits(10);
}
int count = 1; // x == 0
long max = (long) Math.pow(10, n);
boolean[] used = new boolean[10];
for (int i = 1; i < 10; i++) {
used[i] = true;
count += search(i, max, used);
used[i] = false;
}
return count;
}
private static int search(long prev, long max, boolean[] used) {//查询prev打头的，范围为prev-max的个数
int count = 0;//初始
if (prev < max) {//递归出口
count += 1;
} else {
return count;
}
/**
* 这段逻辑的意思是，假设prev = 1,i=2，这时used数组中used[1]为true,used[2]为true，curr =12，再接着去查询12打头，到max为止的个数
*/
for (int i = 0; i < 10; i++) {
if (!used[i]) {
used[i] = true;
long cur = 10 * prev + i;
count += search(cur, max, used);
used[i] = false;
}
}
return count;
}
2，这种思路相对而言简单好理解一点，原理是把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法
本题中我们可以发现，这样一个规律，我们用f(n)标示n位数的符合规则元素的个数，如f(2)标识10-99区间的数目
会发现f(n)符合这样的一个规律，f(n) = 9*9*8...(11-n),于是有如下代码
public int countNumbersWithUniqueDigits(int n) {
if(n==0) return 1;
int count = 10;
int digit = 9;
for(int i = 2;i<=n;i++){
digit *= (11-i);
count+=digit;
}
return count;
}