LeetCode-357 统计各位数字都不同的数字个数

简介: LeetCode-357 统计各位数字都不同的数字个数

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/count-numbers-with-unique-digits

题目描述

给你一个整数 n ,统计并返回各位数字都不同的数字 x 的个数,其中 0 <= x < 10n

 

示例 1:

输入:n = 2

输出:91

解释:答案应为除去 11、22、33、44、55、66、77、88、99 外,在 0 ≤ x < 100 范围内的所有数字。

示例 2:

输入:n = 0

输出:1

 

提示:

0 <= n <= 8

解题思路

看了下n只有9个取值,皮一下直接暴力枚举0-8的结果。

其实是个排列组合问题,对于n = 0 来说,只有0这个数字,对于n = 1来说,存在0-9这10个数字,对于n > 1的情况来说,符合条件的结果就是n-1的情况再加上位数为n的情况,其中位数为n的情况可以使用排列组合来解,第一位不能为0所以有9个数字候选,第二位不能与第一位相同,所以有9个数字可选,第三位不能和第一第二位相同所以有8个数字可选以此类推,所以an = an-1 + 9 * 9 *  ……* (11 - n)。

代码展示

暴力枚举:

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        int iRet = 0;
        switch(n)
        {
            case 0:
                iRet = 1;
                break;
            case 1:
                iRet = 10;
                break;
            case 2:
                iRet = 91;
                break;
            case 3:
                iRet = 739;
                break;
            case 4:
                iRet = 5275;
                break;
            case 5:
                iRet = 32491;
                break;
            case 6:
                iRet = 168571;
                break;
            case 7:
                iRet = 712891;
                break;
            case 8:
                iRet = 2345851;
                break;
        }
        return iRet;
    }
};

排列组合:

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        int iRet = 10;
        if(n == 0) return 1;
        if(n == 1) return 10;
        for(int i = 2; i <= n; i++)
        {
            int iTemp = 1;
            for(int j = 9; j > 10 - i; j--)
                iTemp *= j;
            iRet = iRet + 9 * iTemp;
        }
        return iRet;
    }
};

运行结果

 

相关文章
|
7月前
|
算法 测试技术 C#
区间合并|LeetCode2963:统计好分割方案的数目
区间合并|LeetCode2963:统计好分割方案的数目
|
7月前
|
算法 安全 测试技术
[组合数学]LeetCode:2954:统计感冒序列的数目
[组合数学]LeetCode:2954:统计感冒序列的数目
|
7月前
|
算法 测试技术 C#
【离散差分】LeetCode2953:统计完全子字符串
【离散差分】LeetCode2953:统计完全子字符串
|
7月前
leetcode-1220:统计元音字母序列的数目
leetcode-1220:统计元音字母序列的数目
50 0
|
7月前
leetcode-1995. 统计特殊四元组
leetcode-1995. 统计特殊四元组
41 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
46 0
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
7月前
[leetcode~数位动态规划] 2719. 统计整数数目 hard
[leetcode~数位动态规划] 2719. 统计整数数目 hard
|
7月前
leetcode2376. 统计特殊整数
leetcode2376. 统计特殊整数
56 1