剑指offer 43——1～n整数中1出现的次数

输入：n = 12
输出：5

输入：n = 13
输出：6

class Solution {
    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }

        // 存储从1到上一个数的总结果，初始是从1到1的总结果
        int before = 1;
        int temp, count;
        for (int i = 2; i <= n; i++) {
            temp = i;
            count = 0;
            while (temp != 0) {
                // 计算当前数字的个位数是否等于1
                if (temp % 10 == 1) {
                    count++;
                }
                temp /= 10;
            }

            before += count;
        }
        return before;
    }
}

class Solution {
    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }
        // 存储数字原本含有的1的数量
        int[] countOne = new int[n + 1];
        // 存储从1到上一个数的总结果，初始是从1到1的总结果
        int before = 0;
        int temp, count;
        for (int i = 1; i <= n; i++) {
            countOne[i] = (i % 10 == 1 ? 1 : 0) + countOne[i / 10];
            before += countOne[i];
        }
        return before;
    }
}

3210 = 3000 + 200 + 10 + 0
          = 3 * 1000 + 2 * 100 + 1 * 10 + 0 * 1

从千位 3 开始，针对 1000 ~ 1999 这 1000 个数字，千位上都是 1，因此这里有 1000 个。
百位 2，针对 100 ~ 199 这 100 个数字，百位上都是 1。一共出现了 3 组，分别是 100 ~ 199、1100 ~ 1199、2100 ~ 2199、3100 ~ 3199，一共 (4 * 100 = 400) 个。
十位 1，针对 10 ~ 19 这 10 个数字，十位上都是 1。一共出现了 32 组，但是再加上 3210 本身十位上也是 1，因此一共有 ( 32 * 10 + 1 = 321) 个。
个位 0，针对 1、11、21、...、101、111、121、...、1001、1011、1021、...、3201，每 10 个数都会出现 1 个，因此一共有 (321 * 1 = 321)个。
一共 2042 个。

我们将数字 n，按照位，从低到高进行遍历。
我们假设当前位的数字为 cur，高位为 high，低位为 low，位数为 digit。比如 3210 这个数，针对百位而言，cur 是 2，high 是 3，low 是 10，digit 是 100。
针对 cur，有 3 种情况：
1、大于 1，那么此位 1 的个数就是：(high + 1) * digit
2、等于 1，那么此位 1 的个数就是：high * digit + low + 1
3、小于 1（也就是等于 0 ），那么此位 1 的个数就是：high * digit

class Solution {
    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }

        // 高位
        int temp = n;
        // 低位
        int low = 0;
        // 1出现的总次数
        int total = 0;
        // 当前位数，比如个位时为1，十位时为10，百位时为100
        int pow = 1;
        while (temp != 0) {
            // 当前位上的数字
            int num = temp % 10;
            // 剩下的高位
            temp = temp / 10;
            // 如果当前位上的数字是0
            if (num == 0) {
                // 只加上高位对应
                total += temp * pow;
            }
            // 如果当前位上的数字是1
            else if (num == 1) {
                // 加上高位对应的数字，和低位的所有，再加1(它本身)。
                // 比如10，虽然低位是0，但本身还有1
                total += temp * pow + low + 1;
            }
            // 如果当前位上的数字大于1
            else {
                // 那么高位+1
                total += (temp + 1) * pow;
            }

            // 低位
            low += num * pow;
            // 进入下一位
            pow = pow * 10;
        }

        return total;
    }
}