您好,欢迎来到网暖!

当前位置:网暖 » 站长资讯 » 建站基础 » 网络技术 » 文章详细 订阅RssFeed

(lintcode)第3题统计数字

来源:网络整理 浏览:368次 时间:2021-10-20

要求:计算数字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)

首先我们想到暴力破解法,也就是遍历每一个数,同时每一个数都遍历每一位,遍历每一位的方法是不断地整除10,直到整除为0.代码如下:

 

 

class Solution {    /*     * param k : As description.     * param n : As description.     * return: An integer denote the count of digit k in 1..n     */   public int digitCounts(int k, int n) {        // write your code here        int sum=0;        for(int i=0;i<=n;i++){            int num=i;            while(num/10!=0){                if(num%10==k){                    sum++;                }                num=num/10;            }            if(num==k)            sum++;        }                return sum;    }}

还有另一种方法,来自于《编程之美》,提高了效率。

 

思路如下:假如我们现在要求从1到一个5位数ABCDE之间,出现了2的数次是多少。我们现在把问题简单化,只考虑从0到ABCDE之间在百位(C)上出现2的次数,然后用在个位,十位,千位,万位上也适用,就可以算出总的。

第一种情况:当给出的五位数ABCDE中百位上的C是小于数字2的时候:

1.比如说,百位上是0,假如给定的五位数是12031,那么0到12031之间有哪一些数的百位上会出现2,从小到大数,200-299,1200-1299,2200-2299,3200-3299...,10200-10299,11200-11299.我们会发现后面三位是固定的,变化的只有比百位更高的位,高位从0(0代表200-299)到11,总共12个,再变大就超过了,因为百位上的数字是小于给定数字2的。那么我们发现当百位上是0的时候,百位上出现2的次数由更高的位决定,等于更高的位(12)X当前的位数100=1200个。

2.当百位上是1的时候,假设给定的五位数是12131,那么求出来的结果和百位上是0的一样,所以从1到ABCDE所有数字中,百位上出现2的次数也是1200.

第二种情况,也就是当给定的五位数ABCDE百位上的C刚好等我我们要求的次数的那个数字2

假如现在给定了一个12213,那么我们还是有200-299,1200-1299,2200-2299,3200-3299...,10200-10299,11200-11299这1200个,但是除了这些,还有一部分12200-12213(由低位数字+1),所以,当某一位的数字等于2的时候,百位上出现2的次数=更高位的数字x当前的位数+低位的数字+1;

第三种情况,当百位上的数字大于2的时候

假如说12313,那么这次除了200-299,1200-1299,2200-2299,3200-3299...,10200-10299,11200-11299,还包含了12200-12299,也没有低位的事情计算百位上出现2的次数是:(更高的位数+1)x当前的位数。

总结以下规律,我们要从1到ABCDE中找到k这个数字在某一位上出现了多少次

 当某一位的数字小于k时,那么该位出现i的次数为:更高位数字x当前位数 
当某一位的数字等于k时,那么该位出现i的次数为:更高位数字x当前位数+低位数字+1 
 当某一位的数字大于k时,那么该位出现i的次数为:(更高位数字+1)x当前位数

代码如下:

 

class Solution {  /*   * param k : As description.   * param n : As description.   * return: An integer denote the count of digit k in 1..n   */  public int digitCounts(int k, int n) {    if(k == 0 && n<10)      return 1; // 特殊情况    int temp = n, cnt = 0, pow = 1;//pow代表当前位的后面低位是多少,1为个位,10为十位,100位千位    while(temp != 0) {      int digit = temp % 10; // 根据当前位置数和k的大小关系,可以算出当前位置出现过k的次数      if(digit < k)        cnt += (temp / 10) * pow;      else if(digit == k)        cnt += (temp / 10) * pow + (n - temp * pow + 1);      else {        if(!(k == 0 && temp / 10 == 0)) // 排除没有更高位时,寻找的数为0的情况          cnt += (temp / 10 + 1) * pow;      }      temp /= 10;      pow *= 10;    }    return cnt;  }};

如果有所帮助,脸皮厚求个赞~

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

技术之路不在一时,山高水长,纵使缓慢,驰而不息。

公众号:秦怀杂货店

 

 

 

 

 

 

推荐站点

  • 腾讯腾讯

    腾讯网(www.QQ.com)是中国浏览量最大的中文门户网站,是腾讯公司推出的集新闻信息、互动社区、娱乐产品和基础服务为一体的大型综合门户网站。腾讯网服务于全球华人用户,致力成为最具传播力和互动性,权威、主流、时尚的互联网媒体平台。通过强大的实时新闻和全面深入的信息资讯服务,为中国数以亿计的互联网用户提供富有创意的网上新生活。

    www.qq.com
  • 搜狐搜狐

    搜狐网是全球最大的中文门户网站,为用户提供24小时不间断的最新资讯,及搜索、邮件等网络服务。内容包括全球热点事件、突发新闻、时事评论、热播影视剧、体育赛事、行业动态、生活服务信息,以及论坛、博客、微博、我的搜狐等互动空间。

    www.sohu.com
  • 网易网易

    网易是中国领先的互联网技术公司,为用户提供免费邮箱、游戏、搜索引擎服务,开设新闻、娱乐、体育等30多个内容频道,及博客、视频、论坛等互动交流,网聚人的力量。

    www.163.com
  • 新浪新浪

    新浪网为全球用户24小时提供全面及时的中文资讯,内容覆盖国内外突发新闻事件、体坛赛事、娱乐时尚、产业资讯、实用信息等,设有新闻、体育、娱乐、财经、科技、房产、汽车等30多个内容频道,同时开设博客、视频、论坛等自由互动交流空间。

    www.sina.com.cn
  • 百度一下百度一下

    百度一下,你就知道

    www.baidu.com