43. 1～n 整数中 1 出现的次数

1. 描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次

2. 例子

示例 1:
输入：n = 12
输出：5

示例 2:
输入：n = 13
输出：6

3. 限制

• 1 <= n < $2^{31}$

4. 题解

时间复杂度: O($log_{10}n$)
空间复杂度: O(1)

为了快速解题，肯定是要找规律
为了找到数字 1 出现的规律，我们随便找一个数字来分析一下，以数字 12045 为例，个位数过于特殊，我们来分析十位数
12045 中的十位数是 4，十位数 1 可能出现的地方是其左边 12000 以及其十分位自身 45
左边 12000 中出现的十分位数字非常容易理解，十分位数字可能出现的地方是 10~19，共十个数字，而这一循环每 100 个数字出现一次，所以左边 12000 中出现十分位数字 1 的次数一共是 12000 / 100 * 10
45 出现十分位数字 1 的情况需要讨论，如果出现的数字是 09 呢？根本没有十分位没有什么好说的，如果是 15 呢？那就是 10~15 共 6 个数字，如果是 45 呢？45 又怎么样，19 之后的数字都是一样的，反正最多贡献 10 个十分位数字。所以再来看下我们的分界线，是 10 和 20，10 的由来是因为十分位，如果是百分位，那分界线自然是 100。

class Solution 
{
public:
    int countDigitOne(int n)
    {
        int digitOneCount = 0;
        for(long base = 1; base <= n; base *= 10)
        {
            long divider = base * 10;
            int leftOneDigit = n / divider * base;
            
            int basePositionNumber = n % divider;
            int currentOneDigit = (basePositionNumber < base ? 0 : min(base, basePositionNumber - base + 1));
            
            digitOneCount += leftOneDigit + currentOneDigit;
        }
        
        return digitOneCount;
    }
};