3.统计数字

题目要求计算数字k在0到n中的出现的次数，k可能是0~9的一个值。自己的思路是这样的，如果n比k还要小，那肯定没有出现的次数；如果n是在0-9中的某个数，由于已经判断过n比k大，所以肯定出现了一次；如果n是>=10的，就进行逐位判断，具体操作就是取n的个位数进行比较是否等于k，等于就count加1，不等于就取n的十位数再进行判断，直到n所有的位数都已经判断过了为止。这样的算法固然可以也比较容易想到，代码如下:

class Solution {
public:
    /*
     * @param : An integer
     * @param : An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    int digitCounts(int k, int n) {
        // write your code here
        if (n<k) return 0;
        if (n<10 && n>k)  return 1;
        int count=1;
        for(int i=10;i<n+1;i++)     //弄了半天，才发现一直写的是<n，没有包括n这个项
         {
             int num=i;
             while(num!=0)
              {
                  int a=num%10;
                  if(a==k) count++;
                  num=num/10;
              }
            
         }
        return count;
    }
};

还看到了大神关于此题思路，思路如下：假如我们现在要求从1到一个5位数ABCDE之间，出现了2的数次是多少。我们现在把问题简单化，只考虑从0到ABCDE之间在百位（C）上出现2的次数，然后用在个位，十位，千位，万位上也适用，就可以算出总的。

第一种情况：当给出的五位数ABCDE中百位上的C是小于数字2的时候：

1.比如说，百位上是0，假如给定的五位数是12031，那么0到12031之间有哪一些数的百位上会出现2，从小到大数，200-299,1200-1299,2200-2299,3200-3299...,10200-10299,11200-11299.我们会发现后面三位是固定的，变化的只有比百位更高的位，高位从0（0代表200-299）到11，总共12个，再变大就超过了，因为百位上的数字是小于给定数字2的。那么我们发现当百位上是0的时候，百位上出现2的次数由更高的位决定，等于更高的位（12）X当前的位数100=1200个。

2.当百位上是1的时候，假设给定的五位数是12131，那么求出来的结果和百位上是0的一样，所以从1到ABCDE所有数字中，百位上出现2的次数也是1200.

第二种情况，也就是当给定的五位数ABCDE百位上的C刚好等我我们要求的次数的那个数字2

假如现在给定了一个12213，那么我们还是有200-299,1200-1299,2200-2299,3200-3299...,10200-10299,11200-11299这1200个，但是除了这些，还有一部分12200-12213（由低位数字+1），所以，当某一位的数字等于2的时候，*百位上出现2的次数=更高位的数字x当前的位数+低位的数字+1；

第三种情况，当百位上的数字大于2的时候

假如说12313，那么这次除了200-299,1200-1299,2200-2299,3200-3299...,10200-10299,11200-11299，还包含了12200-12299，也没有低位的事情计算百位上出现2的次数是：（更高的位数+1）x当前的位数。

总结以下规律，我们要从1到ABCDE中找到k这个数字在某一位上出现了多少次：
当某一位的数字小于k时，那么该位出现i的次数为：更高位数字x当前位数
当某一位的数字等于k时，那么该位出现i的次数为：更高位数字x当前位数+低位数字+1
当某一位的数字大于k时，那么该位出现i的次数为：(更高位数字+1)x当前位数

代码如下：

    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) {  
            if(n == 0 && k == 0)  
                return 1; // 特殊情况  
            int temp = n, cnt = 0, pow = 1;//pow代表当前位的后面低位是多少，1为个位，10为十位，100位千位  
            while(temp != 0) {  
                int digit = temp % 10; // 根据当前位置数和k的大小关系，可以算出当前位置出现过k的次数  
                if(digit < k)  
                    cnt += (temp / 10) * pow;  
                else if(digit == k)  
                    cnt += (temp / 10) * pow + (n - temp * pow + 1);  
                else {  
                if(!(k == 0 && temp / 10 == 0)) // 排除没有更高位时，寻找的数为0的情况  
                    cnt += (temp / 10 + 1) * pow;  
                }  
                temp /= 10;  
                pow *= 10;  
            }  
            return cnt;  
        }  
    };