前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >3. 统计数字暴力破解找规律

3. 统计数字暴力破解找规律

作者头像
和蔼的zhxing
发布2018-09-04 13:13:37
2.3K0
发布2018-09-04 13:13:37
举报
文章被收录于专栏:和蔼的张星的图像处理专栏

计算数字k在0到n中的出现的次数,k可能是0~9的一个值 样例: 例如n=12,k=1,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],我们发现1出现了5次 (1, 10, 11, 12)

暴力破解

把每个数的每一个位都拿出来和k来比较,如果相同的话计数器加1就可以了,这也是最容易想到的一个方法,其实我还想过全部转化成字符串加起来,然后通过字符串去统计,估计也是可以的,先把暴力破解放在下面,有个小问题需要注意:循环条件是到0停止的,所以如果k是0的话,是要再加上一个的。

代码语言:javascript
复制
   int digitCounts(int k, int n) {
    int res = 0;
    int temp;
    for (int i = 0; i <= n; i++)
    {
        temp = i;    
//这里一定要用临时变量把i替换掉,如果直接处理i,就死循环了。
        while (temp!=0)
        {
            if (temp%10 == k)
                res++;
            temp/= 10;
        }
    }
    if(k==0)
    return res+1;
    
    return res;
    }

tips:一开始直接在循环里把i拿来直接处理了,这样是不可以的,这种for循环不要再循环体内处理循环变量,虽然很傻逼的错误,但是不注意真的就会犯。

找规律

这个题一看也是一个数学题,我试着找了一下规律并不是很好找,于是就去百度了。 把这个问题分解成统计每一位上这个数出现的次数,以一个5位数位例:ABCDE,假设我们要找2出现的次数,我们以百位为例: 要分成下面几种情况: 百位小于2: 比如12123:百位一共可能出现多少个2 呢?

200~299 1200~1299 2200~2299 3200~3299 …… 11200~11299 这里面一共是多少个呢? 一共有12100个,高位(比百位高的位)100(百位)

百位等于2: 比如12223

等于2的话情况稍微复杂一点,除了上述所说的这些呢,还有就是因为百位可以是2,那么低位的数就决定了要多多少个: 这里应该是:12*100+23

百位大于2: 比如12323

大于2的话,就表明前面的数可以再往上取一个: 200~299 1200~1299 2200~2299 3200~3299 …… 11200~11299 12200~12299 这样的话一共是 (12+1)*100

这样总结一下就是: 假设当前位位数用1,10,100等表示,分别代表个位,十位,百位等。 当前位<k: res=(高位)当前位数 当前位==k: res=(高位)当前位数+低位数+1 当前位>k: res=(高位+1)*当前位数

对于非零的来说,都是这样的,但是如果要查找的是0,这样就是不对的,如果查找的是0,只会进入后两种情况:

如果当前位等于0的话,比如12023 那么会有多少呢: 1000-1099 2000~2099 …… 11000~11099 再加上 12000~12023一共是24个。 那么应该是(高位-1)*当前位数+地位数+1;

如果当前位大于0的话:比如12223 除了上面的这些,还应加上12000~12099,所以应该是: (高位)*当前位数。

不过对于0的话还要处理两种特殊情况: 最高位不能查找0,所以如果是最高位查找0,则跳过; 最低位的0要加一个:因为会多一个0。 比如对于123:要查找个位的0,应该是13个,高位从0~12, 但是对于123:对于十位呢:应该是12*10,比公式要少,因为高位不能是0。 所以0是特殊情况:建议把查找0的单独来处理,这样逻辑上会清晰一些,也可把零归入前面的几种情况,但是对于是不是0要做额外处理。我一开始找的一个答案,对零的处理是不对的,没有考虑当前为也是0的情况,所以如果用103类似的这种数测试就是跑不过的,但是可以跑过lintcode的测试集(我怀疑里面根本没有包含这种情况),改了一点可以了:

代码语言:javascript
复制
 int digitCounts(int k, int n)
    {
        
        if(k==0&&n==0)   //先处理特殊情况
        return 1;
        int res=0;   //计数器
        int pow=1;   //看是那一位,1代表个位,10代表十位,以此类推
        int temp=n;  //因为要求每一位的数,先把n存起来
        while(temp!=0)
        {
            int dig=temp%10;      //当前位
            if(dig<k)       
            {
                res+=(temp/10)*pow;     //小于k的情况
            }
            else if(dig==k)          //等于k的情况
            {
                if(k==0&&pow!=1)    //如果不是最低位要-1
                res+=(temp/10-1)*pow+n%pow+1;
                else                //如果是最低位,就不用减1了
                res+=(temp/10)*pow+n%pow+1;
            }
            else              //大于k的情况
            {
                if(!(k==0&&temp/10==0))     
                //排除没有最高位,寻找的数为0的情况,最高位是不可能有0的
                {
                if(k==0&&pow!=1)
                {
                res+=(temp/10)*pow;
                }
                else
                {
                res+=(temp/10+1)*pow;    //总感觉这里有点问题,
                }
                }
            }
            
            temp/=10;
            pow*=10;
        }
        
         return res;
    }

但是我还是想想把0单独来处理,这样好写很多,逻辑也更清晰:

代码语言:javascript
复制
 int digitCounts(int k, int n)
    {
        
        if(k==0&&n==0)   //先处理特殊情况
        return 1;
        int res=0;   //计数器
        int pow=1;   //看是那一位,1代表个位,10代表十位,以此类推
        int temp=n;  //因为要求每一位的数,先把n存起来
        

        if(k==0)        //查找的是0
        {
        while(temp!=0)
        {
            int dig=temp%10;
            if(dig==k)
            {
                res+=(temp/10-1)*pow+n%pow+1;
            }
            else if(dig>k&&temp/10!=0)   //不允许最高位查找0
            {
                res+=(temp/10)*pow;
            }
            temp/=10;
            pow*=10;
        }
        return res+1;  //这里是加上0这一个
        }
      
      //查找的不是0
        while(temp!=0)   
        {
            int dig=temp%10;      //当前位
            if(dig<k)       
            {
                res+=(temp/10)*pow;     //小于k的情况
            }
            else if(dig==k)          //等于k的情况
            {
                res+=(temp/10)*pow+n%pow+1;
            }
            else              //大于k的情况
            {
                res+=(temp/10+1)*pow;   
            }
            
            temp/=10;
            pow*=10;
        }
        
         return res;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017.12.03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 暴力破解
  • 找规律
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档