[Lintcode] 3 统计数字

计算数字 k 在 0 到 n 中的出现的次数，k 可能是 0~9 的一个值。

描述

计算数字 k 在 0 到 n 中的出现的次数，k 可能是 0~9 的一个值。

样例

1
2
3
输入：k = 1, n = 1
输出：1
解释：在[0,1]中，我们发现1出现了1次(1)。
1
2
3
输入：k = 1, n = 12
输出：5
解释：在[0,1,2,3,4,5,6,7,8,9,10,11,12]中，我们发现1出现了5次(1,10,11,12)(注意11中有两个1)。

思路

以k = 5为例：

每10位产生1个数，[0,9]有一个5，[10,19]有一个15，[20,29]有一个25

每100位产生10个数，[0,99]有10个5，即[50,59]，[100,199]有10个5，即[150,159]

每1000位产生100个数，[0,999]有100个5，即[500,599]

以此类推……

当 n = 2169，k = 1 时：

个位：9前面有216个10，故有216个1，又因为9>1，所以一共有216+1=217个1

十位：6前面有21个100，100中有10个1，故有21*10=210个1，又因为6>1，所以包含了10~19的10个1，一共有210+10=220个1

百位：1前面有2个1000，1000中有100个1，故有2*100=200个1，这里1==1，也就是多了100~169一共70个1，一共有200+70=270个1

千位：2>1，包含了1000~1999的1000个1

一共有217+220+270+1000=1707个1

但当 k = 0 时的情况不同，当 n = 2169，k = 0 时：

个位：9前面有216个10，故有216个0，又因为9>0，所以一共有216+1=217个0

十位：6前面有21个100，100中有10个0，故有21*10=210个0，但00到09的情况不存在，故只有210-10=200个0，又因为6>0，所以包含了00到09的10个0，一共有200+10=210个0

百位：1前面有2个1000，1000中有100个0，故有2*100=200个1，但000到099的情况不存在，故只有200-100=100个0，这里1>0，所以包含了000到099的100个0，一共有100+100=200个0

千位：2>0，但0000到0999的情况不存在

一共有217+210+200=627个0

因此，当计算从右往左数第 i位包含 k 的个数时：

若第 i 位大于k，则结果为**第 i 位左边所有数字乘以10i-1次方 **+ 10i-1次方

若第 i 位小于k，则结果为第 i 位左边的所有数字乘以10i-1次方

若第 i 位等于k，则结果为**第 i 位左边所有数字乘以10i-1次方 **+ 右边的所有数字+1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    /**
     * @param k: An integer
     * @param n: An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    int digitCounts(int k, int n) {
        // write your code here
        int bit=1;//当前位的权重
        int bitnum=0;//当前位的具体数字
        int sum=0;//k出现的总次数
        int val=n;//赋值val用于计算每位
        int t=0;//处理k=0时候的情况，t为要减去的情况之和
    
        if(n==k)
            return 1;
        
        while(val!=0)
        {
            bitnum=val-(val/10)*10;
            if(bitnum<k)
                sum+=(val/10)*bit;
            else if(bitnum==k)
                sum+=(val/10)*bit+n-val*bit+1;
            else
                sum+=(val/10)*bit+bit;
            t+=bit;
            bit*=10;
            val/=10;
        }
        if(k==0)
        {
            sum-=(t-1);//减1是去掉bit为1时的情况，即0的情况存在
        }
        return sum;
    }
};
参考
  1. https://blog.csdn.net/Flag_died/article/details/104062613
  2. https://blog.csdn.net/weixin_42316707/article/details/86510114