题解 | 「力扣」第 233 题：数字 1 的个数（困难、动态规

参考资料 1：https://leetcode-cn.com/problems/number-of-digit-one/solution/zhu-wei-ji-suan-so-easy-by-faith_previal-7lep/

参考资料 2：https://leetcode-cn.com/problems/number-of-digit-one/solution/shu-wei-dp-liang-ge-yi-wei-dp-tablejie-j-7bai/

所有的讨论，认为有前导 0，例如 10 看成 010。

整的区间段（例如 0_99、0999）可以预先求出

以求解 666 为例，可以将 666 拆分为分别求解：

• 600~666
• 500~599（预先求出，这些值是确定的）
• 400~499（预先求出，这些值是确定的）
• 300~399（预先求出，这些值是确定的）
• 200~299（预先求出，这些值是确定的）
• 100~199（预先求出，这些值是确定的）
• 0~99 的数字 1 的个数（预先求出）

最后求和得到结果。

• 第 1 类（整数区间段）：对于 500_599、400499、300_399、200299、0~99，它们的最高位没有 1 ，因此它们的 1 个个数取决于 0~99 中 1 的个数（找到了大问题和小问题之间的联系）。
• 第 2 类（最高位是 1，每一个数都一定有 1）：对于 100~199 ，因为百位数是1，所以 100~199 每个数中都有 1，因此等于 100 加上 0~99 中 1 的个数
• 第 3 类（不满足一个整的区间段）：对于 600~666，1 的个数取决于后两位中 1 的个数，就是 0~66 中 1 的个数，这件事情有点麻烦，后面再说。

对于一个数字，假设从个位到最高位标号为 1~n, 那么需要求出

也就是说，0_9、099、0_999、09999、...、 ~ 包含 1 的个数，这里 为数字 的长度。

---

分别记为 、 、、... 、 中包含 1 个数。

以 666 为例，那么 S1 就是 0~6 中包含 1 的个数、S2 就是 0~66 中包含 1 的个数

首先定义 dp 数组 dp1[i] 表示 0~ 中包含 1 的个数，例如

• dp1[0] 表示求 0~9 中包含 1 的个数，
• dp1[1] 表示求 0~99 中包含 1 的个数

假设已知 dp1[0]，那么根据上述分析，可以求出

这是因为 0~99 可以分为：

• 十位是 dp[0] ，个位都是 1，有 10 * dp[0] 这么多 1。

  （高位是 dp[0] ，最低位都是 1）

01
11
21
31
41
51
61
71
81
91

• 10^1：数出出现在十位的 1 有 10 个
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

dp1[2] 表示： 0~999 里出现的 1 的个数

dp1[1] * 10 指的是：最高位有 0、1、2、3、4、5、6、7、8、9 一共 10 种情况，后两位里 1 的个数由 dp1[1] 决定。

先选最高位，再选低两位，所以是乘法。

特别地，最高位是 1 的每一个数都有 1 所以是 100 个，这里的 100 是 100、101、102、……、199，高位是 1 数出 100 个。因此，

最基本情况 : 因为 0~9 中只有一个 1，因此 dp1[0] = 1。

然后再定义 dp 数组 dp2[i]：表示「从右往左」开始第 i + 1 个数到最后一个数组成的数字包含 1 的个数。

dp2[0] 表示 0 到 6 中包含 1 的个数
例如 dp2[1] 在上例中表示 0~66 包含 1 的个数

对于 i，假设此位为 t，那么需要考虑如下几种情况：

• （这种情况很简单）如果 t = 0，那么该位的结果只能依赖之前的位置，此时有 dp2[i] = dp2[i - 1]
• （这种情况也不难）如果 t = 1，例如 166，此时应该求出 0~66 中元素 1 的个数，也就是 dp2[i - 1]，然后加上由 100~166 中百位数 1 的个数，有 67 个。再加上 0~99 中 1 的个数 dp1[1]。此时有：

• 如果 t != 0 并且 t != 1，此时由一开始的分析可以得到

• base case: 如果最后一个数字为 那么 dp2[0] = 0，否则 dp2[0] = 1。

输出：dp2[len - 1]。

参考代码：

import java.util.Arrays;

public class Solution {

    public int countDigitOne(int n) {
        // 转换成为字符串
        String s = String.valueOf(n);
        int len = s.length();
        if (len == 1) {
            return n == 0 ? 0 : 1;
        }

        // A[i] 表示：0~10^{i+1} - 1 里包含 1 的个数
        // i = 0 时，10^{i+1} - 1 = 10 - 1 = 9
        // i = 1 时，10^{i+1} - 1 = 100 - 1 = 99
        int[] A = new int[len - 1];
        A[0] = 1;
        for (int i = 1; i < len - 1; i++) {
            A[i] = 10 * A[i - 1] + (int) Math.pow(10, i);
        }

        int[] dp = new int[len];
        if (s.charAt(len - 1) == '0') {
            dp[0] = 0;
        } else {
            dp[0] = 1;
        }
        for (int i = 1; i < len; i++) {
            char currChar = s.charAt(len - i - 1);
            if (currChar == '0') {
                // 高位是 0，没有 1，就取决于低位中 1 的个数
                dp[i] = dp[i - 1];
            } else if (currChar == '1') {
                // 最高位是 1，高位是 1 的个数取决于后面有多少个数，要记得加 1，因为有 10000 这种情况
                int count = Integer.parseInt(s.substring(len - i, len));
                // dp[i - 1] 和情况 1 一样理解
                // A[i - 1] 比如 199，A[i - 1] 表示 0 到 99 的里 1 的个数
                dp[i] = (count + 1) + dp[i - 1] + A[i - 1];
            } else {
                // 最高位是 2、3、4、5、6、7、8、9、10
                // dp[i - 1] 表示余数部分
                // (Character.getNumericValue(currChar)) * A[i - 1] 表示有几个区间段
                // (int) Math.pow(10, i) 最高位是 1 每一位都是 1 所以是 10 的方幂
                dp[i] = dp[i - 1] + (currChar - '0') * A[i - 1] + (int) Math.pow(10, i);
            }
        }
        return dp[len - 1];
    }
}