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

leetcode 357. 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])

这道题主要是考察所有的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;
    }
};