【剑指offer】从1到n整数中1出现的次数（查找）

（*****）
题目描述：
求出1-13的整数中1出现的次数,并算出100_{1300的整数中1出现的次数？为此他特别数了一下1}13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
（
输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

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

样例
输入： 12
输出： 5
）

---

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        //13  6
        //left  i  right
        //i 1  left * 10^i + right + 1
        //i 0  left *10^i +10^i
        if(!n) return 0;
        //n >= 1
        vector<int> num;
        while(n)
        {
            num.push_back(n % 10);
            n /= 10;
        }
        int res = 0;
        for(int i = num.size() - 1; i >= 0; i --)
        {
            int left = 0, right = 0, x = 1;
            //高位到低位left
            for(int j = num.size() - 1; j > i; j --)
                left = left * 10 + num[j];
            //计算低位right
            for(int k = i - 1; k >= 0; k --)
            {
                right = right * 10 + num[k];
                x *= 10;
            }
            //计算位数
            res = res + left * x;
            if(num[i] == 1) res += right + 1;
            else if(num[i] > 1) res += x;
        }
        return res;
    }
};