Digit Counts

Description

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

Example

# Example1

Input:
k = 1, n = 1
Output:
1
Explanation:
In [0, 1], we found that 1 appeared once (1).

# Example2

Input:
k = 1, n = 12
Output:
5
Explanation:
In [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we found that one appeared five times (1, 10, 11, 12)(Note that there are two 1 in 11).

Solution

/*
统计所有数字每一位包含k的个数。
通过观察可知，每10个数包含一个在个位的k，每100个数包含10个在十位的k，1000个包含100个在百位的k，以此类推。
直接/10/100...去统计，最后补充剩下的不足10（100/1000）个数中的k
*/

public int counts(int k, int n){
    int count=0;
    if(n<10) return 1;
    
    
    int base = 1;  //基，表示个位/十位/百位/...
    
    /*
    * 分别统计每一位包含k的个数：基础个数加上补充个数
    * 基础个数：通过观察可知，每10个数包含一个在个位的k，每100个数包含10个在十位的k，以此类推
    * 补充个数：最后剩下的不足10（100/1000）个数中也包含k
    */
    while(n/base>0){
        int x = n/base; //末位为当前位
        int high = x/10;  //末位为高位
        
        if (k == 0) { //如果k=0, 由于最高位不为0，因此删去少一位的那些统计数
            if (high>0) high--;
            else {
                count++;
                break;
            }
        }
        count+=high*base;  //当前位k的基本个数等于高位*基
        
        int r = x % 10;    //当前位的值
        if(r>k) count+=base;  //如果大于k，则补充个数与高一位一样包含整个基
        else if(r==k) count+=n-x*base+1; //如果等于k，则补充个数相当于当前位后面几位的值+1
        base = base*10;   
    }
    return count;
}

python 一行搞定,把数当做字符串拼接起来,然后数个数

def digitCounts(k, n):
# write your code here
    return ''.join(map(str,range(n+1))).count(str(k))