题目描述

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

样例描述

示例:

输入: 2
输出: 91 
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

思路

排列组合 + 总结递推规律

1. 如果是5位数，方案数如下
   
2. n最大为10，否则没有意义，因为0~9刚好10种数位，如果n大于10一定会有重复
3. 找规律，例如如果n等于6，相当于在上面例子后面再乘5，同理n等于7，就是再乘4，所以递推的规律就是f[i] = f[i - 1] * (11 - i)
4. 注意边界情况n为0

代码

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        //超过10的一定会有重复数字
       n = Math.min(n, 10);
       if (n == 0) return 1;
       int f[] = new int[n + 1];
       //第一个位置有9种，开头不能为0
       f[1] = 9;
       for (int i = 2; i <= n; i ++ ) {
           //排列组合举例子可以找出递推规律
           f[i] = f[i - 1] * (11 - i);
       }
       //记得算上n为0的
       int res = 1;
       //累加n取0~9的所有个数就是答案
       for (int i = 1; i <= n; i ++ ) {
           res += f[i];
       }
       return res;
    }
}