力扣 统计各位数字都不同的数字个数 C++ 题解

力扣 统计各位数字都不同的数字个数 C++ 题解

文章目录

• 力扣 统计各位数字都不同的数字个数 C++ 题解
• 
  

  一、完整题目

• 
  

  二、具体思路

• 
  

  三、编写代码

• 
  

  四、测评结果

• 
  

  五、总结评价

---

一、完整题目

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

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

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

提示：
0 <= n <= 8

二、具体思路

• 首先考虑 n = 0 的情况，毫无疑问只有一个数 0 ，答案是 0 。
  

  
  

• 其次，考虑 n = 1 的情况，都是个位数不存在重复的问题，所以答案为 10 。
  

  
  

• 再次，考虑 n = 2 的情况，sum = 10(n = 1) + 9 * 9(n = 2) 。
  

  
  

• 最后，考虑 n = 3 的情况，sum = 10(n = 1) + 9 * 9(n = 2) + 9 * 9 * 8(n = 3)。
  

  
  

• 所以，答案已经很明了了：sum = 10 + 9 * (9 + 9 * 8 + 9 * 8 * 7 + …)

三、编写代码

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
       if (n == 0) return 1;
       else if (n == 1) return 10;
       else {
           int cnt = 10, j = 9;
           for (int i = 0; i < n - 1; ++i)
           {
               j = j * (9 - i);
               cnt = cnt + j;
           }
           return cnt;
       }
    }
};

---

四、测评结果

五、总结评价

题目非常简单，拿道题，不要盲目的去敲代码，而是先观察，寻找数学规律，是否有简单的做法，直接暴力的话，会超时的。

有问题欢迎各位大佬指出
力扣系列将持续更新，欢迎关注，一起学习