题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

暴力法，遍历从1道n的数，对每个数字计算1的个数。
时间复杂度O(nlogn)，空间复杂度O(1)。

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

在别人的做法中看到时间复杂度为O(logn)，空间复杂度为O(1)的做法。
这种做法的思想还是需要花点时间去理解的(对我来说)，我将核心逻辑的注释写在下面的代码中，多少能帮助理解。

在写下面代码时被取模运算迷惑了，算是十分低级的基础不牢。任何数对1取模必然为0，因为任何数除以1都不会产生余数，而一个数对比他大的数取模则等于他自身。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int base = 1;//当前位数, 从个位开始
        int count = 0;
        while(n / base){
            int cur = n / base % 10;//当前位数处的值
            int higher = n / base / 10;//cur左侧数
            int lower = n % base;//cur右侧数
            if(cur == 1){//当该位为1时, 要么左侧数保持不变, 右侧数可产生lower+1个数, 要么左侧数取0~higher, 则可以借位给右侧数, 右侧数取0~base-1
                count += higher * base + lower + 1;
            }
            else if(cur == 0){//当该位为0时, 必须向左侧数借位, 左侧数取0~higher-1, 右侧数取0~base-1
                count += higher * base;
            }
            else{//当该位大于1时, 可以在不向左侧数借位的情况下借位给右侧数
                count += (higher + 1) * base;
            }
            base *= 10;
        }
        return count;
    }
};