剑指 Offer 43. 1～n 整数中 1 出现的次数（递归、数学）

举个例子： n = 2304 。答案为四个部分之和：

1. 所有小于等于2304的正整数中，个位出现1的次数.
2. 所有小于等于2304的正整数中，十位出现1的次数.
3. 所有小于等于2304的正整数中，百位出现1的次数.
4. 所有小于等于2304的正整数中，千位出现1的次数.

循环地计算每个位上出现的1的次数。（个位、十位、百位、…）

class Solution {
    
    public int countDigitOne(int n) {
    
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long mulk = 1;
        int ans = 0;
        // 1234 567
        for (int k = 0; n >= mulk; ++k) {
    
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}