leetcode刷題，總結，記錄，備忘 357

leetcode357Count 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]

舉個例子，比如n=3，我們求的就是0 - 999之間有多少獨一無二的數字。我們可以拆分一下，求100到999之間有多少獨一無二的數字，然後用0 - 99的的結果與其相加即可。同理求0 - 99 ，先求 10 - 99 再用0 - 9 的結果進行相加，由于我們已經知道0 - 9 的結果是10，是以隻要求 10 - 99即可。先看第一位數字，可取值的範圍是1 - 9，一共有9種可能，第二位數字可取值範圍是0 - 9，理論上可以取10個數，但是考慮與第一位上的數字重複的情況，隻能取9個，是以 10 - 99 之間獨一無二數字個數為9 X 9 = 81個。現在再回頭看下100 - 999之間，在10 - 99 的基礎上，直接看第三位數字，取值範圍0 - 9 ，由于前兩位數字可能出現重複的情況，是以隻能取8個數字，是以100 - 999 之間的獨一無二數字應該隻有 81 X 8 = 648個，再加上之前的0 - 99 之間的個數，0 - 999 之間的獨一無二數字個數為648 + 81 + 10 = 739個。依次類推，以3為初始值，n多加一位，該位上的可選擇的數字個數就-1，代碼如下。

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0)
        {
            return 1;
        }
        if (n == 1)
        {
            return 10;
        }
        
        vector<int> dp(n + 1, 0);
        
        dp[2] = 91;
        
        for (int i = 3; i < n + 1; ++i)
        {
            int sum = 81;
            for (int j = 3; j <= i; ++j)
            {
                sum *= (11 - j);
            }
            
            dp[i] = sum + dp[i - 1];
        }
        
        return dp[n];
    }
};