题目描述

解题思路

详细解析：https://leetcode.cn/leetbook/read/illustration-of-algorithm/57nyhd/
名词解析：

这道题就是求各个十分位上1出现的次数，这里以十位为例进行说明，认为十位以上的为高位high，十位以下的为低位low:
拿2304来举例子，此时当前位cur为第十位，低位就是4，高位就是23。
此时高位high = 2，地位low = 1，cur = 0; 注：high和low表示位数，cur表示数值

• 当cur == 0 时，此时含有1的最大数字就为2219，此时不看1，就有0 ~ 229个数字满足有1，所以res += high * digit
• 当cur == 1时，此时含有1的最大数字就是2314，此时除去当前的1，那么就有0~234，res+=(high * dight) + low + 1
• 当cur 为 2，3，…，9时，此时含有1的最大数字就是2319，那么就有0~239，res+=(high + 1) * digit

  注意：上面案例只计算的是一位的情况，所以计算所有位数，需要把每个位数当作cur来做计算。

class Solution {
    public int countDigitOne(int n) {
        int high = n / 10, low = 0, digit = 1, cur = n % 10, res = 0;
        // 高位不为0，cur不为0，才进行循环
        while (high != 0 || cur != 0) {
            if (cur == 0) res += high * digit;
            else if (cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low = cur * digit + low;
            // 当前位是高位的余数
            cur = high % 10;
            // 高位需要去掉最后一位
            high /= 10;
            // 位数加10
            digit *= 10;
        }
        return res;
    }
}