### 题目

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

### 基本思路

  10-1    9      8      7      6     ...
|      |      |      |      |
| pos1 | pos2 | pos3 | pos4 | pos5 | ...


T(n) = T(n-1) + f(n)

#### 代码1

class Solution {

private static final int[] base = new int[]{9,9,8,7,6,5,4,3,2,1};

public int countNumbersWithUniqueDigits(int n) {
if (n < 0) { return 0; }
int count = 1;
for (int i = 0; i < n; i++) {
int product = 1;
for (int j = 0; j <= i; j++) {
product *= base[j];
}
count += product;
}
return count;
}
}


#### 代码

class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n < 0) { return 0; }
int availableNumber = 10, product = 1;
int count = 1; // special case: only 0 can start with 0
for (int i = 0; i < n; i++) {
product *= (i == 0)? (availableNumber - 1 ) : availableNumber; // avoid numbers start with 0
count += product;
availableNumber--;
}
return count;
}
}