Đếm tất cả các số có các chữ số duy nhất trong một phạm vi nhất định

Question

Đây là câu hỏi phỏng vấn. Đếm tất cả các số có các chữ số duy nhất (tính bằng số thập phân) trong phạm vi [1, N].

Giải pháp hiển nhiên là kiểm tra từng số trong phạm vi nếu các chữ số của nó là duy nhất. Chúng tôi cũng có thể tạo tất cả các số có các chữ số duy nhất (như hoán vị) và kiểm tra nếu chúng nằm trong phạm vi.

Bây giờ tôi tự hỏi liệu có giải pháp DP (lập trình động) cho vấn đề này hay không.

Answer 1

Tôi đang nghĩ đến:

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 

Vì vậy:

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 

Thêm tất cả những điều trên cho đến khi bạn nhận được để số lượng chữ số mà N có trừ đi 1.

Sau đó, bạn chỉ phải làm Number of unique digits numbers 1000-5324

Và:

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 

Vì vậy:

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) 

Trên đây là một cái gì đó như:

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 

Bạn không thực sự cần DP như trên nên được đủ nhanh.

EDIT:

Trên đây thực sự cần phải được phức tạp hơn một chút (N [2] = 2 và N [3] = 2 ở trên là không hợp lệ). Nó cần phải được nhiều hơn như:

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 Lazy của con người:

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

Mặc dù câu hỏi này đã được đăng trong năm 2013, tôi cảm thấy như nó vẫn còn xứng đáng để cung cấp một thực hiện để tham khảo như khác với thuật toán được đưa ra bởi Dukeling tôi không thể tìm thấy bất kỳ thực hiện trên internet.

Tôi đã viết mã bằng Java cho cả lực lượng vũ phu và thuật toán hoán vị của Dukeling và, nếu tôi đúng, chúng phải luôn mang lại kết quả tương tự.

Hy vọng nó có thể giúp ai đó cố gắng hết sức để tìm ra giải pháp chạy thực tế.

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ó câu hỏi phỏng vấn như thế, thuật toán brute-force có thể nhằm mục đích chứng minh năng lực logic và lập trình. Nhưng cũng quan trọng là thể hiện kiến ​​thức về một công cụ tốt cho công việc.

Chắc chắn, sau nhiều thời gian để tính toán, bạn có thể đưa ra một công thức toán học phức tạp để rút ngắn thuật toán lặp.Nhưng câu hỏi này là một ví dụ đơn giản về khớp mẫu, vậy tại sao không sử dụng công cụ khớp mẫu được tích hợp vào bất kỳ ngôn ngữ nào bạn sẽ sử dụng: cụm từ thông dụng?

Dưới đây là một giải pháp cực kỳ đơn giản trong C# là một ví dụ:

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

Line 1 sẽ khác nhau tùy thuộc vào ngôn ngữ mà bạn sử dụng, nhưng nó chỉ tạo ra một CSV của tất cả các số nguyên từ 1 đến N.

Nhưng Dòng 2 sẽ rất giống nhau bất kể ngôn ngữ nào: đếm số lần so khớp mẫu trong csv.

Các mô hình regex phù hợp một chữ số có thể theo sau bởi một số chữ số khác, tiếp theo là một bản sao của chữ số đầu tiên.