剑指offer 43 "1"出现的次数

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

对于每一位考虑出现的次数:

如果这一位是0: 出现次数 = (高位值)* 权重
这一位是1: 出现次数 = (高位值) * 权重 + 低位值 + 1
这一位>1 出现次数 = (高位值 + 1)* 权重

class Solution {
public:
    int countDigitOne(int n) {
        
        int result = 0;
        int low = 0;
        int weight = 1;
        //当前位置出现1的次数的三种情况: 当前位是0;1; >1

        //0: 取决于高位 * 本位权值  
        // 1: 高位 * 本位权值 +  低位 + 1
        //>1 (高位+ 1) * 本位权值 

        while(n >0)
        {
            if( n % 10 == 0)
            {
                result += n / 10 * weight;
            }
            else if(n % 10 == 1)
            {
                result += n / 10 * weight + low + 1;
            }
            else{
                result += (n / 10 + 1) * weight;
            }
            low += weight * (n % 10);
            n /= 10;
            if(n > 0)weight *= 10;
        }
        return result;
    }
};

时间复杂度: log 10 N
空间复杂度: 1