【leetcode刷题】T168-计算各个位数不同的数字个数
【leetcode刷题】T168-计算各个位数不同的数字个数
木又AI帮
发布于 2019-09-23 18:07:43
发布于 2019-09-23 18:07:43
木又连续日更第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;
}
};
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-09-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读