聊聊在私立文理读cs的两年感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1125|回复: 5
收起左侧

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

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

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

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

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

使用道具 举报

全球28万学生4.7分推荐
离人笑 发表于 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写的

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-21 21:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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