找顺数题解

大家好，我是讯享网，很高兴认识大家。

找顺数

现在给出一个大于1的正整数n，请你求出在1到n的正整数中，至少有一个数位含有6的正整数个数。

输入：100

输出：19

算法思路

很明显，这题就是需要利用数位DP来做，通常采用数位dp的来做的题型就是：“给定某一区间，然后求出满足某一条件的数的个数”。那么针对这题而言的话，应该如何采用数位dp来实现这题的解答呢。

对于其给定的数N，也就是其的数字的上界，所有的数均满足n<=N；现在将N拆分为n位数：An-1,An-2,An-3…A0;对于每一位数其范围都是依赖于前一项的，主要是看前一项是否取到了边界条件。

举个例子：N=23456，那么对于第一位可以取值的范围是0-2，而当取到2的时候，也就是达到边界，那么下一位的所能取到的数就是0-3了；而没有取到2的数就无所谓了，0-9都可以取。后面的也同样依葫芦画瓢。其实也就是一个树，见下图:

讯享网

blog/树.png · zmc-x/图库 - 码云 - 开源中国 (gitee.com)

那么要怎样来求解呢？本质来说其实还是枚举。首先对于这一题的要求是寻找区间范围中为含有6的个数，那么其实就是这n位数中只要有一位含有6就可以了。那么首先假设在第p位上，假如其取到了6且不是上边界，那么后面的数就无所谓了，选什么都可以，那么就有10^p种方案(注意这里位数是从0开始算的)；对于是上边界的话，这个就比较好算了，就是其该位数后面的所有上边界组成的数再加上1（还有全是0的情况）；当要不等于6的话就直接到下一位进行计算，所以再最后的算法实现过程中是要用到递归的。这其实已经是大致的实现过程了，还得在判断是否是存在限制（其实也就是受不受到上边界的影响）。这个问题其实很好判断，直接利用一个flag标志来实现就可以了，当flag=1就代表其是有限制的，为0就代表没有限制，再向下寻找的过程中必然也要传递flag这个参数，那么应该如何去传递呢？其实很简单就flag&&该位是否等于上边界；那么就可以了。这里可以利用写一个dfs函数来实现，其中包含两个参数：当前位数，是否受限制，然后在函数中进行计数即可。

现在来分析一下时间复杂度，很显然按照上面这么写的话，时间复杂度也是指数级的。那么很显然就过不了了，准确的说这还只是数位dp的第一步--------搜索，第二步就是利用记忆功能（其实也就是数据暂存）。简单的分析一下，对于第p位而言，向下寻找的话就是dfs(p-1,限制位),对于不同的p位的数，向下寻找的的也就是dfs(p-1,限制位)，那么对于所有的第p位而言，就是dfs(p-1,限制位)；所以就可以利用一个数组来进行存储dfs(xxx,xxx),那么之后再使用的dfs(xxx,xxx),就可以使用该数组来替代。那么这样的话，就会减少一些不必要的计算，时间复杂度就会下降至NlogN（应该没有算错吧，有点不确定），对于这个只有在非限制位才可以使用，当满足条件是可以直接return该数组中此位的数，而当不能够return的时候，那就只能计算了，然后再将其值赋给数组中对应的位，前提条件是非限制才可以赋值。

源码

ps：建议先理解上面的算法，or通过下面的代码来理解，然后再自己重新写一遍

#include<stdio.h> #include<string.h> #define N 15 long long a[N],mid[N];//存储每位的边界,mid来存储幂指运算 long long f[N];//记录dfs， int init(long long n) { 
    int i=0; while(n!=0){ 
    a[i]=n%10; n=n/10; i++; } return i; } long long dfs(int p,int flag)//1表示约束，0表示为不是边界 { 
    if(p<0) return 0; if(flag==0&&f[p]!=-1) return f[p]; int right=9; long long cnt=0; if(flag==1) right=a[p]; for(int i=0;i<=right;i++){ 
    if(i==6){ 
    if(flag==1&&i==a[p]){ 
    cnt++; for(int j=p-1;j>=0;j--) cnt+=a[j]*mid[j]; } else cnt+=mid[p]; } else cnt+=dfs(p-1,flag&&i==right); } if(flag==0) f[p]=cnt; return cnt; } int main() { 
    long long n; scanf("%lld",&n); memset(f,-1,sizeof(f)); int len=init(n); mid[0]=1; for(int i=1;i<N;i++){ 
    mid[i]=10*mid[i-1]; } printf("%lld",dfs(len-1,1)); return 0; }

讯享网

嗯，可能算法讲的不是很好，这里推荐一个视频，大家可以通过下面这个b站视频来寻找灵感

闫式DP分析法

找顺数

算法思路

源码

相关推荐