找1到1亿中包含68的数字并打印并记录68出现的总次数

缘起

这是我朋友面试一家公司的时候机试的题目. 题目很简单，就是求出

1~100000000（1亿）中68出现的总次数，例如 168068 就出现了2次68. 而且要求打印出全部包含68的数字

分析

具体代码参见DEMO【1】. 下面只说分析

蠢萌做法就是遍历, 将每个数字作为一个字符串，使用字符串操作求出答案.

但是显然不是面试官想要的答案. 其实正确的做法应该是使用dp（当然，有dp做法就有递归做法，只是我偏向dp）.

令 dp[n] 为1~10^n 范围内的68出现的总次数. 则根据第n位是不是6，我们可以得到下面的递推公式

1
dp[n] = dp[n-1]*10 + 10^(n-2)

其中起始条件是

1
dp[2] = 1

程序就显然了. 这里列出两种算法之间的性能比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
经过测试， 对比如下
前者是遍历1~1亿，使用字符串的方法得到的性能
后者是通过DP动态规划得到的性能

需要打印出字符串的前提下性能比较

三位数
7毫秒 vs 2毫秒
四位数
36毫秒 vs 12毫秒
五位数
256毫秒 vs 140毫秒
六位数
1579毫秒 vs 1285毫秒
七位数
17216毫秒 vs 15103毫秒
八位数
193358毫秒 vs 178752毫秒


不需要打印字符串 仅仅计算68出现次数下的性能比较

三位数
10毫秒 vs 1毫秒
四位数
23毫秒 vs 0毫秒
五位数
84毫秒毫秒 vs 1毫秒
六位数
350毫秒 vs 0毫秒
七位数
2374毫秒 vs 0毫秒
八位数
22058毫秒 vs 0毫秒

DEMO

【1】https://github.com/yfsyfs/algorithm/tree/master/dp_find68