leetcode [357] 计算各个位数不同的数字个数

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

示例:

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

来自题解：

排列组合：n位有效数字 = 每一位都从 0~9 中选择，且不能以 0 开头

• 1位数字：0~9 10
• 2位数字：C10-2，且第一位不能是0 9 * 9
• 3位数字：C10-3，且第一位不能是0 9 * 9 * 8
• 4位数字：C10-4，且第一位不能是0 9 * 9 * 8 * 7
• … …
• 最后，总数 = 所有 小于 n 的位数个数相加

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0: return 1
        first = 10
        second = 9 * 9
        size = min(n, 10)
        for i in range(2, size + 1):
            first += second
            second *= 10 - i
        
        return first