leetcode 357. Count Numbers with Unique Digits 统计独特编码数组的数量 + 一个很简单的排列组合问题

偏执的太偏执、 2022-06-07 02:45 141阅读 0赞

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\])

这道题主要是考察所有的digit的唯一性，最简单的就是遍历，但是肯定会超时，仔细想一下，这是一个排列组合问题。

这道题让我们找一个范围内的各位上不相同的数字，比如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\]区间位数通过通项公式算出来累加起来即可，参见代码如下：

代码如下：

import java.util.HashSet;
    import java.util.Set;
    
    /*
     * 仔细想一下这是一个简单的排列组合问题
     * */
    class Solution 
    {
         public int countNumbersWithUniqueDigits(int n)
         {
             if(n<=1)
                 return (int)Math.pow(10, n);
    
             int count=10,val=9;
             for(int i=2;i<=n;i++)
             {
                 val=val*(9+2-i);
                 count=count+val;
             }
             return count;
         }
    
        /*
         * 直接查询肯定是最直接的想法，但是肯定会超时
         * */
        public int countNumbersWithUniqueDigitsByLoop(int n)
        {
            if(n<=1)
                return (int)Math.pow(10, n);
    
            int count=0;
            for(long i=0;i<Math.pow(10, n);i++)
            {
                char[] array=(""+i).toCharArray();
                Set<Character> set=new HashSet<>();
                for(int j=0;j<array.length;j++)
                    set.add(array[j]);
                if(set.size()==(""+i).length())
                    count++;
            }
            return count;
        }
    }

下面是C++的做法

其实这是一个排列组合问题

代码如下:

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    
    class Solution 
    {
    public:
        int countNumbersWithUniqueDigits(int n)
        {
            if (n == 0)
                return 1;
            int count = 10 , tmp = 9;
            for (int i = 2; i <= n; i++)
            {
                tmp *= (11 - i);
                count += tmp;
            }
            return count;
        }
    };