剑指offer 44- 从1到n整数中1出现的次数

输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1出现的次数。

例如输入 12，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，11 和 12，其中 “1” 一共出现了 5次。
样例

输入： 12
输出： 5

分析：
算法一：
暴力枚举

假如存在abcdef这样一个数：
当枚举到i=2，即number[i] = c时：
_ _ c_ _ _
（1）c左边：00-ab-1；c右边：000-999 此时：共ab*1000个“1”
（2）00-ab-1算完了，开始算ab这一种，即abc_ _ _
当c=0时，0个1
当c=1时，000-def，共def+1个“1”
当c>1时，000-999，共1000个1
时间复杂度：
数字n共有，时间复杂度为：

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if(!n) return 0;
        int res = 0;
        vector<int> number;//把n的每一位存到数组中（高位在右边）
        while(n) number.push_back(n%10), n/=10;//把n的每一位存到数组中
        for(int i = number.size()-1; i>=0; i--) {
            //比如abcdef，此时number[i]=c,则left=ab，right=def，t记录right是几位数
            int left = 0, right = 0, t = 1;
            for(int j = number.size()-1;j>i;j--) left = left*10 + number[j];
            for(int j = i-1;j>=0;j--) right = right*10 + number[j], t*=10;
            //比如abcdef，此时number[i]=c,则c左边：00-ab-1，右边：000-999，总共ab*1000个“1”
            res += left * t;
            //00-ab-1算完了，开始算ab这一种，即abc_ _ _
            //当c=0时，0个1
            //当c=1时，000-def，共def+1个“1”
            //当c>1时，000-999，共1000个1
            if(number[i] == 1) res += right+1;
            else if(number[i] > 1) res += t;
        }
        return res;
    }
};

算法二：

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if(!n) return 0;
        int res = 0, left = n, right = 0, t=1, x;
        while(left) {
          x = left % 10, left /= 10;
          res += left * t;
          if (x > 1) res += t;
          else if (x == 1) res += right + 1;
          right += x * t, t *= 10;
        }
        return res;
    }
};