输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            res += helper(i);
        }
        return res;
    }
private:
    int helper(int n)
    {
        int cnt = 0;
        while(n)
        {
            if(n%10 == 1)
                cnt++;
            n /= 10;
        }
        return cnt;
    }
};

不出意外的运行超时，看样子应该有更高效的方法.

class Solution {
public:
    int countDigitOne(int n) {
        int sum = 0;
        for(long long base = 1;base <= n;base *= 10)
        {
            int left = n/base/10;
            int cur = n/base%10;
            int right = n % base;
            
            if(cur > 1)
                sum += (left + 1) * base;
            else if(cur < 1)
                sum += left * base;
            else
                sum += left * base + right + 1;
        }
        
        return sum;
    }
};

youtube上有个up主讲解的非常清晰，LeetCode 233. Number of Digit One 中文解释 Chinese Version