在给定范围内计算所有具有唯一数字的数字数量

Question

在给定范围内计算所有具有唯一数字的数字数量

algorithmdynamic-programming

15

这是一个面试题。计算在[1, N]范围内所有具有唯一数字（十进制）的数字总数。

明显的解决方案是测试范围内每个数字是否具有唯一数字。我们也可以生成所有具有唯一数字的数字（作为排列），并测试它们是否在范围内。

现在我想知道是否有一个DP（动态规划）解决方案来解决这个问题。

- Michael

为了以后参考，听起来可能更适合在CodeGolf上。 - Bernhard Barker

你应该计数它们，而不是生成它们。 - n. m.

顺带一提，关于最大不同数字数的公式，对于一个n位数 a(n) = 9*9!/(10-n)!，可以在此链接找到：http://oeis.org/A073531。 - user978923

7个回答

2

针对这样的面试问题，通常需要使用暴力算法来展示逻辑推理和编程能力。但同样重要的是展示对工具的了解。

当然，经过大量计算后，您可以提出一个复杂的数学公式来缩短循环算法。但是，这个问题是一个明显的模式匹配示例，为什么不使用几乎所有语言中都内置的模式匹配工具：正则表达式？

以下是 C# 中一个极其简单的解决方案示例：

string csv = string.Join(",", Enumerable.Range(1, N));
int numUnique = N - Regex.Matches(csv, @"(\d)\d*\1").Count;

第一行代码根据您使用的语言而异，但只是创建了一个从1到N的所有整数的CSV文件。

但是第二行代码无论使用哪种语言都非常相似：计算csv文件中模式匹配的次数。

正则表达式模式匹配可能跟随其他数字的一个数字，然后是第一个数字的副本。

- Brian Stephens

1

尽管这个问题是在2013年发布的，但我觉得仍然值得提供一个实现作为参考，因为除了Dukeling给出的算法之外，我在互联网上找不到任何其他的实现。我用Java编写了暴力和Dukeling的排列算法的代码，如果我没错的话，它们应该总是产生相同的结果。希望它能帮助那些努力寻找实际运行解决方案的人。

public class Solution { 

    public static void main(String[] args) {
        test(uniqueDigitsBruteForce(5324), uniqueDigits(5324));
        test(uniqueDigitsBruteForce(5222), uniqueDigits(5222));
        test(uniqueDigitsBruteForce(5565), uniqueDigits(5565));
    }

     /**
     * A math version method to count numbers with distinct digits.
     * @param n
     * @return
     */
    static int uniqueDigits(int n) {
        int[] used = new int[10];
        String seq = String.valueOf(n);
        char[] ca = seq.toCharArray();
        int uniq = 0;

        for (int i = 1; i <= ca.length - 1; i++) {
            uniq += uniqueDigitsOfLength(i);
        }

        uniq += (getInt(ca[0]) - 1) * factorial(9) / factorial(9 - ca.length + 1);
        used[getInt(ca[0])] = 1;
        for (int i = 1; i < ca.length; i++) {
            int count = 0;
            for (int j = 0; j < getInt(ca[i]); j++) {
                if (used[j] != 1) count++;
            }
            uniq += count * factorial(9 - i) / factorial(9 - ca.length + 1);
            if (used[getInt(ca[i])] == 1)
                break;
            used[getInt(ca[i])] = 1;
        }

        if (isUniqueDigits(n)) {
            uniq += 1;
        }
        return uniq;
    }


    /**
     * A brute force version method to count numbers with distinct digits.
     * @param n
     * @return
     */
    static int uniqueDigitsBruteForce(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (isUniqueDigits(i)) {
                count++;
            }
        }
        return count;
    }



    /**
     * http://oeis.org/A073531
     * @param n
     * @return
     */
    static int uniqueDigitsOfLength(int n) {
        if (n < 1) return 0;
        int count = 9;
        int numOptions = 9;
        while(--n > 0) {
            if (numOptions == 0) {
                return 0;
            }
            count *= numOptions;
            numOptions--;
        }
        return count;
    }

    /**
     * Determine if given number consists of distinct digits
     * @param n
     * @return
     */
    static boolean isUniqueDigits(int n) {
        int[] used = new int[10];
        if (n < 10) return true;
        while (n > 0) {
            int digit = n % 10;
            if (used[digit] == 1)
                return false;
            used[digit] = 1;
            n = n / 10;
        }
        return true;
    }

    static int getInt(char c) {
        return c - '0';
    }

    /**
     * Calculate Factorial
     * @param n
     * @return
     */
    static int factorial(int n) {
        if (n > 9) return -1;
        if (n < 2) return 1;
        int res = 1;            
        for (int i = 2; i <= n; i++) {
            res *= i;
        }
        return res;
    }

    static void test(int expected, int actual) {
        System.out.println("Expected Result: " + expected.toString());
        System.out.println("Actual Result: " + actual.toString());
        System.out.println(expected.equals(actual) ? "Correct" : "Wrong Answer");
    }
}

- Robert.Li

1

以下是Python解决方案的总结：

该解决方案基于Bernhard Barker在回答列表中提供的数学原理：

感谢Bernhard的理想。

def count_num_with_DupDigits(self, n: int) -> int:
    # Fill in your code for the function. Do not change the function name
    # The function should return an integer.
    n_str = str(n)
    n_len = len(n_str)
    n_unique = 0
    
    
    # get the all the x000 unique digits
    if n > 10:
        for i in range(n_len-1):
            n_unique = n_unique + 9*int(np.math.factorial(9)/np.math.factorial(10-n_len+i+1))
        m=0
        if m == 0:
            n_first  = (int(n_str[m])-1)*int(np.math.factorial(9)/np.math.factorial(10-n_len))
        m=m+1
        count_last=0
        n_sec=0
        
        
        for k in range(n_len-1):
            if m == n_len-1:
                count_last = int(n_str[m])+1
                for l in range(int(n_str[m])+1):a
                           if n_str[0:n_len-1].count(str(l)) > 0:
                               count_last = count_last-1
              
            else:
                for s in range(int(n_str[k+1])):
                    if n_str[0:k+1].count(str(s))>0:
                        n_sec=n_sec
                    else:
                        n_sec = int(np.math.factorial(9-m)/np.math.factorial(10-n_len))+n_sec
                if n_str[0:k+1].count(n_str[k+1]) > 0:
                    break
                m= m+1

        value=n-(n_sec+n_first+n_unique+count_last)
    else:
        value = 0
    return value

- Jio Du

1

懒人DP：

Prelude> :m +Data.List
Data.List> length [a | a <- [1..5324], length (show a) == length (nub $ show a)]
2939

- גלעד ברקן

11

对于不懂这种语言的人而言，这段话就是无意义的。这并不是一个特定的语言问题。 - Bernhard Barker

很明显这是 Haskell。我对此没问题。 - Michael

0

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution { 
 public static void main(String[] args) {

         int rem;
        Scanner in=new Scanner(System.in);
         int num=in.nextInt();
    int length = (int)(Math.log10(num)+1);//This one is to find the length of the number i.e number of digits of a number


    int arr[]=new int[length]; //Array to store the individual numbers of a digit for example 123 then we will store 1,2,3 in the array

    int count=0;
     int i=0;

     while(num>0)           //Logic to store the digits in array
    { rem=num%10;   
        arr[i++]=rem;
        num=num/10; 
    }     
    for( i=0;i<length;i++)          //Logic to find the duplicate numbers
    {
        for(int j=i+1;j<length;j++)
        {
            if(arr[i]==arr[j])
            {
                count++;
                 break;
            }
        }
    }
     //Finally total number of digits minus duplicates gives the output
     System.out.println(length-count);
   }
}

- m_prasu

0

这是你想要的，用Python实现的

def numDistinctDigitsAtMostN(n):
    nums = [int(i) for i in str(n+1)]
    k = len(str(n+1))
    res = 0
    # Here is a paper about Number of n-digit positive integers with all digits distinct
    # http://oeis.org/A073531
    # a(n) = 9*9!/(10-n)!

    # calculate the number of n-digit positive integers with all digits distinct
    for i in range(1, k):
        res += 9 * math.perm(9,i-1)

    # count no duplicates for numbers with k digits and smaller than n
    for i, x in enumerate(nums):
        if i == 0:
            digit_range = range(1,x) # first digit can not be 0
        else:
            digit_range = range(x)

        for y in digit_range:
            if y not in nums[:i]:
                res += math.perm(9-i,k-1-i)
        if x in nums[:i]:
            break
    return res

以下是一些很好的测试用例。它们足够大，可以测试我的代码。

numDistinctDigitsAtMostN(100) = 90 #(9+81)
numDistinctDigitsAtMostN(5853) = 3181
numDistinctDigitsAtMostN(5853623) = 461730
numDistinctDigitsAtMostN(585362326) = 4104810

- Rimuru Tempest

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

我在思考：

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。

然后只需执行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