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:

A direct way is to use the backtracking approach.

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.

This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.

Let f(k) = count of numbers with unique digits with length equals k.

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の平方、範囲は[1100]であり、その後、この範囲内の合法値がいくつかあることを見出した.9*9(1位は0ではないので、9であり、2位は1位以外の9中の場合であってもよい).
n次方
範囲
合法的な個数.
0
[0,1)
1
1
[1,10)
9
2
[10,100)
9*9
3
[100,1000)
9*9*8
...
...
...
i(i<9)
[10のi-1次方,10のi次方)
9*9*8*7*...*(9 - n + 2)
9
[100000000,1000000000)
9*9*8*7*6*5*4*3*2
以上の解析により,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