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

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        //if(n==0) return 0;
        //if(n<10) return 1;
        vector<int> eachPos;
        int curTen = 1, res = 0, lastSum = 0, cnt = 0;
        while(n>0){
            ++cnt;
            int temp = n%10;
            if(temp==1)
                res += lastSum+1;
            else if(temp>1) res += curTen;
            res += (curTen/10)*(cnt-1)*temp;
            lastSum += curTen*temp;
            curTen *= 10;
            n /= 10;
        }
        return res;
    }
};

我的思路是解决每一个位置上面的1的个数，两个判断条件就是看当前位置为1能有多少种。

然后加上除了后面冒出来的部分，这个位的完整底下还有多少个1。

每进一位，之前的部分都是算的冒起来的部分。

初始可以假装有小数的部分，结果为0，这样就把0和一个位的也考虑进去了。

时间复杂度是O(logn)，空间复杂度是O(1)。