剑指 Offer 43. 1~n 整数中 1 出现的次数

题目

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

示例 1:
输入:n = 12
输出:5

示例 2:
输入:n = 13
输出:6

限制:
1 <= n < 231

注意:本题与主站233题相同

题解

public int countDigitOne(int n) {
    int count = 0;
    // 从个位开始遍历到最高位
    long i = 1;
    while (n / i != 0) {
        // 高于i位的数字
        long high = n / (10 * i);
        // i位数字
        long cur = (n / i) % 10;
        // 低于i位数字
        long low = n - (n / i) * i;
        // 当前位为0 只计算高位的0
        if (cur == 0) {
            count += high * i;
        } else if (cur == 1) {
            // 当前位为1 则高位加低位
            count += high * i + (low + 1);
        } else {
            // 当前位大于1
            count += (high + 1) * i;
        }

        // 进位
        i *= 10;
    }

    return count;
}