计算给定范围内具有唯一数字的所有数字 [英] Count all numbers with unique digits in a given range

问题描述

这是一道面试题.计算 [1, N] 范围内具有唯一数字(十进制)的所有数字.

This is an interview question. Count all numbers with unique digits (in decimal) in the range [1, N].

显而易见的解决方案是测试范围内的每个数字，如果其数字是唯一的.我们还可以生成具有唯一数字(作为排列)的所有数字并测试它们是否在范围内.

The obvious solution is to test each number in the range if its digits are unique. We can also generate all numbers with unique digits (as permutations) and test if they are in the range.

现在想知道这个问题有没有DP(动态规划)解决方案.

Now I wonder if there is a DP (dynamic programming) solution for this problem.

推荐答案

我在想:

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 的位数.

Add all of the above until you get to the number of digits that N has minus 1.

那么你只需要做唯一位数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，因为上面应该足够快了.

You don't really need DP as the above should be fast enough.

上面的实际上需要稍微复杂一些(上面的N[2] = 2和N[3] = 2是无效的).它需要更像:

The above actually needs to be a little more complicated (N[2] = 2 and N[3] = 2 above is not valid). It needs to be more like:

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

这篇关于计算给定范围内具有唯一数字的所有数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！