整数中1出现的次数（从1到n整数中1出现的次数）_31

image.png

两种方法。

1.总结规律

思路:

• 1.对于整数n，我们将这个整数分为三部分：当前位数字cur，更高位数字high，更低位数字low，如：对于n=21034，当位数是十位时，cur=3，high=210，low=4。
• 1. 我们从个位到最高位 依次计算每个位置出现1的次数：
  • 1当前位的数字等于0时，例如n=21034，在百位上的数字cur=0，百位上是1的情况有：00100~00199，01100~01199，……，20100~20199。一共有21*100种情况，即high*100;
  • 2）当前位的数字等于1时，例如n=21034，在千位上的数字cur=1，千位上是1的情况有：01000~01999，11000~11999，21000~21034。一共有2*1000+（34+1）种情况，即high*1000+(low+1)。
  • 3）当前位的数字大于1时，例如n=21034，在十位上的数字cur=3，十位上是1的情况有：00010~00019,00110~00119，……，21010~21019。一共有（210+1）*10种情况，即(high+1)*10。
  • 4)这个方法只需要遍历每个位数，对于整数n，其位数一共有lgn个，所以时间复杂度为O(logn)。

代码：

 public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for (int i = 1; i <=n; i*=10) {
            //更高位的((数字
            int high=n/i*10;
            //更低位数字
            int low=n%i;
            //当前位数字
            int curr=n/i%10;
            if (curr==0){
                count+=high*10;
            }else if (curr==1){
               count+=high*i+(low+1);
            }else {
               count+=(high+1)*i;
            }
        }
        return count;
    }

方法二：

注解：参考一位牛友提到的leetcode的链接网址（包括求1~n的所有整数中2,3,4,5,6,7,8,9出现的所有次数） 通过使用一个 位置乘子m 遍历数字的位置, m 分别为1,10,100,1000…etc.（m<=n）

对于每个位置来说，把10进制数分成两个部分，比如说 当m=100的时候， 把十进制数 n=3141592 分成 a=31415 和 b=92 ，以此来分析百位数为1时所有数的个数和。m=100时，百位数的前缀为3141，当百位数大于1时，为3142*100，因为当百位数大于1时，前缀可以为0，即百位数可以从100到199，共100个数；当百位数不大于1时，为3141*100；如何判断百位数是否大于1？假设百位数为x，若（x+8）/10等于1，则大于1，若（x+8）/10等于0，则小于1。因此前缀可用（n/m + 8）/10 *m来计算(若计算2的个数，可以改为（n/m + 7）/10*m,若计算3的个数，改为（n/m + 6）/10*m，…以此类推)。

再例如m=1000时，n分为a=3141和 b=592；千位数的前缀为314，千位数不大于1，故前缀计算为314*1000；因为千位数为1，再加b+1(0到592)。即千位数为1的所有书的个数和为314*1000+592+1；公式（n/m + 8）/10*m + b +1。

注意：只有n的第m位为1时需要计算后缀，后缀计算为 （n/m%10==1）*(b+1)，另外a+8的巧妙之处在于当a的最后一位(当前分析位)为0或1时，加8不产生进位，这是为需要单独算的特殊情况做准备，而当前分析位为2~9时，不需要考虑特殊情况，所以允许加8产生的进位。

即（n/m%10==1）判断第m位是否为1，若为1，则加上（b+1），若不为1，则只计算前缀。（若计算2的个数，可以改为（n/m%10==2）*(b+1)，若计算3的个数，可以改为（n/m%10==3）*(b+1)…以此类推）

代码：

public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;

        //m为个位， 十位 百位 千位....
        for (long m = 1; m <= n; m *= 10) {
            //n除以基数后的数
            long a = n / m;
            //n在基础上的数
            long b = n % m;
            //a%10表示上一位是否为1，为0?后一位为几就加几:0
            count+=(a+8)/10*m+(a%10==1?b+1:0);
        }
        return count;
    }