统计数字
in 算法 with 0 comment

统计数字

in 算法 with 0 comment

题目

计算数字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的话,是要再加上一个的。

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出现的次数,我们以百位为例:
要分成下面几种情况:

1.百位小于2:

比如12123:百位一共可能出现多少个2 呢?

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

2.百位等于2:

比如12223

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

3.百位大于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的话还要处理两种特殊情况:

int digitCounts(int k, int n) {
    if(k==0&&n==0)   
    return 1;
    int res=0;   
    int pow=1;   
    int temp=n;  
    while(temp!=0)
    {
        int dig=temp%10;      
        if(dig<k)       
        {
            res+=(temp/10)*pow;     
        }
        else if(dig==k)          
        {
            if(k==0&&pow!=1)    
            res+=(temp/10-1)*pow+n%pow+1;
            else                
            res+=(temp/10)*pow+n%pow+1;
        }
        else              
        {
            if(!(k==0&&temp/10==0))     
            
            {
            if(k==0&&pow!=1)
            {
            res+=(temp/10)*pow;
            }
            else
            {
            res+=(temp/10+1)*pow;    
            }
            }
        }
        
        temp/=10;
        pow*=10;
    }
    
     return res;
}

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

 int digitCounts(int k, int n) {
    if(k==0&&n==0)   
    return 1;
    int res=0;   
    int pow=1;   
    int temp=n;  

    if(k==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)   
        {
            res+=(temp/10)*pow;
        }
        temp/=10;
        pow*=10;
    }
    return res+1;  
    }
  
    while(temp!=0)   
    {
        int dig=temp%10;      
        if(dig<k)       
        {
            res+=(temp/10)*pow;     
        }
        else if(dig==k)          
        {
            res+=(temp/10)*pow+n%pow+1;
        }
        else              
        {
            res+=(temp/10+1)*pow;   
        }
        
        temp/=10;
        pow*=10;
    }
    return res;
}

题目链接

Responses