C语言重构【357】计算各个位数不同的数字个数

素颜马尾好姑娘i 2022-11-06 05:50 200阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
    
    示例:
    
    输入: 2
    输出: 91 
    解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

#### 方案： ####

*  这道题可以看作dp+数学，也就是排列组合的思想。对于n位数，0开头交给下一级（n-1位），剩下直接排列组合算就行了，且n不可能>10。

class Solution
    { 
    public:
        int countNumbersWithUniqueDigits(int n)
        { 
            if (n == 0)
                return 1;
            else if (n == 1)
                return 10;
            else if (n == 2)
                return 91;
            else if (n > 10)
                return countNumbersWithUniqueDigits(10);
            else
            { 
                return countNumbersWithUniqueDigits(n - 1) + 9 * A(9, n - 1);
            }
        }
        int A(int m, int n)
        { 
            //排列组合计算
            if (n == 1)
                return m;
            else
                return m * A(m - 1, n - 1);
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关统计不同数字的个数(升级版)

统计不同数字的个数(升级版) 此处用的是C++。使用如下O(n2)级别的算法（普通版）此处先是求出相同的个数，再用总的去减。 include<ios

我就是我/ 2023年10月06日 17:06/ 0 赞/ 45 阅读

相关 C语言重构【389】找不同

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

今天药忘吃喽~/ 2022年12月29日 01:46/ 0 赞/ 169 阅读

相关 C语言重构【738】单调递增的数字

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

刺骨的言语ヽ痛彻心扉/ 2022年12月28日 07:14/ 0 赞/ 193 阅读

相关 C语言重构【115】不同的子序列

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

淩亂°似流年/ 2022年12月21日 10:50/ 0 赞/ 138 阅读

相关 C语言重构【268】丢失的数字

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

墨蓝/ 2022年12月17日 04:27/ 0 赞/ 148 阅读

相关 day1: 357. 计算各个位数不同的数字个数

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。示例: 输入: 2 输出: 91 解

迈不过友情╰/ 2022年12月04日 02:19/ 0 赞/ 141 阅读

相关 C语言重构【357】计算各个位数不同的数字个数

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

素颜马尾好姑娘i/ 2022年11月06日 05:50/ 0 赞/ 201 阅读

相关 leetcode 357. Count Numbers with Unique Digits | 357. 计算各个位数不同的数字个数（Java）

题目 [https://leetcode.com/problems/count-numbers-with-unique-digits/][https_leetcode.c

心已赠人/ 2022年08月30日 04:03/ 0 赞/ 106 阅读

相关 357. Count Numbers with Unique Digits （计算各位数字不都不相同的整数个数）

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 1

ゝ一纸荒年。/ 2022年07月14日 00:39/ 0 赞/ 53 阅读

相关 java技术支持计算各个位数之和

/ 程序头部注释开始程序的版权和版本声明部分 Copyright (c) 2011, 烟台大学计算机学院学生

阳光穿透心脏的1/2处/ 2022年05月28日 10:55/ 0 赞/ 186 阅读