所有的讨论，认为有前导 0，例如 10 看成 010。
整的区间段（例如 099、0999）可以预先求出
以求解 666 为例，可以将 666 拆分为分别求解：
- 600~666
- 500~599（预先求出，这些值是确定的）
- 400~499（预先求出，这些值是确定的）
- 300~399（预先求出，这些值是确定的）
- 200~299（预先求出，这些值是确定的）
- 100~199（预先求出，这些值是确定的）
- 0~99 的数字 1 的个数（预先求出）
最后求和得到结果。
- 第 1 类（整数区间段）：对于 500599、400499、300399、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, 那么需要求出
也就是说，09、099、0999、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];
}
}
