木又连续日更第4天(4/100)
木又的第168篇leetcode解题报告
动态规划
类型第13篇解题报告
leetcode第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) 区间内的所有数字。
【思路】
这道题主要用到排列组合知识。
首先考虑特殊情况,n>10,肯定会存在重复数字,所以返回0。
使用dp[i]存储i位数符合条件的个数(不包含最高位为0的数),最后返回sum(dp)。
n==0时,dp[i]=1
n==1时,dp[i]=9*dp[0]
n==2时,dp[i]=9*dp[1],相当于首位数有9种可能(1->9),第二位数也存在9种可能(0->9除了首位数)
n==3时,dp[i]=8*dp[i],首位数有9种可能(1->9),第二位数存在9种可能(0->9除了首位数),第三位数存在8种可能(0->9除了首位数和第二位数)
同理得到n>1时,dp[i] = (10-i+1)*dp[i-1],相当于前面几位都排序好,接下来一位只存在(10-i+1)种可能。
【代码】
python版本
class Solution(object):
def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
if n > 10:
return 0
dp = [1] * (n+1)
for i in range(1, n+1):
if i < 3:
dp[i] = dp[i-1] * 9
else:
dp[i] = dp[i-1] * (10-i+1)
return sum(dp)
C++版本
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n > 10)
return 0;
vector<int> dp(n+1, 1);
for(int i=1; i<n+1; i++){
if(i < 3)
dp[i] = 9 * dp[i-1];
else
dp[i] = (10-i+1) * dp[i-1];
}
// 求和
int sum = 0;
for(auto tmp: dp)
sum += tmp;
return sum;
}
};