Leetcode 357.计算各个位数不同的数字个数

计算各个位数不同的数字个数

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

示例:

输入: 2

输出: 91

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

解题分析：

题目要就就是找出 0≤ x < 10n中各位数字都不相同的数的个数。要接触这道题只需要理解：

1.设f(n)表示n为数字中各位都不相同的个数，则有countNumbersWithUniqueDigits(n)=f(1)+f(2)+……+f(n)=f(n)+countNumbersWithUniqueDigits(n-1);

2.对于f(n),由于首位不能为0，之后n--1位可以选不重复的任意数字，所以这是一个高中常见的概率题，可能性为9*9*8*……（所以可能出现的不可能超过10位);

理解了以上两点，这道题就很好得出。

 1 public class Solution {
 2     public static int countNumbersWithUniqueDigits(int n) {
 3         if(n<0)
 4             return 0;
 5         if(n==0){
 6             return 1;
 7         }
 8         if(n==1)
 9             return 10;
10         if(n==2)
11             return 91;
12         int sum=9;
13         int index=0;
14         while(index<n-1){
15             int m=9-index;
16             if(m<=0)
17                 break;
18             sum=sum*m;
19             index++;
20         }
21         int result = sum+countNumbersWithUniqueDigits(n-1);
22         return result;
23     }
24 }