用給定範圍內的唯一數字計算所有數字

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

And：

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

懶漢DP：

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

Answer 3

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

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

對於這樣一個面試問題，蠻力算法可能意，表現出邏輯和編程能力。但同樣重要的是展示對這項工作的好工具的知識。

當然，經過大量的時間計算，你可以想出一個複雜的數學公式來縮短循環算法。但是這個問題是模式匹配的一個直接例子，爲什麼不使用內置的模式匹配工具來使用任何語言：正則表達式？

下面是在C＃中一個極其簡單的解決方案爲例：

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

1號線將根據您使用的語言不同，但它只是創建所有整數的CSV從1到N

但是無論使用什麼語言，第2行都會非常相似：統計csv中模式的匹配次數。

正則表達式模式匹配一個數字可能跟隨一些其他數字，接着第一數字的副本。