剑指 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 < 2^31

1-n中1的个数.pdf

class Solution {
    public int countDigitOne(int n) {
        int[] f = new int[10], pow = new int[10];
        f[0] = 0; pow[0] = 1;
        int p = 1;
        for (int i = 1; i < 10; i++) {
            f[i] = f[i - 1] * 10 + pow[i - 1];
            pow[i] = pow[i - 1] * 10;
        }
        int pre = 0;
        String num = Integer.toString(n);
        n = num.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            int x = num.charAt(i) - '0';
            res += pre * x * pow[n - i - 1];
            if (x == 1) {
                pre++;
                res += f[n - i - 1];
            } else if (x != 0) {
                res += pow[n - i - 1] + x * f[n - i - 1];
            }
        }
        return res + pre;
    }
}