📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
比如当n为5时,1,2,3,4,5,1出现的次数为1
n为15时,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
1出现的次数为7次

上一篇:Google : 搜索提示功能实现
下一篇:最长等差数列问题
🔗
ForeverYoung 2011-5-27 13:56:17 | 只看该作者
全局:
貌似见过。。等大神来
回复

使用道具 举报

🔗
Roquin 2011-5-29 23:18:02 | 只看该作者
全局:
每一位上的个数加起来
  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 | 只看该作者
全局:
  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 | 只看该作者
全局:
本帖最后由 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 | 只看该作者
全局:
回复 5# BillyFan
这个做法有个小缺点,就是效率低的不能再低了。。
回复

使用道具 举报

🔗
BillyFan 2011-6-14 14:58:46 | 只看该作者
全局:
回复 6# darksteel

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

多谢指教啦~~~~
回复

使用道具 举报

🔗
darksteel 2011-6-15 10:43:05 | 只看该作者
全局:
回复 9# BillyFan
不敢当啊,开个玩笑。。当时我也以为是简单的递归结果费了好半天劲,其实如果不追求递归和简练,稳稳的展开了写也没多少
回复

使用道具 举报

🔗
MontagueHu 2011-6-20 08:51:11 | 只看该作者
全局:
本帖最后由 MontagueHu 于 2011-6-20 08:53 编辑

这道题很麻烦的,编程之美上面有分析,不是遍历所有数字的
回复

使用道具 举报

🔗
lambda2fei 2012-9-4 16:56:12 | 只看该作者
全局:
// count the number of occurrence of digit 'd' in series: 1, 2, 3, ..., n.
unsigned int DigitCounting(unsigned int n, unsigned int d) {
  unsigned int count = 0;
  for (unsigned int i = 1; true; i *= 10) {
    unsigned int q = n / (i * 10);
    unsigned int r = n % i;
    int dd = n / i % 10;
    if (n / i == 0 || dd < d && q == 0) break;
    if (dd != d) r = i - 1;
    if (dd < d || d == 0) --q;
    if (q >= 0) {
      count += q * i + r + 1;
    }
  }
  return count;
}
试试这个对不对,可以计算所有数字不仅仅是1
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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