题目
输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12，从1到12这些整数中包含“1”的数字有1，10，11和12，其中“1”一共出现了5次。
样例
输入： 12
输出： 5

解法：找规律

记第i个位置左边的数大小为left，右边的数大小为right，第i位对应的大小为10^i
那么对于第i个位置中1出现的次数

• 首先它的左边从0~left-1共left*10^i次第i个位置为1
• 然后考虑左边恰好等于left的情况
  • 如果第i个位置为0，不会再出现1
  • 如果第i个位置恰好为1，那么右边从0~right共right+1次出现
  • 如果第i个位置大于1，那么右边包含从0~999…也就是10^i次出现

时间复杂度O()，空间复杂度O(1)
也可以将left, right和t的值预处理出来，这样时间复杂度降为O(logn)

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        vector<int> a;
        while (n) a.push_back(n % 10), n /= 10;
        int ans = 0;
        for (int i = a.size() - 1; i >= 0; i--) {
            int left = 0, right = 0, t = 1;
            for (int j = a.size() - 1; j > i; j--) left = left * 10 + a[j];
            for (int j = i - 1; j >= 0; j--) right = right * 10 + a[j], t *= 10;
            ans += t * left;
            if (a[i] == 1) ans += right + 1;
            else if (a[i] > 1) ans += t;
            // cout << i << ' ' << left << ' ' << right << ' ' << t << endl;
        }
        return ans;
    }
};