打卡群刷题总结0929——计算各个位数不同的数字个数

发布于

题目：357. 计算各个位数不同的数字个数

链接：https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

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

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

解题：

1、dp问题。dp[i]存储真实的i位数的满足条件的数字个数，比如dp[3]只算了100->999中满足条件的个数，不算0->99。

转换为排列问题，排在第一位有9种可能（1->9），排在第二位有9种可能，排在第三位有8种可能……

那么，当i>1时，dp[i] = dp[i - 1] * (11 - i)

当i为0和1时，dp[i]分别为1和9。

代码：

代码语言：javascript
复制
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        dp = [1, 9]
        for i in range(2, n + 1):
            dp.append(dp[-1] * (11 - i))
        return sum(dp[:(n + 1)])

PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。

PPS：还是得日更呀，总结一下总是好的。

#dp#ps