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

  输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
  例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

数据范围：1≤n≤30000

进阶：空间复杂度 O(1)，时间复杂度 O(lognn)

输入：
13
返回值：
6

输入：
0
返回值：
0

暴力穷举

class Solution {
public:
    //求某个整数1出现的次数
    int Numbers1(int n)
    {
        int count = 0;
        while(n != 0)
        {
            if(n % 10 == 1)
                count++;
            n /= 10;
        }
        return count;
    }
    
    int NumberOf1Between1AndN_Solution(int n) {
        int sum = 0;
        for(int i = 1;i <= n;i++)
            sum += Numbers1(i);
        return sum;
    }
};

参考至：【牛客网-摸鱼学大师】

按位统计法

具体做法：

对于每个数字统计1出现的次数太复杂了，我们可以考虑每次直接计算1到n的数字中某位上面的1出现了多少次。

假设我们要计算百位上总共有多少1：首先100-199有100个1，而1100-1199又出现了100个1，于是我们知道了每过1000个数字就会出现100个百位上的1，于是我们就有[n/1000] * 100，细分讨论一下就是：

• 当n%1000<100，百位上不会出现1；
• 当100<=n%1000<200，百位上出现的1有n%1000−100+1次
• 当n%1000>=200，百位上的1一共100次

于是我们就可以得到计算公式每一位的计算公式：

[n/10ⁱ⁺¹] * 10ⁱ + min(max(n%10ⁱ⁺¹ - 10ⁱ + 1,0),10ⁱ)

公式中10ⁱ就表示某一位，而前半部分是表示完整在循环中的，后半部分表示部分出现需要讨论的。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        long long MulBase = 1;//MulBase = 10^i
        for(int i = 0; MulBase <= n; i++){ //每位数按照公式计算
            res += (n / (MulBase * 10)) * MulBase + min(max(n % (MulBase * 10) - MulBase + 1, (long long)0), MulBase);
            MulBase *= 10; //扩大一位数
        }
        return res;
    }
};