统计数字：计算数字 k 在 0 到 n 中的出现的次数，k 可能是 0~9 的一个值_统计数字k在o到n中的出现次数怎么算

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

Lintcode的题目，处理数字的话参考网上的思路数据没法全部通过，写了一个供参考。

思路：
统计每个位置上出现k的次数，即求k在第i位上确定后，范围内的所有有效的数字组合。

分类：
一.位置分类
将n分解为首位、中间位、个位，n记录每一位数字，原数字赋值m。

1.个位
个位出现k的次数和n/10相关。
每十位进位1次，k在个位会出现1次，当n个位左边的数完全相同时，需比较k与当前个位的大小。
(1) n>=k时，count += n/10 + 1
(2) n<k时，count += n/10
PS:取个位后将n整除10，若n仅为个位数，返回count。

2.中间位

(1) n=k 时
k在此位置上出现的次数，与两个数值相关；
原数字m第i+1位右边的数字的数值；（用数组a十进制加权累加至p中）
第i+1位保持k不变，左边数字减1后的所有组合。
12345为例，取百位，k=3时：第一种为003xx–113xx的组合；第二种为12300–12345的组合；
count += p + 1;
n=n/10;
count += n * pow(10,i);

(2) n>k 时
k在此位置出现的次数，与原数字m相关。
出现的次数为左边数字的组合（左边数字为可能的最大数值，为n/10+1）乘以右边数字的组合（由于n>k，右边数字任意组合，为C(1,10)）
12345为例，取百位，k=2时：003xx–122xx的组合
n=n/10;
count += (n+1) * pow(10,i);

(3) n<k时
k在此位置出现的次数，与原数字m无关。
相关的数字需满足k在此位置出现，且在[0,m]内的最大数值。
从左边借1位后，将此位置为k，则出现的次数为左边数字的组合（左边数字会比最大值小1，为n/10）乘以右边数字的组合（由于借位，右边数字任意组合，为C(1,10)）
12345为例，取百位，k=4时，004xx-114xx的组合
n=n/10
count += npow(10,i)*

3.首位
(1) n=k
首位后所有数字数值+1，即为首位出现k的次数。
count += m - n * pow(10,i)+1;

(2) n>k
首位进1位所需的数值，10^数字长度-1的次方
count += pow(10,i)

(3) n<k时
无

二.特殊条件
(1) n = 0，仅在k=0时输出1;
(2) k = 0，首位无需处理，且中间位为0时，需确保左侧有非0位（计数count减去处理位左侧所有位同时为0的组合），个位为0的特殊情况已在（1）中涉及。所以正常统计后减去所有k左侧同时为0的计数即为0在k位上出现的次数。
n=n/10;
count+=(n-1) * pow(10,i);

三.程序实现

（1）数组a实现对n每一位记录；
（2）数字p实现累加求k右侧数值的功能；
（3）首位处理（补全判断是否需要处理。包含n为个位数和k=0的情况）；
（4）中间数处理（补全对0的操作）；、
（5）个位处理（补全n=0特例）

代码：

    int digitCounts(int k, int n) {
        // write your code here
        int count=0,i=0,m,a[64]={0},p=0;
        m=n;
        if(n==0)                 //n=0的特殊情况
        {
            if(k==0) return 1;
            else return 0;
        }

            a[i]=n % 10;               //个位处理
            if(n % 10 >= k) 
            {
                count += n/10 + 1;
                n = n/10;
            }
            else
            {
                count += n/10;
                n = n/10;
            }
            i++;
            
            if(n==0)  return count;    //n为个位数退出
            
                while(n > 9)  //中间位处理
                {
                    if(n % 10 == k)
                     {
                        if(k!=0)
                        {
                        a[i] = n % 10;
                        p+=a[i-1] * pow(10,i-1);
                        count += p + 1;
                        n=n/10;
                        count += n * pow(10,i);
                        }
                        else
                        {
                        a[i] = n % 10;
                        p+=a[i-1] * pow(10,i-1);
                        count += p + 1;
                        n=n/10;
                        count+=(n-1) * pow(10,i);    
                        }
                    }
                    else if(n % 10 > k)
                    {
                        a[i] = n % 10;
                        p+=a[i-1] * pow(10,i-1);
                        n=n/10;
                        count += (n+1) * pow(10,i);
                    }
                    else
                    {
                        a[i] = n % 10;
                        p+=a[i-1] * pow(10,i-1);
                        n=n/10;
                        count += n * pow(10,i);
                    } 
                    i++;
                }
                if(k==0) return count;//首位处理
                else
                {
                if(n == k)  count += m - n * pow(10,i)+1;    
                else if( n > k)  count += pow(10,i);
                }
            
        return count;
    }
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71