查看: 2123|回复: 9
收起左侧

Google : 求1到n个数中,1出现的个数

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Google : 搜索提示功能实现
下一篇:最长等差数列问题
ForeverYoung 2011-5-27 13:56:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
貌似见过。。等大神来
回复

使用道具 举报

Roquin 2011-5-29 23:18:02 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
每一位上的个数加起来
  1. input=125
  2. output=0
  3. mod=10
  4. if input / mod != 0:
  5.     output += (input+1)/mod*mod/10 + max((input+1-mod),mod/10)
  6.     mod *= 10
  7. print output
复制代码
回复

使用道具 举报

darksteel 2011-6-6 11:54:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
  1. int cnt(int n, int x, int y)
  2. {
  3.         if(n == 0) return 0;
  4.         return (n+9)/10*x+cnt(n/10,x*10,(9-n%10)*x+y)-(n%10==1)*y;
  5. }
  6. int count1(int n)
  7. {
  8.         return cnt(n, 1, 0);
  9. }
复制代码

评分

参与人数 1大米 +10 收起 理由
BillyFan + 10 据说看到好的算法需要加分

查看全部评分

回复

使用道具 举报

BillyFan 2011-6-9 21:20:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (39)
 
 
2% (1)    👎
本帖最后由 BillyFan 于 2011-6-9 21:25 编辑


把从1到n的每一个整数转换成字符串连起来成为一个$strLong,
然后把$strLong中的所有字符“1”都replace成空字符,生成$strShort,
然后用$strLong的字符串长度减去$strShort的字符串长度,就是字符“1”出现的次数

  1. <?php
  2. function get_num_of_one($n){
  3.         $strLong = "";
  4.         for($i =1; $i <= $n; $i++){
  5.                 $strLong .= $i ;
  6.         }
  7.         $strShort = str_replace("1","",$strLong);
  8.         
  9.         return strlen($strLong) - strlen($strShort);
  10. }
  11. ?>
复制代码
回复

使用道具 举报

darksteel 2011-6-12 03:03:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 5# BillyFan
这个做法有个小缺点,就是效率低的不能再低了。。
回复

使用道具 举报

无效楼层,该帖已经被删除
无效楼层,该帖已经被删除
BillyFan 2011-6-14 14:58:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (39)
 
 
2% (1)    👎
回复 6# darksteel

哈哈,发现确实如此,之前一直被框在“数个数”的想法里,
第一次看你的算法的时候,没仔细看,还以为只是个简单的递归,
重新看了一遍,才发现原来可以跳出这个框框~~~~~

多谢指教啦~~~~
回复

使用道具 举报

darksteel 2011-6-15 10:43:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 9# BillyFan
不敢当啊,开个玩笑。。当时我也以为是简单的递归结果费了好半天劲,其实如果不追求递归和简练,稳稳的展开了写也没多少
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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