13

これは面接の質問です。[1、N]の範囲の一意の数字（10進数）を持つすべての数値をカウントします。

明らかな解決策は、その桁が一意であるかどうか、範囲内の各数値をテストすることです。また、（順列として）一意の数字を使用してすべての数値を生成し、それらが範囲内にあるかどうかをテストすることもできます。

ここで、この問題に対するDP（動的計画法）ソリューションがあるかどうか疑問に思います。

4

6 に答える 6

15

考えている：

Number of unique digits numbers 1-5324
=   Number of unique digits numbers 1-9
  + Number of unique digits numbers 10-99
  + Number of unique digits numbers 100-999
  + Number of unique digits numbers 1000-5324

そう：

f(n) = Number of unique digits numbers with length n.
f(1) = 9 (1-9)
f(2) = 9*9 (1-9 * 0-9 (excluding first digit))
f(3) = 9*9*8 (1-9 * 0-9 (excluding first digit) * 0-9 (excluding first 2 digits))
f(4) = 9*9*8*7

N の桁数がマイナス 1 になるまで、上記のすべてを追加します。

あとはやるだけですNumber of unique digits numbers 1000-5324

と：

Number of unique digits numbers 1000-5324
=   Number of unique digits numbers 1000-4999
  + Number of unique digits numbers 5000-5299
  + Number of unique digits numbers 5300-5319
  + Number of unique digits numbers 5320-5324

そう：

N = 5324

If N[0] = 1, there are 9*8*7 possibilities for the other digits
If N[0] = 2, there are 9*8*7 possibilities for the other digits
If N[0] = 3, there are 9*8*7 possibilities for the other digits
If N[0] = 4, there are 9*8*7 possibilities for the other digits
If N[0] = 5
  If N[1] = 0, there are 8*7 possibilities for the other digits
  If N[1] = 1, there are 8*7 possibilities for the other digits
  If N[1] = 2, there are 8*7 possibilities for the other digits
  If N[1] = 3
    If N[2] = 0, there are 7 possibilities for the other digits
    If N[2] = 1, there are 7 possibilities for the other digits
    If N[2] = 2
      If N[3] = 0, there is 1 possibility (no other digits)
      If N[3] = 1, there is 1 possibility (no other digits)
      If N[3] = 2, there is 1 possibility (no other digits)
      If N[3] = 3, there is 1 possibility (no other digits)

上記は次のようなものです。

uniques += (N[0]-1)*9!/(9-N.length+1)!
for (int i = 1:N.length)
  uniques += N[i]*(9-i)!/(9-N.length+1)!

// don't forget N
if (hasUniqueDigits(N))
  uniques += 1

上記は十分に高速であるため、実際にはDPは必要ありません。

編集：

上記は実際にはもう少し複雑にする必要があります (上記の N[2] = 2 および N[3] = 2 は無効です)。次のようにする必要があります。

binary used[10]
uniques += (N[0]-1)*9!/(9-N.length+1)!
used[N[0]] = 1
for (int i = 1:N.length)
  uniques += (N[i]-sum(used 0 to N[i]))*(9-i)!/(9-N.length+1)!
  if (used[N[i]] == 1)
    break
  used[N[i]] = 1

// still need to remember N
if (hasUniqueDigits(N))
  uniques += 1
于 2013-03-01T10:44:47.707 に答える
1

怠け者の DP:

Prelude> :m +Data.List
Data.List> length [a | a <- [1..5324], length (show a) == length (nub $ show a)]
2939
于 2013-03-01T11:54:41.233 に答える