Digit Counts 3

Question

Count the number of k's between 0 and n. k can be 0 - 9.

Example

if n = 12, k = 1 in

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

we have FIVE 1's (1, 10, 11, 12)

Solution

方法一: Brute Force, 0到n个数挨个算过去。最大的问题就是效率,当n非常大时,就需要很长的运行时间。

方法二:参考http://www.hawstein.com/posts/20.4.html分析一下会发现有如下结论

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

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

当百位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个。

当百位c为1时,比如说12113。分析同上,并且和上面的情况一模一样。 最大也只能到11200~11299,所以百位出现2的次数也是1200个。

上面两步综合起来,可以得到以下结论:

当某一位的数字小于2时,那么该位出现2的次数为:更高位数字x当前位数 当百位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时,比如说12313,那么固定低3位为200~299,高位依次可以从0到12, 这一次就把12200~12299也包含了,同时也没低位什么事情。因此出现2的次数是: (更高位数字+1)x当前位数。结论如下:

当某一位的数字大于2时,那么该位出现2的次数为:(更高位数字+1)x当前位数

注意:当k为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
        if(k < 0 || k > 9){
            return 0;
        }

        if(n < 0 || k > n){
            return 0;
        }

        //brute force
        // int count = 0;
        // for(int i = 0; i <= n; i++){
        //     if(i == k){
        //         count++;
        //         continue;
        //     }

        //     int curt = i;
        //     while(curt != 0){
        //         if(curt % 10 == k){
        //             count++;
        //         }
        //         curt /= 10;
        //     }
        // }
        // return count;

        //analytic version
        int result = 0;
        int base = 1;
        while (n/base > 0) {
            //当前位
            int cur = (n/base)%10;
            //低位
            int low = n - (n/base) * base;
            //高位
            int high = n/(base * 10);

            if (cur == k) {
                //考虑k=0时的特殊情况
                if(k == 0){
                    result += (high - 1) * base + low + 1;
                }else{
                    result += high * base + low + 1;
                }
            } else if (cur < k) {
                result += high * base;
            } else {
                //考虑k=0时的特殊情况
                if(k == 0){
                    result += high * base; 
                }else{
                    result += (high + 1) * base;
                }
            }
            base *= 10;
        }
        //当k!=0时,都是从最高位数值等于k时开始数起,k=2时从百位为2即200开始数起;但是当k为0时,开始的最高位不能为0,所以上面的方法都是从高一位为1开始数的,因此在考察个位的情况时,没有考虑个位数是0但是没有高位(即就是数字0)的合法情况,所以要+1
        return k == 0? result + 1 : result;
    }
};

results matching ""

    No results matching ""