[leetcode] 357. Count Numbers with Unique Digits

Description

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

Example:

Input: 2
Output: 91 
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, 
             excluding 11,22,33,44,55,66,77,88,99      

分析

題目的意思是：找一個範圍内的各位上不相同的數字，比如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) {
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1]+9*factorial(i-1);
        }
        return dp[n];
    }
    int factorial(int n){
        int res=1;
        for(int i=0;i<n;i++){
            res=res*(9-i);
        }
        return res;
    }
};      

參考文獻