LeetCode_排列组合_中等_357.统计各位数字都不同的数字个数

不念不忘少年蓝@ 2023-10-06 23:47 36阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n。

**示例 1：**  
输入：n = 2  
输出：91  
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

**示例 2：**  
输入：n = 0  
输出：1

**提示：**  
0 <= n <= 8

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/count-numbers-with-unique-digits

## 2.思路 ##

（1）排列组合  
求解本题可以用到一定的数学知识：  
① 当 n = 0 时，由于 0 <= x < 10n，故 x = 0，即答案为 1；  
② 当 n = 1 时，x 可取 0 ~ 9 之间的所有整数，故答案为 10；  
③ 当 n ≥ 2 时，x 可分为 **1 位数**和 **n 位数**这两种，此时的情况比上面复杂一点：  
1）如果 x 是一位数，那么显然各位数字都不同的数字的个数为 10；  
2）如果 x 是 n 位数，此时需要运用到**排列组合**方面的知识，由于第一位不能为 0，所以第一位数只有 9 种选择，即 C(9, 1) = 9，其余的 n - 1 位则从剩余的 9 个数字中选 n - 1 个排列，即 A(9, n - 1)，所以一共有 C(9, 1) \* A(9, n - 1) 种答案；  
3）上述 2 种情况相加，即为 10 + C(9, 1) \* A(9, n - 1)；

## 3.代码实现（Java） ##

//思路1————排列组合
    class Solution {
        
        public int countNumbersWithUniqueDigits(int n) {
        
            if (n == 0) {
        
                return 1;
            }
            if (n == 1) {
        
                return 10;
            }
            // 2 ≤ n ≤ 8
            int res = 10;
            //当 n 大于等于 2 时，x 的第一位只有 9 种选择（第一位不能为 0），即 C(9, 1) = 9
            int cur_n_res = 9;
            for (int i = 0; i < n - 1; i++) {
        
                /* 
                    C(9, 1) * A(9, n - 1)
                    第一位有 9 种选择，即 1~9
                    其余的 n - 1 位从剩余的 9 个数字中选 n - 1 个排列，即 A(9, n - 1)
                */
                cur_n_res *= 9 - i;
                //累加 n 的不同取值的情况
                res += cur_n_res;
            }
            return res;
        }
    }