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项福利资源
获取方式：进入群后点开群公告即可领取下载链接

注意：请大家添加时修改备注为 [学校/公司 + 姓名 + 方向]
例如 —— 哈工大+张三+对话系统。
号主，微商请自觉绕道。谢谢！

推荐阅读
“拍一拍” 能撤回了 ！！！
5款Chrome插件，第1款绝对良心！
为开发色情游戏，这家公司赴日寻找AV女优拍摄，期望暴力赚钱结果...
拼多多终于酿成惨剧
华为阿里下班时间曝光：所有的光鲜，都有加班的味道

关于程序员大白

程序员大白是一群哈工大，东北大学，西湖大学和上海交通大学的硕士博士运营维护的号，大家乐于分享高质量文章，喜欢总结知识，欢迎关注[程序员大白]，大家一起学习进步！