algorithm - 计算给定范围内具有唯一数字的所有数字

Question

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

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

现在我想知道这个问题是否有DP（动态编程）解决方案。

Answer 1

我在想：

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

Answer 2

对于这样的面试问题，可能会使用蛮力算法来展示逻辑和编程能力。但同样重要的是展示对这项工作的好工具的了解。

当然，在花费大量时间进行计算之后，您可以想出一个复杂的数学公式来缩短循环算法。但是这个问题是模式匹配的一个简单示例，那么为什么不使用内置于您将使用的任何语言的模式匹配工具：正则表达式？

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

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

第 1 行会因您使用的语言而异，但它只是创建一个包含从 1 到 N 的所有整数的 CSV。

但是无论哪种语言，第 2 行都会非常相似：计算模式在 csv 中匹配的次数。

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

Answer 3

懒人DP：

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

Answer 4

虽然这个问题是在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");
    }
}

Answer 5

一个python解决方案总结如下：</p>

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

感谢伯恩哈德的理想

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

Answer 6

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);
   }
}