【lintcode】统计数字问题

描述
计算数字 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;
    }
}

上一篇:基于OpenCV+ZXing手工打造,FPS300+的二维码识别库


下一篇:lintcode 382. 三角形计数【双指针】