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)

1、Python

1 class Solution:
 2     """
 3     @param: : An integer
 4     @param: : An integer
 5     @return: An integer denote the count of digit k in 1..n
 6     """
 7 
 8     def digitCounts(self, k, n):
 9         # write your code here
10         sum = 0
11         k=str(k)
12         for i in range(n + 1):
13             s = str(i)
14             for j in s:
15                 if(j==k):
16                     sum+=1
17         return sum

2、Java

说明：

设一个整数为abcdef（六位数），current表示当前正在统计的i位上的数字大小（i=10时，current=e i=1000时，current=c）

before为current之前的所有数字，after为current之后的所有数字（current=d时，before=abc,after=ef）

举例：

534898 current=4 before=53 after=898

从个位开始统计。直到统计完所有位。

public class Solution {
     /*
      * @param : An integer
      * @param : 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 current = 0,before = 0,after = 0;  
         int i = 1,count = 0;
         int flag=1;
         while(n/i != 0 || (n==0&&flag==1)){//n=0,k=0特殊情况处理
             if(n==0){
                 flag=0;
             }
             current = (n / i) % 10;  
             before = n / (i * 10);  
             after = n - before * (i * 10) - current * i;
             if(k!=0 || before!=0){
                 if(current > k)  
                     count += (before + 1) * i;  
                 else if(current < k)
                     count += before * i;
                 else
                     count += before * i + after + 1;
             }
             else{
                 if(after!=0)
                     count += 0;
                 else
                     count += 1;
             }
             i *= 10;
         }
         return count;
     }
 };