从1到1亿这1亿个数里面有多少个1?

遍历每个数再toString() 看看里面有多少个1
服务器君一共花费了470.132 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单的办法不外乎就是遍历每个数,然后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

本文地址:http://www.nowamagic.net/librarys/veda/detail/1331,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1331

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《重构:改善既有代码的设计》 福勒(Martin Fowler) (作者), 熊节 (译者)

《重构:改善既有代码的设计》清晰地揭示了重构的过程,解释了重构的原理和最佳实践方式,并给出了何时以及何地应该开始挖掘代码以求改善。书中给出了70多个可行的重构,每个重构都介绍了一种经过验证的代码变换手法的动机和技术。《重构:改善既有代码的设计》提出的重构准则将帮助你一次一小步地修改你的代码,从而减少了开发过程中的风险。

更多计算机宝库...