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 &lt; 100, excluding <code>[11,22,33,44,55,66,77,88,99]</code>)

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的平方，範圍為[1,100)，然後找出這個範圍内合法值有幾個。9*9(第一位不能為0，是以為9，第二位可以為除了第一位以外的9中情況)。

n次方

範圍

合法個數

[0,1)

1

[1,10)

9

2

[10,100)

9*9

3

[100,1000)

9*9*8

...

i（i&lt;9）

[10的i-1次方，10的i次方)

9*9*8*7*...*(9 - n + 2)

[100000000,1000000000)

9*9*8*7*6*5*4*3*2

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

代碼如下：

4

5

6

7

8

10

11

12

13

14

15

16

17

18

19

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>int</code> <code>countNumbersWithUniqueDigits(</code><code>int</code> <code>n) {</code>

<code>        </code><code>int</code> <code>result,tmp;</code>

<code>        </code><code>if</code><code>(0 == n)</code>

<code>            </code><code>return</code> <code>1;</code>

<code>        </code><code>if</code><code>(1 == n)</code>

<code>            </code><code>return</code> <code>10;</code>

<code>        </code><code>result = 10;</code>

<code>        </code><code>tmp = 9;</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 2; i&lt;=min(n,9); ++i)</code>

<code>        </code><code>{</code>

<code>            </code><code>result += tmp * (11 - i);</code>

<code>            </code><code>tmp *= (11 - i);</code>

<code>        </code><code>}</code>

<code>        </code> 

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>}</code>

<code>};</code>

<code></code>

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1845316