3. 统计数字(lintcode)

题目：

计算数字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)

思路：

    对于数字n，k的出现次数 = 当n的个(十百千万...)位为2其他位数的全排列数量的总和.例如数字为n=302,k=2那么 在n中k出现的次数 = 2**全排列数量 + *2*全排列数量 + **2全排列数量,

    对于n中个十百千万...任一位数 = k时的全排列数量数量可以分开两部分统计，高位-1 和 高位保持不变两种情况统计。高位-1则当前位必然可以选为 k 且 低位可以0-9任选，所以:

    高位-1时当前位选k的全排列数量=(高位-1 + 1)*10^低位的数量。

    对于n=33022,k=2，当前位为百时 高位-1时当前位选k的全排列数量 = (33 - 1 + 1) * 10 ^ 2。(高位可选范围0-32，低位可选范围0-99)

对于高位保持不变部分的统计分三种情况:

    当前位 > k :

    低位可以0-9任选，所以数量 = 10^低位数量

    例如对于33322百位的统计,低位可选范围0-99,保持高位不变的数量 = 10^2

    当前位 = k :

    低位可以0-原数据最大值任选，所以数量 = 低位原数据 + 1

    例如对于33322百位的统计,低位可选范围0-22,保持高位不变的数量 = 22 + 1

    当前位 < k :

    当前为高位保持不变时不能选k，所以数量 = 0

代码:

public int digitCounts(int k, int n) {
    //特殊情况
    if(k == 0 && n == 0){
        return 1;
    }
    
    int count = 0;
    //获取的数字是和n一样长的1000....的数字，方便做除数获得当前位的数字，以及统计10^低位长度
    //假如n=33022,那么zeros = 10000
    int zeros = getZeros(n);
    //获取头位数 33022/10000 = 3
    int quotient = n / zeros;

    //最大位的统计,当k=0不用统计头位数
    //对于33022，选头位为0时，03022 = 3022,0消失
    if(k != 0){ 
        //当头位数 > k
        if(quotient > k){
            count += zeros;
        //当头位数 == k
        }else if(quotient == k){
            count += n%zeros + 1;
        }
    }
    //开始统计下一位数
    zeros /= 10;

    //循环统计除头位数以外的位数
    while (zeros > 0){
        //获取高位数
        quotient = n / zeros;
        //高位-1时当前位选k的全排列数量=(高位-1 + 1)*10^低位的数量
        count += quotient/10 * zeros;
        //高位保持不变的统计
        if(quotient % 10 > k){
            count += zeros;
        }else if(quotient % 10 == k){
            count += n % zeros + 1;
        }
        zeros /= 10;
    }

    return count;
}

private int getZeros(int n){
    int r = 1;
    while (n >= 10){
        r *= 10;
        n /= 10;
    }
    return r;
}

代码优化:

上面的代码是从头位统计到尾位.我们可以从头位统计到尾位统计到头位可以去掉getZeros的操作

public int digitCounts(int k, int n) {
    if (k == 0 && n == 0) {
        return 1;
    }

    int count = 0,zeros = 1,quotient,t = n / 10;

    while (zeros <= t) {
        quotient = n / zeros;
        count += quotient / 10 * zeros;
        if (quotient % 10 > k) {
            count += zeros;
        } else if (quotient % 10 == k) {
            count += n % zeros + 1;
        }
        zeros *= 10;
        //System.out.println(count);
    }

    quotient = n / zeros;
    if (k != 0) {
        if (quotient > k) {
            count += zeros;
        } else if (quotient == k) {
            count += n % zeros + 1;
        }
    }

    //System.out.println(count);

    return count;
}v