31.整数中1出现的次数（从1到n整数中1出现的次数）.md

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

题目描述

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

 

解题思路

• 思路一，笨办法，每个数依次判断。判断一个数字中有几个1可以通过不停和10取余数即n%10，判断余数是不是1，然后再把这个数除以10，再和10取余数，一直到这个数为0为止.

• 思路二，牛逼的方法，分别计算每一位上1出现的次数，通过仔细分析，总结规律。来自牛客咩咩jiang用户的题解，但是写的稍微有点错误，我这里改正了，思路如下：

  让i分别等于1,10,100,1000...即表示现在计算的是哪一位上1出现的次数，这样可以把数n分为两个部分，比如n=31456，计算百位上1出现的次数时，i=100，让a = n/i, b=n%i，那么a=314, b=56，就把整个数分为了两个部分，a%10就得到了当前数字n在百位上的数，也就是4，接下来再根据这一位的大小计算在这一位上会出现多少个1，以百位为例子（即i=100）：

  • 这一位上的数大于等于2时，即a%10>=2，比如n=31456，计算百位时，a=314, b=56，百位前面的数每变化一次，百位上就会有个1，这里是0-31即总共32次，公式为a/10+1，而百位每次为1时，都会有100个数字百位为1（100-199），所以得到某一位上的数字大于等于2时，这一位为1的数字的数量为(a/10+1)*i；
  • 这一位上的数字为1时，即a%10==1，比如n=31156，计算百位时，a=311, b=56，还是上面的规律，百位前面的数每变化一次，百位上就会有个1，这里是0-31即32次，公式为a/10+1，但是最后一次百位为1的时候，后面的数字只到56，即不满100个，只有57个（0-56），所以得到某一位上的数字等于1时，这一位为1的数字的数量为(a/10)*i+b+1；
  • 这一位上的数字为0时，即a%10==0，比如n=31156，计算百位时，a=310, b=56，这一位为1的数字的数量为(a/10)*i；

  用for循环让i每次乘以10，对每一位都按上面的公式计算，就能得到所有1的数量，接下来考虑对上面的三个公式进行合并。三个公式的前面都是(a/10+1)*i或者(a/10)*i，唯一不同的就是这一位的数大于等于2（即a%10>=2）的时候要多一个+1，这时候可以考虑给a加上一个数x，使得这一位的数大于等于2时，(a+x)/10==a/10+1，也就是要进位，而这一位的书等于1或者0的时候，(a+x)/10==a/10，也就是加了以后不会造成进位，显然，x=8，因此上面三个公式统一成：(a+8)/10*i + (a%10==1)*(b+1)。

 

代码

• 思路一，笨办法，递归。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {    
        if(n<1) return 0;
        if(n<10) return 1;
        int lastResult = NumberOf1Between1AndN_Solution(n-1);
        int num = 0;
        while(n){
            if(n%10==1) num++;
            n /= 10;
        }
        return lastResult + num;
    }
};

• 思路一，笨办法，迭代。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {    
        if(n<1) return 0;
        if(n<10) return 1;
        int result = 1;
        for(int i=10;i<=n;i++){
            int temp = i;
            int num = 0;
            while(temp){
                if(temp%10==1) num++;
                temp /= 10;
            }
            result += num;
        }
        return result;
    }
};

• 思路二，分别计算每一位上出现1的次数

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {    
        if(n<1) return 0;
        if(n<10) return 1;
        int result = 0;
        for(int i=1; i<=n; i*=10){
            int a = n/i;
            int b = n%i;
            result += (a+8)/10*i+(a%10==1)*(b+1);
        }
        return result;
    }
};