Count number of 2s, 给一个数n，求0到n里一共有多少个2.

给一个数n，要求返回从0到n里面一共有多少个2。比如n = 12, 返回2（2， 12）； n = 33，返回14(2, 12, 20 ---29, 32).
自己只写出了一种极其复杂的recursive的方法，求问论坛里面的大神们有什么方法可以解决哎？多谢。

其实这就是LC原题Number of Digit One

假设数字是123，那么最低位上是2的数字有2， 12， 22, 32... 112, 122.总共有13个数字
但如果数字是121，那么最低位上是2的数字就只有12个数字。

所以：看最低位有几个2的方法是n/10+(最低位==2)

同理，如果是235，第二位是2的数字有20--29, 120--129, 220--229共30个数字
但如果是215，第二位是2的数字就只有20--29, 120--129共20个数字
如果是225，，第二位是2的数字则是20--29, 120--129, 220--225共26个数字

所以：看倒数第二位有几个2的方法是(n/10)/10 * 10 （上述三种情况下，此式==20）
在此基础上，如果倒数第二位比2大，那么再加10；如果倒数第二位恰等于2，那么再加n % 10
然后继续推广：看倒数第三位有几个2的方法是(n/100)/10 * 100 （上述三种情况下，此式==0）
在此基础上，如果倒数第二位比2大，那么再加100；如果倒数第二位恰等于2，那么再加n % 100

...

好有趣的题，关注一下。

离人笑 发表于 2015-12-14 10:45
好有趣的题，关注一下。

想了一个比较复杂的递归方法…

离人笑 发表于 2015-12-14 11:10
想了一个比较复杂的递归方法…

我也是递归，分最大位数上面的数是大于2，等于2，还是小于2写的

oneshot 发表于 2015-12-14 12:59
我也是递归，分最大位数上面的数是大于2，等于2，还是小于2写的

嗯我们的方法应该差不多。我想不出更简单的办法了，其实这个递归的复杂度已经很不错了。