Это вопрос интервью. Подсчитайте все числа с уникальными цифрами (в десятичной форме) в диапазоне [1, N].
Очевидным решением является проверка каждого числа в диапазоне, если его цифры уникальны. Мы также можем сгенерировать все числа с уникальными цифрами (как перестановки) и проверить, находятся ли они в диапазоне.
Теперь мне интересно, есть ли решение для динамического программирования (DP) для этой проблемы.
Я думаю:
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, поскольку вышеуказанное должно быть достаточно быстрым.
EDIT:
Приведенное выше должно быть немного сложнее (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
Ленивый человек DP:
Prelude> :m +Data.List
Data.List> length [a | a <- [1..5324], length (show a) == length (nub $ show a)]
2939
Хотя этот вопрос был опубликован в 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");
}
}
Для такого вопроса интервью, вероятно, нужен алгоритм грубой силы, чтобы продемонстрировать логику и способность программировать. Но также важно продемонстрировать знание хорошего инструмента для работы.
Конечно, после большого количества времени, затраченного на расчет, вы можете придумать сложную математическую формулу, чтобы сократить алгоритм цикла. Но этот вопрос является простым примером сопоставления шаблонов, поэтому почему бы не использовать инструмент сопоставления шаблонов, встроенный в любой язык, который вы будете использовать: регулярные выражения?
Здесь очень простое решение в С# в качестве примера:
string csv = string.Join(",", Enumerable.Range(1, N));
int numUnique = N - Regex.Matches(csv, @"(\d)\d*\1").Count;
Строка 1 будет отличаться в зависимости от используемого вами языка, но она просто создает CSV всех целых чисел от 1 до N.
Но строка 2 будет очень похожа, независимо от того, на каком языке: подсчитайте, сколько раз шаблон соответствует в csv.
Шаблон регулярного выражения соответствует цифре, за которой следует некоторые другие цифры, а затем дубликат первой цифры.
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);
}
}