对于输入 L 和 R, L 和 R 的范围在 1 到 10^20,求从 L 到 R 中包括数字 49 的个数。

例 1:

输入:

输出:

例 2:

输入:

输出:

【解题提示】:

  • 请在评论中先给出你的实现思路;
  • 然后贴出实现的代码;
  • 编程语言不限;
  • 评论支持代码高亮,请点击评论框菜单栏上的  < > 按钮;
4 2 收藏


直接登录
最新评论
  • C-2016   2016/11/06

    for each in range(10,1000):

    if “49” not in str(each):

    continue

    else:

    print(each)

  • 匿名了 JAVA 2016/11/13

    这么好的一个帖子,沉了, 没想到好的算法,有没有人分享下

  • 想到用正则匹配可以不?

  • 已经实现,循环l到r,用正则匹配幸运数字,匹配成功让sum加1,最后输出sum就可以得到

  • 哦哦   2016/11/23

    long long n=0;

    for(i=0;<=18;i++)

    n=n+pow(10,i)*(i+1);

  • re   2016/11/23

    应该是一个排列组合的问题,用循环的肯定不是最好的

    10^20 是个21位的数,去掉第一位的1,剩下20位,在去掉49剩下18位,把49看成一个整体,其实就是算19个元素的排列组合 + 18位数字变化。。。。。。。。。。。。

  • wf php、前端 2016/11/23

    for($i = 1, $max = pow(10, 20), $total = 0; $i <= $max; $i++){

    if(strpos($i, ’49’) !== false){

    ++$total;

    }

    }

    echo $total;

  • 冷月小刀 小学三年级 2016/11/24

    统计个数是个排列组合问题,n+2 位数以内统计公式为(n+1)*10^n,难点在对494949这类数字的去重。两位数内一个49, 三位数内20个49,四位数有一个4949所以有3000-1=2999个。这里发现49开头的四位数49xx会多统计所有两位数内49的个数,五位数49xxx则会多统计三位数内49的个数。再深入进去,1000以内20个,2000以内2*20=40个…但大于4900的时候要特殊处理,这里就略过了。对于526842这种数字我们只要拆分为1-500000  500001-520000  520001-526000……几个部分分别统计求和就能求出1到526842之间的幸运数。只要再算出1到另一个数之间幸运数个数就可以得出答案了

  • Ikaruga皓予 Android 2016/11/29

    不考虑”转字符串再用正则匹配”这种简单粗暴的解法的情况下,前边的同学已经说了,确实是个排列组合的问题,要找出[1,10^n]中有多少‘49’,通过(n-1)*10^(n-2)的方法可以计算出包含重复结果在内的所有包含‘49’的结果数量,接下来只要去掉除包含‘49’的两位数字以外,其他位上包含‘49’的结果数量(说着绕的慌。。比如10000以内,包含重复结果的个数为3*10^2=300个,再除去包含‘49’的两位,即100以内包含‘49’的数量1*10^0=1,最后结果为299个),即为结果。其他位上包含‘49’的结果数量如果也包含重复结果的话,就需要再进行去重。那么思路就很明显了,直接上递归:

     

  • 可健康了 程序员 2016/12/02

    print [a | a <- filter (\x -> elem “49” $ subsequences $ show x) [1..1000]]

  • 话说写暴力解法的都不考虑时间复杂度吗?问题规模大估计可以跑一个月

  • n = 21

    2.0987654320987656e+19

    :)

     

  • Samuel任 Linux运维初学者 2016/12/04

  • Laniary   2016/12/04

    传统数位dp

    dp[pos][pre][up][contain]表示到第pos位,前一位数字为pre,当前是否卡着上届,上一位与当前位是否位49的状态,我用tot数组表示该状态的总数字,contains数组表示该状态包含49的数的个数。具体pos位的顺序参考num的处理,卡上届的判断用于限制枚举该位的数字,例如数字是25,如果十位数枚举2,那么个位只能是0~5,如果十位数是1,则个位数可能是0~9。具体的大家自行搜索数位dp算法

     

  • {RoYal}   2016/12/04

  • lrscy 学生 2016/12/04

    HDU 3555 数位DP可解~

     

  • 林蛋凡 Android喵 2016/12/05

    其实,为什么不反过来 用49去匹配 L R呢   无非就一种

    1.(10^n * m + 49 ) * 10 ^ i + j      n > 1, m, i, j 任意    (i = 0 时, j = 0)

    然后拿这边的值x  去判断    是否   L >= x >= R 就好了

  • 就是那么屌 web前端开发 2016/12/05

    fucntion find(str) {

    var

    }

  • 就是那么屌 web前端开发 2016/12/05

    function find49(star, end) {
    var arr = [];
    for (var i=star;len=end-star,i<=len;i++) {
    if (i.indexOf(’49’) != -1) {
    arr.push(i);
    }
    }
    var str = arr.join(‘ ‘);
    return str;
    }

  • Pegasus   2016/12/05

    把微信那边回的单行代码贴下..

    这边不用单行了..拆开再发下..

  • ye_ibl .net 程序员 2017/03/10