计算数字 k 在 0 至 n 范围内出现的次数

样例 1：

输入： k = 1, n = 1
输出： 1
解释： 在 [0, 1] 中，我们发现 1 出现了 1 次 (1)。

样例 2：

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

3.思路

• 计算出每一位上出现的次数然后累加求和；
• 对于个位出现的次数乘1，十位出现的次数乘10，百位乘100，依次类推；
• 对于k等于0分两种情况讨论；
• 对于k等于0且n小于10时直接输出1；
• 对于k对于0且n大于10时由于最高位不可能出现0所以最后结果要减去最高位的次数；

4.具体情况分析

来自《编程之美》 ：

假设有一个5位数N=ABCDE，我们现在来考虑百位上出现2的次数，即：从0到ABCDE的数中，有多少个数的百位上是2。分析完它，就可以用同样的方法去计算个位，十位，千位，万位等各个位上出现2的次数。 

第一种情况：当百位上的数C小于2时：

1）当百位c为0时，比如说12013，0到12013中哪些数的百位会出现2？我们从小的数起， 200~299, 1200~1299, 2200~2299, … , 11200~11299, 也就是固定低3位为200~299，然后高位依次从0到11，共12个。再往下12200~12299 已经大于12013，因此不再往下。所以，当百位为0时，百位出现2的次数只由更高位决定，等于更高位数字(12)x当前位数(100)=1200个。
2）当百位C为1时，比如说12113。分析同上，并且和上面的情况一模一样。最大也只能到11200~11299，所以百位出现2的次数也是1200个。

上面两步综合起来，可以得到以下结论：
　　—>当某一位的数字小于2时，那么该位出现2的次数为：更高位数字x当前位数

第二种情况：当百位上的数C等于2时：

当百位C为2时，比如说12213。那么，我们还是有200~299, 1200~1299, 2200~2299, … , 11200~11299这1200个数，他们的百位为2。但同时，还有一部分12200~12213，共14个(低位数字+1)。所以，当百位数字为2时，百位出现2的次数既受高位影响也受低位影响，结论如下：
—>当某一位的数字等于2时，那么该位出现2的次数为：更高位数字x当前位数+低位数字+1

第三种情况：当百位上的数C大于2时：
当百位C大于2时，比如说12313，那么固定低3位为200~299，高位依次可以从0到12，这一次就把12200~12299也包含了，同时也没低位什么事情。因此出现2的次数是： (更高位数字+1)x当前位数。结论如下：
—>当某一位的数字大于2时，那么该位出现2的次数为：(更高位数字+1)x当前位数

通过上述分析，我们可以得到以下规律：

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

5.代码展示

 1 #include <iostream>
 2 using namespace std;
 3 
 4 //计算数字 k 在 0 到 n 中的出现的次数，k 可能是 0~9 的一个值。
 5 class Solution{
 6 public:
 7     int digtCounts(int k, int n){
 8         int i = 1;
 9         int count = 0;
10         int current, high, low;
11         while(n / i != 0){
12             current = n / i % 10;    //记录当前位大小 
13             high = n / (i*10);        //记录高位大小 
14             low = n - n / i * i;    //记录低位大小 
15             if(current < k)
16                 count += high * i;
17             if(k == current)
18                 count += high * i + low + 1;
19             if(current > k)
20                 count += (high + 1) * i;
21             i *= 10; 
22         } 
23         
24         //特殊情況 
25         if(k == 0 && n < 10){
26             return 1;
27         }
28         if(k == 0 && n >= 10)
29             count -= i / 10;
30             
31         return count;
32     }
33 }; 
34 
35 
36 int main(){
37     int k, n;
38     Solution s;
39     cin >> k >> n;
40     cout << s.digtCounts(k, n) << endl;
41     return 0;    
42 }