1～n 整数中 1 出现的次数

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

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

思路：

分析一个例子找规律，对于1234567，百位上出现1的次数，可以分成2种情况来分析，
百位前面的数字1234，百位上出现1的情况为从100～199，共100个数。所以有1234*100个数。
从百位数字开始到结尾的数字，对于数字567，有完整的100～199，所以有100个数。百位上1出现的次数为1234*100+100。如果数字567，不是567，而是其他，比如80，135呢？当80的时候，百位上不可能出现1，当135时，百位上1出现的次数为135-100+1次。设某个数共有m位，从右到左第i位(从0开始)1出现的次数等于，从右到左i+1~m上的数字乘以10ⁱ加上从右到左0~i位上的数字分情况的结果，记0～i位上的数字为x，如果x小于10ⁱ则结果为0，如果x大于等于10ⁱ，小于2*10ⁱ,则结果为x-10ⁱ+1,如果x大于等于2*10ⁱ,则结果为10ⁱ。用公式表示这三种情况就是min(max(n % (pow(10,i) * 10) - pow(10,i) + 1, 0), pow(10,i)),这样某一位上1出现的次数就是，n/pow(10,i+1)*pow(10,i)+min(max(n % (pow(10,i) * 10) - pow(10,i) + 1, 0)

代码：

class Solution {
public:
    int countDigitOne(int n) {
        long long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
            mulk *= 10;
        }
        return ans;
    }
};