这是一个面试问题。计算 [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，因为上面的应该足够快了。
编辑：
上面实际上需要更复杂一点（上面的 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
对于这样的面试问题，可能会使用暴力算法来展示逻辑和编程能力。但同样重要的是展示对这项工作的好工具的了解。
当然，经过大量时间的计算，你可以想出一个复杂的数学公式来缩短循环算法。但是这个问题是模式匹配的一个简单示例，所以为什么不使用您将使用的几乎任何语言中内置的模式匹配工具：正则表达式？
这里有一个非常简单的 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 中模式匹配的次数。
正则表达式模式匹配一个数字，可能后跟一些其他数字，后跟第一个数字的重复项。
懒人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");
}
}
一个python解决方案总结如下：
该解决方案基于答案列表中先前提供的 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
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);
}
}
这就是你想要的，由Python实现
def numDistinctDigitsAtMostN(n):
nums = [int(i) for i in str(n+1)]
k = len(str(n+1))
res = 0
# Here is a paper about Number of n-digit positive integers with all digits distinct
# http://oeis.org/A073531
# a(n) = 9*9!/(10-n)!
# calculate the number of n-digit positive integers with all digits distinct
for i in range(1, k):
res += 9 * math.perm(9,i-1)
# count no duplicates for numbers with k digits and smaller than n
for i, x in enumerate(nums):
if i == 0:
digit_range = range(1,x) # first digit can not be 0
else:
digit_range = range(x)
for y in digit_range:
if y not in nums[:i]:
res += math.perm(9-i,k-1-i)
if x in nums[:i]:
break
return res
这里有一些很好的测试用例。 它们足够大来测试我的代码。
numDistinctDigitsAtMostN(100) = 90 #(9+81)
numDistinctDigitsAtMostN(5853) = 3181
numDistinctDigitsAtMostN(5853623) = 461730
numDistinctDigitsAtMostN(585362326) = 4104810
#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[19][2048][2];
int func(int pos, string &num,int mask, int tight){
if(pos == -1)
return 1;
if(dp[pos][mask][tight] != -1)
return dp[pos][mask][tight];
int ans=0;
int d = num[num.length()-pos-1]-'0';
if((1LL<<d)& mask)
dp[pos][mask][tight]=0;
int x = (tight ? d : 9);
for(int i=0;i<=x;i++)
{
ans += func(pos-1, num, mask+(1LL<<d), (i==x));
}
return dp[pos][mask][tight] = ans;
}
signed main()
{
// for(int i=0;i<19;i++)
// {
// for(int j=0;j<2048;j++)
// {
// dp[i][j][0]=dp[i][j][1]=-1;
// }
// }
memset(dp,-1,sizeof(dp));
int l,r;
cin>>l>>r;
string num = to_string(r);
int val1 = func(num.length()-1, num, 0, 1);
memset(dp,-1,sizeof(dp));
// l=l-1;
string temp = to_string(l);
cout<<temp<<endl;
int val2 = func(num.length()-1,temp,0,1);
int res= val1-val2;
cout<<res<<endl;
}