剑指Offer 32 从1到n整数中1出现的次数

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

思路

暴力法，你可以对每一个数的每一位检查一下是否有1；
暴力法，变成字符串，检查‘1’的个数；
数学规律法

核心思路：

1.分别判断每一位上1出现过的次数，从个位往高位递推；


2.对于当前处理的位，需要根据其值是0,1，还是>1 对应有不同的处理。


    例如，假设当前考虑百位：


    (1 )如果百位>1,那么百位上1的次数 = (n/100 + 1) * 100;由高位和低位共同决定


    (2)如果百位=1，那么百位上1的数次 = (n/100) * 100 + (n%100 + 1)；由高位和低位共同决定


    (3)如果百位<1，那么百位上1的次数 = (n/100) * 100;由高位决定。

代码

static   public int NumberOf1Between1AndN_Solution(int n) {
          int a=0;
      for (int i = 0; i <=n; i++) {
          int number = 0 ;
          int j = i;
          while (j>0)
          {
              if ( (j % 10) ==1)
                  number++;
                  j=j/10;
          }
          a+=number;
      }
          return  a;
    }
    static   public int NumberOf1Between1AndN_Solution1(int n) {
        int temp = n ;                  //temp 复制一个n的备份
        int timeof1=0;
        int current;
        int power = 0;
        while (n>0)
        {
           current = n%10;
            n/=10;
            if (current>1)
                timeof1+= (n+1)*Math.pow(10,power);
            else  if (current==1)
                timeof1+= (n)*Math.pow(10,power) +temp%Math.pow(10,power)+1;
            else
                timeof1+= n*Math.pow(10,power);
            power++;
        }
        return  timeof1;
    }
        static  public  int NumberOf1Between1AndN_Solution2(int n)
    {
        int ones = 0;
        for (long m = 1; m <= n; m *= 10)
            ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
        return ones;
    }

收获

显而易见的方法，往往不是面试官想要的
努力啊，leetcode的题什么时候才能开始做呢
（n+8）/10，如果n>= 2 就会产生进位，很神奇；

2017-03-31