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次方內(nèi)，沒有重復(fù)數(shù)字的數(shù)的個數(shù)。例如10的3次方內(nèi)，102為合法值，101為非法值。

思路：

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

經(jīng)過上面分析，當(dāng)n大于等于10的時候，合法值不再增加，因?yàn)閚>=10時，數(shù)的位數(shù)超過了10位，所以肯定有重復(fù)的數(shù)字。

代碼如下：

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