简明现代魔法 -> 计算机算法 -> 数字1亿里面有多少个1呢

数字1亿里面有多少个1呢

2011-04-17

乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单的办法不外乎就是遍历每个数,然后toString() 看看里面有多少个1,最后全部加起来,这是我们得到标准答案的办法。

群里3个人写了3个笨方法都跑出来了,3个笨方法,呵呵 有意思,笨方法也不一样。 程序的实现真是变幻莫测。

var re = /1{1}/g;

var max = 1 * 10000 * 10000;

getTotal(f);
getTotal(f1);
getTotal(f2);

function getTotal(func)
{
    var total = 0;
    var begin = new Date();
    for(var i= 1 ;i <= max;i++)
    {
        total += func(i);
    }
    var end = new Date();
    var timespan = end - begin;
    alert("开始时间:"+begin + "\n 结束时间:"+end +"\n总耗时:"+timespan + "毫秒 \n 总数:"+total);
}

function f(num)
{
    var t = 0;
    while(num)
    {
        if(num < 10){ if(num==1)t++;break;}
        var i = num % 10;
        if(i == 1) t++;    
        num = parseInt(num / 10);
    }
    return t;
}

function f1(num)
{
    var str = num.toString()
    var t = 0;
    for(var i=0;i<str.length;i++)
    {
        if(str.charAt(i)=="1") t++;
    }
    return t;
}

function f2(num)
{
    var str = num.toString();
    var t = 0;
    while(re.exec(str))
    {
        t++;
    }
    return t;
}

当数量少的时候第一种最快,显然嘛,没有处理字符串的步骤。按理说数量越大他越有优势。 可是实测结果,3个都差不多。但是用C#跑的话,第一个明显越来越有优势。。。。

但是出题人肯定不是这样想的,很多人都在说自己的技巧与看法,我也思考了很久。

先拿 100来说 ,100里面有多少个1?

10
11
12
13
14
15
16
17
18
19
01
11
21
31
41
51
61
71
81
91

故意这么排列是我们可以把 0~99看作是 1个长度为2的数组, 1位为1时,2位的可能性是10,2位为1时1位的可能性为10,所以 0~99应该有20个1,而100有1个所以是21个。

999就应该是 1*10*10 + 10*1*10 + 10*10*1 = 300

400呢? 因为首位只能出现0~3 ,所以应该是 1*10*10 + 4*1*10 + 4*1*10

4 0000 0000 应该是 1 * (10^8) + 4*(10^7) * 8 = 420000000

随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们