描述
计算数字 k 在 0 到 n 中的出现的次数,k 可能是 0~9 的一个值。
样例
样例 1:
输入:
k = 1, n = 1
输出:
1
解释:
在 [0, 1] 中,我们发现 1 出现了 1 次 (1)。
样例 2:
输入:
k = 1, n = 12
输出:
5
解释:
在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 中,我们发现 1 出现了 5 次 (1, 10, 11, 12)(注意11中有两个1)。
思想:按位分析,从个位开始一位位分析,最后计算每个位中K出现次数的和
对个位进行分析:
例1:n=723, k=1 即((n%10)>k)
个位:个位出现1的情况为001,011,021…711,721
出现的个数为:73次 即n/10+1
例2: n=723,k=3 即((n%10)==k)
个位:个位出现3的情况为003,013,023…713,723
出现的个数为:73次 即n/10+1
例3:n=723,k=5 即((n%10)<k)
个位:个位出现5的情况为005,015,025…715
出现的个数为:72次 即n/10
对十位进行分析:
例1:n=723,k=1 即(((n/10)%10)>k)
十位:十位出现1的情况为010019,110029…610619,710719出现的个数为:80次
即(n/10/10+1)10
例2:n=723,k=2 即(((n/10)%10)==k)
十位:十位出现2的情况为020029,020029…620629,720723出现的次数是710+4=74
即(n/10/10)10+n%10+1
例3:n=723,k=3 即(((n/10)%10)<k)
十位:十位出现1的情况为030039,130139…630~639出现的次数是710=70次
即(n/10/10)*10
Java代码如下:
public class Solution {
/**
* @param k: An integer
* @param n: 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
int count=0;
for(int i = 0;i<= n;i++){
int num = i;
while(num/10 !=0){
if(num%10==k){
count++;
}
num=num/10;
}
if(num == k)
count++;
}
return count;
}
}