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

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

示例:
给定 n = 2，返回 91。（答案应该是除[11,22,33,44,55,66,77,88,99]外，0 ≤ x < 100 间的所有数字）

致谢:
特别感谢 @memoryless 添加这个题目并创建所有测试用例。

思路

1
2
3
4
5
6
7
8
//         n 0 :0
//         n 1:0~9
//         n 2:0~9 + 10~99
//         n 3:0~9 + 10~99 + 100~999
//         n 4:0~9 + 10~99 + 100~999 + 1000~9999


每一位从0～9有10种选择，注意第一位不能为0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int countNumbersWithUniqueDigits(int n) { 
        if(n==0){
            return 1;
        }
        if(n==1){
            return 10;
        }
        int []arr = new int[n+1];
        arr[0]=1;
        arr[1]=10;
        for(int i =2;i<n+1;i++){
            int temp=1;
            for(int j =0;j<i;j++){
                if(j==0){
                    temp*=9;
                }else{
                    temp*=(10-j);
                }
               
            }
            arr[i]= arr[i-1]+temp;
            System.out.println(arr[i]);
        }
        return arr[n];
    }
}