从 1 到 n 整数中 1 出现的次数

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        vector<int> q;
        do
        {
            q.push_back(n%10);
            n/=10;
        }while(n);
        int res=0;
        for (int i = q.size()-1; i >=0 ; i -- )//从最高位开始
        {
            int left=0,right=0,t=1;
            for (int j = q.size()-1; j > i; j -- )   left=left*10+q[j];
            for (int j = i-1; j >= 0; j -- )    right=right*10+q[j],t=t*10;
            res+=left*t;//前两位小于ab时
            //前两位取ab时
            if(q[i]==1) res+=right+1;
            else if(q[i]>1) res+=t;
        }
        return res;
    }
};