前言
刷某乎突然刷到了这个问题，正好自己最近也在写LeetCode，想着这题也不算难，正好可以拿来练手。话不多说，先看题目。
题目描述
从一读到一亿需要读多少个汉字，而汉字在不同的场合、环境以及不同的人口中可能存在细微的差异，为了统一读法，以保证本文的答案与大多数答案没有出入，现对如何读出一个一亿一下的数有如下定义：
-
对于零在万位的情况：如果千位有数，则省略不读零
10_1020读作十万一千零二十而不是十万[零]一千零二十
10_0102读作十万零一百零二 -
对于两个非零数之间存在多个零的情况：读且只读一个零
1001_0020读作一千零一万零二十
1000_0020读作一千万零二十 -
对于最高位为十(万)位的数：如果十(万)位为一，则一省略不读
10_1210读作十万一千二百一十 -
普通情况，直接正常按位读出
1234_5678读作一千二百三十四万五千六百七十八
34_5078读作三十四万五千零七十八
思路分析
经过上面的总结，不难发现：万位之前与万位之后的读法相同，如：
1234_5678读作一千二百三十四万五千六百七十八
1234_0567读作一千二百三十四万零五百六十七
1234_0000读作一千二百三十四万
1234读作一千二百三十四
但是中间连接它们的有时为“万零”，有时为“万”，具体总结如下：
-
后四位为0，连接符为“万”，且需要去掉后四位读出来的“零”
1234_0000读作一千二百三十四万而是一千二百三十四万零 -
后四位整体不为0，但千位为0，连接符为“万零”
1234_0567读作一千二百三十四万零五百六十七 -
后四位整体不为0，但千位不为0，连接符为“万”
1234_5678读作一千二百三十四万五千六百七十八
所以如果想读出一个一亿一下的数，我们只需要将数分为前后各4位分别读出，然后加上中间的“万[零]”即可。
有了这个思路，我们已经将题目从从一读到一亿需要读多少个汉字，简化成了从一读到一万需要读多少个汉字。
从一读到一万需要多少个汉字
通过观察下面几个数的读法，不难发现规律：
1234读作一千二百三十四
234读作二百三十四
34读作三十四
4读作四
所以想要读一个千位数，我们只需要读千位即可，因为百位已经读过了，重复读的话一定会让我们写出的代码更复杂，那怎么体现我们已经读过这个数了呢？不难想到，我们可以使用动态规划的方式，将读过的数保存在一个数组中，每次读的时候将读过的值直接从数组拿出来，那就不用重复读了。
动态规划以及它的转移方程
顾名思义，转移方程就是一个较大的数如何转成一个较小的数的转移方法，也可以理解为一个函数：
大数abcd的汉字数 = dp(小数bcd的汉字数)
这里的dp就是转移方程。
我们只要得到转移方程，就能得出一到一万每一个数字的中文读法所需要的汉字了。
-
从1~10为一个汉字
dp[i] = 1 -
从11~20为两个汉字
dp[i] = 2 -
从20~99，汉字个数与末尾是否为零相关
dp[i] = i % 10 == 0 ? 2 : 3 -
从100~999，汉字个数与个位、十位的零相关
if (i % 100 == 0) dp[i] = 2; else if (i % 10 == 0 || i % 100 < 10) dp[i] = 4; else dp[i] = 5; -
从1000~9999，汉字的个数可以由之前的结果组合而来
2000读作两千dp[2000] = 2
2002读作两千零二dp[2002] = 2 + dp[2] + 1
2020读作两千零二十dp[2020] = 2 + dp[20] + 1
2200读作两千二百dp[2200] = 2 + dp[200]
2022读作两千零二十二dp[2022] = 2 + dp[22] + 1
2220读作两千二百二十dp[2220] = 2 + dp[220]
2202读作两千二百零二dp[2202] = 2 + dp[202]
2222读作两千二百二十二dp[2222] = 2 + dp[222]
可总结为：
dp[i] = dp[i % 1000] + (i % 1000 == 0 ? 2 : i % 1000 < 10 ? 3 : i % 1000 < 20 ? 4 : i % 1000 < 100 ? 3 : 2);
代码[从一读到一万]
public static void main(String[] args) {
long start = System.nanoTime();
int res = 0;
int[] dp = new int[10000];
for (int i = 1; i <= 10; i++) {
dp[i] = 1;
res += dp[i];
}
for (int i = 11; i <= 20; i++) {
dp[i] = 2;
res += dp[i];
}
for (int i = 21; i <= 99; i++) {
dp[i] = i % 10 == 0 ? 2 : 3;
res += dp[i];
}
for (int i = 100; i <= 999; i++) {
dp[i] = i % 100 == 0 ? 2 : i % 10 == 0 || i % 100 < 10 ? 4 : 5;
res += dp[i];
}
for (int i = 1000; i < 10000; i++) {
dp[i] = dp[i % 1000] + (i % 1000 == 0 ? 2 : i % 1000 < 10 ? 3 : i % 1000 < 20 ? 4 : i % 1000 < 100 ? 3 : 2);
res += dp[i];
}
System.out.println("从1读到10000共读了" + (res + 2) + "个汉字, 耗时" + (System.nanoTime() - start) / 1e6 + "ms");
}
// 结果
从1读到10000共读了64693个汉字, 耗时0.430422ms
从一读到一亿的转移方程
上面已经给出了从一读到一万的转移方程，而且在之前的分析中，从一读到一亿的方程可以通过从一读到一万的方程得来：
-
后四位为0，连接符为“万”，且需要去掉后四位读出来的“零”
dp[1234_0000] = dp[1234] + dp[0] -
后四位整体不为0，但千位为0，连接符为“万零”
dp[1234_0567] = dp[1234] + dp[567] + 2 -
后四位整体不为0，但千位不为0，连接符为“万”
dp[1234_5678] = dp[1234] + dp[5678] + 1 -
后四位为十几的时候记得还要读出一
dp[1234_0018] = dp[1234] + dp[18] + 3
最终代码[从一读到一亿]
public class ReadNumbers {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int res = 0;
int[] dp = new int[1_0000];
dp[0] = 1;
for (int i = 1; i <= 10; i++) {
dp[i] = 1;
res += dp[i];
}
for (int i = 11; i <= 20; i++) {
dp[i] = 2;
res += dp[i];
}
for (int i = 21; i <= 99; i++) {
dp[i] = i % 10 == 0 ? 2 : 3;
res += dp[i];
}
for (int i = 100; i <= 999; i++) {
dp[i] = i % 100 == 0 ? 2 : i % 10 == 0 || i % 100 < 10 ? 4 : 5;
res += dp[i];
}
for (int i = 1000; i < 1_0000; i++) {
int next = i % 1000;
dp[i] = dp[next] + (next == 0 ? 1 : next < 10 ? 3 : next < 20 ? 4 : next < 100 ? 3 : 2);
res += dp[i];
}
for (int i = 1_0000; i < 1_0000_0000; i++) {
int next = i % 1_0000;
res += dp[i / 1_0000] + dp[next] + (next == 0 ? 0 : next > 9 && next < 20 ? 3 : next < 1000 ? 2 : 1);
}
System.out.println("从1读到1_0000_0000共读了" + (res + 2) + "个汉字, 耗时" + (System.currentTimeMillis() - start) + "ms");
}
}
// 结果
从1读到1_0000_0000共读了1403898993个汉字, 耗时201ms
总结
这题真是比我想象中更复杂，总算是根据大家在某乎上的答案写出了动态规划的版本。使用动态规划确实能够让时间复杂度变得更低，但是对于比较复杂的问题，需要更严谨的分析才能拿到正确的转移方程。
网友评论