转自http://blog.csdn.net/kkdd2013/article/details/51882774 并处理了出现0的情况
题目描述：
计算数字k在0到n中的出现的次数，k可能是0~9的一个值
例如n=12，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]中，我们发现1出现了5次 (1, 10, 11, 12)
思路一：我们可以用最简单的办法先尝试一下，遍历1到n中间的每个整数，对每个整数从低位到高位依次检查，如果有k出现则计数器自加。
思路一最大的问题就是效率，当n非常大时，就需要很长的运行时间。想要提高效率，就要避开暴力法，从数字中找出规律。
思路二：来自《编程之美》
假设有一个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位为200299，然后高位依次从0到11，共12个。再往下1220012299 已经大于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, … , 1120011299这1200个数，他们的百位为2。但同时，还有一部分1220012213，共14个(低位数字+1)。所以，当百位数字为2时，百位出现2的次数既受高位影响也受低位影响，结论如下：
—>当某一位的数字等于2时，那么该位出现2的次数为：更高位数字x当前位数+低位数字+1
第三种情况：当百位上的数C大于2时：
当百位C大于2时，比如说12313，那么固定低3位为200299，高位依次可以从0到12，这一次就把1220012299也包含了，同时也没低位什么事情。因此出现2的次数是： (更高位数字+1)x当前位数。结论如下：
—>当某一位的数字大于2时，那么该位出现2的次数为：(更高位数字+1)x当前位数
通过上述分析，我们可以得到以下规律：
- 当某一位的数字小于i时，那么该位出现i的次数为：更高位数字x当前位数
- 当某一位的数字等于i时，那么该位出现i的次数为：更高位数字x当前位数+低位数字+1
- 当某一位的数字大于i时，那么该位出现i的次数为：(更高位数字+1)x当前位数
public static int digitCounts(int k, int n) {
int result = 0;
int base = 1; //位, 个位/十位/百位
if (k == 0 && n == 0) {
return 1;
}
while (n / base > 0) {
int cur = (n / base) % 10;
int low = n - (n/base) * base;
int hight = n / (base * 10);
if (k == 0 && cur > k){
if (hight != 0) {
result += hight + 1;
} else {
result += hight;
}
} else if (cur == k){
result += hight * base + low + 1;
} else if (cur < k ){
result += hight * base;
} else {
result += (hight + 1) * base;
}
base *= 10;
}
return result;
}
