指定された範囲内のすべての数字を一意の数字でカウントします。

Question

これはインタビューの質問です。範囲[1、N]のすべての数値を一意の数字（10進数）で数えます。

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

今、この問題の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 

：あなたはあなたのその後Nが持っている桁の数から1を引いた

に到達するまで

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 

は、上記のすべてを追加します。ただ行う必要があります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 

ので：あなたが本当に上記のは十分に高速である必要がありますようDPを必要としない

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 

：

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) 

上記のようなものです。

が

編集：

上記は実際に少し複雑にする必要がある（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行目は、あなたが使用している言語によって異なりますが、それはちょうど1からN.

にすべての整数のCSVを作成しています

しかし、2行目はどんな言語であっても非常によく似ています：パターンがCSVで何回一致するかを数えます。

正規表現パターンは、最初の桁の複製に続いて、おそらくいくつかの他の桁続く数字と一致します。