题目地址：https://leetcode-cn.com/problems/numbers-with-repeated-digits/
题目叙述：
给定正整数N，返回小于等于 N且具有至少 1 位重复数字的正整数。
示例 1：
输入：20输出：1解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：
输入：100输出：10解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：
输入：1000输出：262
提示：
1 <= N <= 10^9
记录一下一波三折的解题过程：
方法1：
使用代码最少的方法，两层循环，外层循环从N循环到10，内层循环：N%10，N/=10，从个位往上记录出现的数字，出现重复数字跳出内层循环，count++。
class Solution {
public:
int numDupDigitsAtMostN(int N) {
int count=0;
while(N>10){
int tmpN=N;
int *recorder=new int[10];
while(tmpN>=1){
int tmp=tmpN%10;
if(recorder[tmp]==1){
count++;
break;
}
recorder[tmp]=1;
tmpN=tmpN/10;
}
N--;
}
return count;
}
};
时间复杂度评估:O(nlogn)，这种方法挑战到第99个测试用例就超时了，进行优化：
方法2：
优化了几个地方：1.从高位往个位来查找重复数字，在出现重复的数位将后面部分截断，直接跳过重复数位后面数位的逐个迭代，例如在2020024直接跳到2019999，重复个数加25。2.使用case判断替代pow来计算10的n次方以加快速度。
class Solution {
public:
int numDupDigitsAtMostN(int N) {
int count=0;
int x=log10(N);
int recorder[10];
int cut;
int tmpX;
while(N>10){
cut=1;
if(getPower(x)>N){
x--;
}
tmpX=x;
memset(recorder, 0, sizeof(int)*10);
while(tmpX>=0){
int power=getPower(tmpX);
int tmp=((N/power)%10);
if(recorder[tmp]==1){
cut=N-((N/power)*power)+1;
count+=cut;
break;
}
recorder[tmp]=1;
tmpX--;
}
N-=cut;
}
return count;
}
int getPower(int x){
switch (x){
case 0:
return 1;
break;
case 1:
return 10;
break;
case 2:
return 100;
break;
case 3:
return 1000;
break;
case 4:
return 10000;
break;
case 5:
return 100000;
break;
case 6:
return 1000000;
break;
case 7:
return 10000000;
break;
case 8:
return 100000000;
break;
case 9:
return 1000000000;
break;
default:
return 1;
}
}
};
时间复杂度评估:O(nlogn)，这种方法坚持到第110个测试用例才超时，看来得换个思路了。
方法3：
认真分析其实这是一道高中的排列组合题目，计算出不重复的数字的个数，然后用N来减就行了。N-1数位的数字的组合其实可以很方便地计算出来：9x9x8x...(最大数位k-1个数相乘)+9x9x8x...(最大数位k-2个数相乘)+...+9即可算出。麻烦的是N数位的数字的组合难以计算，从高数位往低数位迭代，分为三步：
1.最大数位：最大位数字n进行-1然后乘以9x8x...（最大数位k-1次），将结果累加；
2.中间数位J：判断前面是否有重复数字，有的话剩下的事情就别干了,break循环，没有的话：计算前面小于当前数位数字的数字的个数z，当前位数数字减去这个个数z得到v，vx((9-j)x(8-j)x...(最大数位k-j-1次乘法迭代))，将结果累加，J往后递增；
3.末尾数：判断前面是否有重复数字，有的话剩下的事情就别干了，没有的话：计算前面小于当前数位数字的数字的个数z，当前位数数字减去这个个数z得到v，将v累加；
最后返回N-累加结果；
class Solution {
public:
int numDupDigitsAtMostN(int N) {
if(N<=10)
return 0;
int rawN=N;
int count=0;
int x=log10(N);
int *n = new int[x+1];
for(int i=x;i>=0;i--){
n[i]=N%10;
N/=10;
}
count+=getFloor2(x-1);
int duplicated=0;
for(int j=0;j<=x&&duplicated==0;j++){
if(j==0){
count+=(n[j]-1)*getFloor3(x-1,0);
}
else if(j==x){
int tmp=n[j]+1;
int k[10] = {};
for(int v=0;v<j;v++){
if(k[n[v]]==1){
duplicated=1;
break;
}
if(n[j]>=n[v]){
tmp--;
}
k[n[v]]=1;
}
if(duplicated==0)
count+=tmp;
}
else{
int tmp=n[j];
int k[10] = {};
for(int v=0;v<j;v++){
if(k[n[v]]==1){
duplicated=1;
break;
}
if(n[j]-1>=n[v]){
tmp--;
}
k[n[v]]=1;
}
if(duplicated==0)
count+=tmp*getFloor3(x-j-1,j);
}
}
return rawN-count;
}
int getFloor(int n){
int res=1;
for(int i=9,j=0;j<=n;j++){
res*=i;
if(j!=0){
i--;
}
}
return res;
}
int getFloor2(int x){
if(x<0)
return 0;
int res=0;
for(int i=x;i>=0;i--){
res+=getFloor(i);
}
return res;
}
int getFloor3(int n,int o){
if(n<0)
return 0;
int res=1;
for(int i=9-o,j=0;j<=n;j++,i--){
res*=i;
}
return res;
}
};
方法3完美运行。时间复杂度评估:O(logn)。
image
其他：
看到其他用户的解答用到一种叫做dp数位的方法。dp数位是一个类似动态规划（一个问题可以化为同样类型的几个子问题）的递归方法，适用于类似需要在一个区间段寻找符合条件的数字个数的题目，有时间学习一下。
网友评论