Leetcode题解 CountNumberswithUniqueDigits
点击上方“程序员大白”，选择“星标”公众号
重磅干货，第一时间送达
题意
题目：对唯一数字组成的数进行计数 给定一个非负整数n，对唯一数字组成的数x进行计数，其中0 <= x <= 10 ^ n. 举个例子： 给定 n = 2，应当返回 91.
题解
算法及复杂度（0 ms） 根据排列组合的知识，要想得到每个数字都不重复的数，对于一个n位数（1 <= n <= 10），第一个位置有9中可能，第二个位置有9中可能，第三个位置8中，... 由于本题，所求的是0 <= x <= 10 ^ n范围内所有的数，所以可以设dp[i]表示<= x <= 10 ^ i所有满足条件的x的个数， 那么dp[i + 1] = 9 * 9 * 8...(共i个) + dp[i]. 可以看到，本题存在递推的关系，但是并不存在重叠子问题的性质，可以直接使用递推的方法进行求解.
时间复杂度: O(n).
举个例子
// 输入数据 n = 3
// 初始化
dp[0] = 1
// i = 1时
dp[1] = 9 + dp[0] = 10
// i = 2时
dp[2] = 9 * 9 + dp[1] = 91
// i = 3时
dp[3] = 9 * 9 * 8 + dp[2] = 739
// 返回结果
return 739
CPP代码
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
vector<int> dp(11);
dp[0] = 1;
for(int i = 1; i <= 10; i ++) {
int temp = 9;
for(int j = 9; j > 10 - i; j--) {
temp *= j;
}
dp[i] = temp + dp[i - 1];
}
if(n > 10) return dp[10];
else return dp[n];
}
};
重磅！程序员大白交流群-学术微信交流群已成立
额外赠送福利资源！邱锡鹏深度学习与神经网络，pytorch官方中文教程，利用Python进行数据分析，机器学习学习笔记，pandas官方文档中文版，effective java（中文版）等20项福利资源
获取方式：进入群后点开群公告即可领取下载链接
注意：请大家添加时修改备注为 [学校/公司 + 姓名 + 方向]
例如 —— 哈工大+张三+对话系统。
号主，微商请自觉绕道。谢谢！
推荐阅读
关于程序员大白
程序员大白是一群哈工大，东北大学，西湖大学和上海交通大学的硕士博士运营维护的号，大家乐于分享高质量文章，喜欢总结知识，欢迎关注[程序员大白]，大家一起学习进步！
评论