leetCode 357. Count Numbers with Unique Digits | Dynamic Programming | Medium

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

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

題目大意：

找出10的n次方內，沒有重復數字的數的個數。例如10的3次方內，102為合法值，101為非法值。

思路：

采用排列組合來求出10的i次方，比如10的平方，范圍為[1,100)，然后找出這個范圍內合法值有幾個。9*9(第一位不能為0，所以為9，第二位可以為除了第一位以外的9中情況)。

經過上面分析，當n大于等于10的時候，合法值不再增加，因為n>=10時，數的位數超過了10位，所以肯定有重復的數字。

代碼如下：

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

2016-09-01 18:45:28