public class Solution {
public int numDupDigitsAtMostN(int N) {
if (N < 11) return 0;
String Nstr = String.valueOf(N);
int Nlength = Nstr.length();
int nonrepeatableNumTotal = 0;
//首先数清楚位数小于 N 的数中发生了重复的数
//位数等于 n 时,最高位也就是第一位只有 9 种选择(不能选 0 )但
//但之后的 n-1 位可从(10-1)个数字中任一选择
for (int i = 0; i + 1 < Nlength; i++) {
nonrepeatableNumTotal += (9 * A(i, 9));
}
//然后数清楚和给出的数据等位数的数里有发生了重复的数
//由于规定了位数要相同,所以最高位即 i==1 时不能取 0,故有 t-1
for (int i = 0; i < Nlength; i++) {
int t = Nstr.charAt(i) - '0';
if (i == 0) {
nonrepeatableNumTotal += ((t - 1) * A(Nlength - 1, 9));
} else {
nonrepeatableNumTotal += (t * A(Nlength - 1 - i, 9 - i));
}
}
int used = 0;
for (char c : Nstr.toCharArray()) {
int t = (1 << (c - '0'));
if ((used & t) == 0) {
used |= t;
} else {
return N - nonrepeatableNumTotal + 1;
}
}
return N - nonrepeatableNumTotal;
}
private int factorial(int n) {
if (n == 1 || n == 0) return 1;
return n * factorial(n - 1);
}
private int A(int m, int n) {
return factorial(n) / factorial(n - m);
}
}
谢谢
1
lysS 2020-05-18 19:30:44 +08:00
php 我这样写的, 思路就那么几种
https://gist.github.com/lysShub/d313e16861e6e97deed686e15a4e60f2 |