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

题目描述：

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

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

样例

输入： 12
输出： 5

分析：

直接枚举n个数，复杂度太高。现在比如51023，对于第一个数5 > 1，若最高位是1，有10000-19999共10000种情况；第二个数就是1，左边数是0-4时，右边可以是000-999，左边数为5时，右边数是000-023，一共5*1000+24=5024种情况；第三个数为0，要使它为1，左边可以是0-50，右边可以是0-99，共5100种情况；第四个数是2，当其为1时，左边可以是0-510，右边可以是0-9，一共5100种情况；第五个数是3，当其为1，左边的数可以是0-5102，共5103种情况。1一共出现了30337次。

通过上例可以发现，我们考察某数n=abcde时，比如考察c这一位，如果c大于1，则左边可以是0-ab，右边可以是0-99；如果c等于1，左边是0-ab-1时，右边可以是0-99，左边是ab时，右边可以是0-de；如果c等于0，则左边可以是0-ab-1，右边可以是0-99。所以我们需要求出每一位左边和右边的数是什么以及当前位的权值。

所以很容易得到以下程序：

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if(!n)  return 0;
        vector<int> num;
        while(n)    num.push_back(n % 10),n /= 10;
        int ans = 0;
        for(int i = num.size() - 1;i >= 0;i--){
            int l = 0,r = 0,t = 1;
            for(int j = num.size() - 1;j > i;j--)   l = l * 10 + num[j];
            for(int j = i - 1;j >= 0;j--)   r = r * 10 + num[j],t *= 10;
            ans += l * t;
            if(num[i] == 1) ans += r + 1;
            else if(num[i] > 1) ans += t;
        }
        return ans;
    }
};