一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 830|回复: 5
收起左侧

[算法题] Count number of 2s, 给一个数n,求0到n里一共有多少个2.

[复制链接] |试试Instant~ |关注本帖
oneshot 发表于 2015-12-14 08:45:04 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给一个数n,要求返回从0到n里面一共有多少个2。比如n = 12, 返回2(2, 12); n = 33,返回14(2, 12, 20 ---29, 32).
自己只写出了一种极其复杂的recursive的方法,求问论坛里面的大神们有什么方法可以解决哎?多谢。
stellari 发表于 2015-12-18 09:26:05 | 显示全部楼层
其实这就是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

...


回复 支持 1 反对 0

使用道具 举报

离人笑 发表于 2015-12-14 10:45:14 | 显示全部楼层
好有趣的题,关注一下。
回复 支持 反对

使用道具 举报

离人笑 发表于 2015-12-14 11:10:59 | 显示全部楼层
离人笑 发表于 2015-12-14 10:45
好有趣的题,关注一下。

想了一个比较复杂的递归方法…
回复 支持 反对

使用道具 举报

 楼主| oneshot 发表于 2015-12-14 12:59:23 | 显示全部楼层
离人笑 发表于 2015-12-14 11:10
想了一个比较复杂的递归方法…

我也是递归,分最大位数上面的数是大于2,等于2,还是小于2写的
回复 支持 反对

使用道具 举报

离人笑 发表于 2015-12-14 13:15:24 | 显示全部楼层
oneshot 发表于 2015-12-14 12:59
我也是递归,分最大位数上面的数是大于2,等于2,还是小于2写的

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表