题解 | #整数中1出现的次数#

想想时间复杂度更加优秀的算法: 可以对每一位 分别进行计算，下面以 一个六位数：abcdef为例：对于任意一位，比如c: 只要c不为0，则将c认为是1，则此时的个数为：
:one: 前面的ab 则可以是符合条件的数字，对于 00~ab-1 的情况下，后面三位def 就可以是任何数，只要在 000~999 范围内都可，因为 前面的ab 一定是满足条件的，所以此情况下 1的个数就是: ab*1000 个
:two: 前面的ab 就取 ab,则有可以分为三种情况了：
如果 c 为0，则后面def就没有可能为1了，因为前面的三位都已经固定了，后面三位根本没有变化的可能了，只要变化，就必然会超过abcdef了
如果 c 为1，则后面的def 的选择只能在0~def 中，个数就是 def+1
如果 c 大于1，则后面的 def可以为任何数字，就是 0~999,为 1000 个
以上就是所有可能的1 出现的次数了

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        //获取每位数字
        vector<int> number;
        while(n)
        {
            number.push_back(n%10);
            n/=10;
        }

        int res=0;
        //从高位开始枚举
        for(int i=number.size()-1;i>=0;i--)
        {
            int left=0;
            int right=0;

            //进制
            int 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;
            }

            //计算低位可以全部为1
            res+=left*t;

            //当前位为1的情况
            if(number[i]==1)
            {
                res+=right+1;
            }
            else if(number[i]>1)
            {
                res+=t;
            }

        }
        return res;
    }
};