[LeetCode] Count Numbers with Unique Digits 计算各位不相同的数字个数

简介:

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

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Hint:

  1. A direct way is to use the backtracking approach.
  2. Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
  3. This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
  4. Let f(k) = count of numbers with unique digits with length equals k.
  5. f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2) [The first factor is 9 because a number cannot start with 0].

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

这道题让我们找一个范围内的各位上不相同的数字,比如123就是各位不相同的数字,而11,121,222就不是这样的数字。那么我们根据提示中的最后一条可以知道,一位数的满足要求的数字是10个(0到9),二位数的满足题意的是81个,[10 - 99]这90个数字中去掉[11,22,33,44,55,66,77,88,99]这9个数字,还剩81个。通项公式为f(k) = 9 * 9 * 8 * ... (9 - k + 2),那么我们就可以根据n的大小,把[1, n]区间位数通过通项公式算出来累加起来即可,参见代码如下:

解法一:

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            res += count(i);
        }
        return res;
    }
    int count(int k) {
        if (k < 1) return 0;
        if (k == 1) return 10;
        int res = 1;
        for (int i = 9; i >= (11 - k); --i) {
            res *= i;
        }
        return res * 9;
    }
};

下面这种方法是上面方法的精简版,思路完全一样:

解法二:

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int res = 10, cnt = 9;
        for (int i = 2; i <= n; ++i) {
            cnt *= (11 - i);
            res += cnt;
        }
        return res;
    }
};

最后我们来看题目提示中所说的回溯的方法,我们需要一个变量used,其二进制第i位为1表示数字i出现过,刚开始我们遍历1到9,对于每个遍历到的数字,现在used中标记已经出现过,然后在调用递归函数。在递归函数中,如果这个数字小于最大值,则结果res自增1,否则返回res。然后遍历0到9,如果当前数字没有在used中出现过,此时在used中标记,然后给当前数字乘以10加上i,再继续调用递归函数,这样我们可以遍历到所有的情况,参见代码如下:

解法三:

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        int res = 1, max = pow(10, n), used = 0;
        for (int i = 1; i < 10; ++i) {
            used |= (1 << i);
            res += search(i, max, used);
            used &= ~(1 << i);
        }
        return res;
    }
    int search(int pre, int max, int used) {
        int res = 0;
        if (pre < max) ++res;
        else return res;
        for (int i = 0; i < 10; ++i) {
            if (!(used & (1 << i))) {
                used |= (1 << i);
                int cur = 10 * pre + i;
                res += search(cur, max, used);
                used &= ~(1 << i);
            }
        }
        return res;
    }
};

本文转自博客园Grandyang的博客,原文链接:计算各位不相同的数字个数[LeetCode] Count Numbers with Unique Digits ,如需转载请自行联系原博主。

相关文章
|
10月前
|
存储 C++ Python
LeetCode刷题---Add Two Numbers(一)
LeetCode刷题---Add Two Numbers(一)
|
存储 算法 安全
LeetCode - #2 Add Two Numbers
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #2 Add Two Numbers
LeetCode 357. Count Numbers with Unique Digits
给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。
73 0
LeetCode 357. Count Numbers with Unique Digits
|
存储 Python
LeetCode 315. Count of Smaller Numbers After Self
给定一个整数数组 nums,按要求返回一个新数组 counts。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
81 0
LeetCode 315. Count of Smaller Numbers After Self
LeetCode contest 200 5475. 统计好三元组 Count Good Triplets
LeetCode contest 200 5475. 统计好三元组 Count Good Triplets
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题