要求：计算数字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;
}
};
