LeetCode 357. 统计各位数字都不同的数字个数

357. 统计各位数字都不同的数字个数

题目：给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10^n 。
链接 https://leetcode.cn/problems/count-numbers-with-unique-digits/

个人思路

1. 只有9个测试用例，其实可以打表。此外，这道题其实就是一个排列组合。如一个三位数其各位数字都不同的数字个数为：998（0-9共有10位数，但第一位不能为0），然后要求 0 <= x < 10^3这个范围的话只需加上两位数、一位数的个数即可

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        ans = [1,10,91,91+9*9*8,91+9*9*8+9*9*8*7,91+9*9*8+9*9*8*7+9*9*8*7*6,
        91+9*9*8+9*9*8*7+9*9*8*7*6+9*9*8*7*6*5,
        91+9*9*8+9*9*8*7+9*9*8*7*6+9*9*8*7*6*5+9*9*8*7*6*5*4,
        91+9*9*8+9*9*8*7+9*9*8*7*6+9*9*8*7*6*5+9*9*8*7*6*5*4+9*9*8*7*6*5*4*3]
        return ans[n]
1
2
3
4
5
6
7

其他思路

1. 官方：也是排列组合，只是写成了迭代形式

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        if n == 1:
            return 10
        res, cur = 10, 9
        for i in range(n - 1):
            cur *= 9 - i
            res += cur
        return res
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：O(n)。仅使用一个循环。
空间复杂度：O(1)。仅使用常数空间。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/count-numbers-with-unique-digits/solution/tong-ji-ge-wei-shu-zi-du-bu-tong-de-shu-iqbfn/

2. 评论区大佬：动态规划
   
   
   根据大佬的提示写了个python版本的动态规划

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        dp = [1,10]
        i = 2
        while i <= n:
            dp.append(dp[-1] + (dp[-1]-dp[-2]) * (10-i+1))
            i += 1
        return dp[-1]
1
2
3
4
5
6
7
8
9
10