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

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

乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单的办法不外乎就是遍历每个数,然后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本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

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

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

《高性能JavaScript》 Nicholas C. Zakas (作者), 赵泽欣 (合著者), 丁琛 (译者)

《高性能JavaScript》揭示的技术和策略能帮助你在开发过程中消除性能瓶颈。你将会了解如何提升各方面的性能,包括代码的加载、运行、DOM 交互、页面生存周期等。雅虎的前端工程师 Nicholas C. Zakas 和其他五位 JavaScript 专家介绍了页面代码加载的最佳方法和编程技巧,来帮助你编写更为高效和快速的代码。你还会了解到构建和部署文件到生产环境的最佳实践,以及有助于定位线上问题的工具。如果你使用 JavaScript 构建交互丰富的 Web 应用,那么 JavaScript 代码可能是造成你的Web应用速度变慢的主要原因。

更多计算机宝库...