Solution3.java

package com.lintcode;

/**
 * 3. 统计数字
 * 计算数字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)
 *
 */

public class Solution3 {

    /*
     * @param : An integer
     * @param : An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    public int digitCounts(int k, int n) {
        // write your code here
        if(n == 0 && k == 0)
            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;
    }
}