- 浏览: 21238 次
- 性别:
- 来自: 南京
最新评论
乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单的办法不外乎就是遍历每个数,然后toString() 看看里面有多少个1,最后全部加起来,这是我们得到标准答案的办法。
群里3个人写了3个笨方法都跑出来了,3个笨方法,呵呵 有意思,笨方法也不一样。 程序的实现真是变幻莫测。
view sourceprint?01 var re = /1{1}/g;
02
03 var max = 1 * 10000 * 10000;
04
05 getTotal(f);
06 getTotal(f1);
07 getTotal(f2);
08
09 function getTotal(func)
10 {
11 var total = 0;
12 var begin = new Date();
13 for(var i= 1 ;i <= max;i++)
14 {
15 total += func(i);
16 }
17 var end = new Date();
18 var timespan = end - begin;
19 alert("开始时间:"+begin + "\n 结束时间:"+end +"\n总耗时:"+timespan + "毫秒 \n 总数:"+total);
20 }
21
22 function f(num)
23 {
24 var t = 0;
25 while(num)
26 {
27 if(num < 10){ if(num==1)t++;break;}
28 var i = num % 10;
29 if(i == 1) t++;
30 num = parseInt(num / 10);
31 }
32 return t;
33 }
34
35 function f1(num)
36 {
37 var str = num.toString()
38 var t = 0;
39 for(var i=0;i<str.length;i++)
40 {
41 if(str.charAt(i)=="1") t++;
42 }
43 return t;
44 }
45
46 function f2(num)
47 {
48 var str = num.toString();
49 var t = 0;
50 while(re.exec(str))
51 {
52 t++;
53 }
54 return t;
55 }
当数量少的时候第一种最快,显然嘛,没有处理字符串的步骤。按理说数量越大他越有优势。 可是实测结果,3个都差不多。但是用C#跑的话,第一个明显越来越有优势。。。。
但是出题人肯定不是这样想的,很多人都在说自己的技巧与看法,我也思考了很久。
先拿 100来说 ,100里面有多少个1?
view sourceprint?01 10
02 11
03 12
04 13
05 14
06 15
07 16
08 17
09 18
10 19
11 01
12 11
13 21
14 31
15 41
16 51
17 61
18 71
19 81
20 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
群里3个人写了3个笨方法都跑出来了,3个笨方法,呵呵 有意思,笨方法也不一样。 程序的实现真是变幻莫测。
view sourceprint?01 var re = /1{1}/g;
02
03 var max = 1 * 10000 * 10000;
04
05 getTotal(f);
06 getTotal(f1);
07 getTotal(f2);
08
09 function getTotal(func)
10 {
11 var total = 0;
12 var begin = new Date();
13 for(var i= 1 ;i <= max;i++)
14 {
15 total += func(i);
16 }
17 var end = new Date();
18 var timespan = end - begin;
19 alert("开始时间:"+begin + "\n 结束时间:"+end +"\n总耗时:"+timespan + "毫秒 \n 总数:"+total);
20 }
21
22 function f(num)
23 {
24 var t = 0;
25 while(num)
26 {
27 if(num < 10){ if(num==1)t++;break;}
28 var i = num % 10;
29 if(i == 1) t++;
30 num = parseInt(num / 10);
31 }
32 return t;
33 }
34
35 function f1(num)
36 {
37 var str = num.toString()
38 var t = 0;
39 for(var i=0;i<str.length;i++)
40 {
41 if(str.charAt(i)=="1") t++;
42 }
43 return t;
44 }
45
46 function f2(num)
47 {
48 var str = num.toString();
49 var t = 0;
50 while(re.exec(str))
51 {
52 t++;
53 }
54 return t;
55 }
当数量少的时候第一种最快,显然嘛,没有处理字符串的步骤。按理说数量越大他越有优势。 可是实测结果,3个都差不多。但是用C#跑的话,第一个明显越来越有优势。。。。
但是出题人肯定不是这样想的,很多人都在说自己的技巧与看法,我也思考了很久。
先拿 100来说 ,100里面有多少个1?
view sourceprint?01 10
02 11
03 12
04 13
05 14
06 15
07 16
08 17
09 18
10 19
11 01
12 11
13 21
14 31
15 41
16 51
17 61
18 71
19 81
20 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
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 640在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 660最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1057在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3034输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1001背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1264我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 672Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 890排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1129设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1337求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 720题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1293题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1789题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1034很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 573给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 938在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 728快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
最大子序列、最长公共子串、最长公共子序列
2011-08-25 18:33 754最大子序列 最大子序列是要找出由数组成的一维数组中和最大的连续 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1016阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
1亿以内的质数(共5761455个数).txt
从一亿个数中找出最大的100个 或者n个 用了个堆从一亿个数中找出最大的100个 或者n个 用了个堆
把1亿内的所有质数用.in文件里存放 相邻2个数字用空格隔开.
2013年年底的时候,我看到了网上流传的一个叫做《Java面试题大全》的东西,认真的阅读了以后发现里面的很多题目是重复且没有价值的题目,还有不少的参考答案也是错误的,于是我花了半个月时间对这个所谓的《Java面试...
假设我们有1亿个数字范围,那么代码里的intArr数组也得搞1亿+1个位置,哪怕我们只排序5个数字。冒泡排序相比桶排序,对空间要求不高,但是因为排序的时候使用双
32位无符号整数的范围是0 ~ 4 294 967 295,现在有一个正好包含40亿个无符号整数的文件,所以在整个范围中必然有未出现过的数。怎么找到所有未出现过的数? 要求: 可以使用最多1GB的内存。 进阶: 内存限制10MB,...
整数部分里的零读出或不读的情况有以下几种: 1、不读出的情况: 零在每级的结尾时这里的一级是指每四位,个位到千位是一级, 万位到亿位是一级,此后一次类推。 3006200中3后面的两个零是万位到亿位的一级的结尾...
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 39、下面的程序代码输出的结果是多少? 40、final, finally, finalize的区别。 41、...
我告诉他,大概27万左右,因为网民总1亿 ,365天每天都有人可能过生日,所以这个27万的正确率绝对80%以上。 2,A公司的年度交易量发展变化图 "年度 "每日交易额 "年度交易额 "每日订单量 "平均每单金额( " " "(万)...
本文实例讲述了JavaScript将数字转换成大写中文的方法。分享给大家供大家参考。具体实现方法如下: function intToChinese ( str ) { str = str+''; var len = str.length-1; var idxs = ['','十','百','千','万...
只有1个操作数的运算符。 如果操作数是一个常数,它不需要用括号括起,并且与运算符之间不需要空格分隔,如: sqr2 = 1.41421 cos0 = 1 当操作数是表达式时,需要用括号括起,以划分优先级: sqr(1 + 2) = 1....
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 25 39、下面的程序代码输出的结果是多少? 25 40、final, finally, finalize的区别。 27 ...
所以,如果有人问我,今天大概多少网民过生日我告诉 " "他,大概27万左右,因为网民总1亿,365天每天都有人可能过生日,所以这个27万的正确率绝对80% " "以上。 " " " " " " " "2,A公司的年度交易量发展变化图 " " ...
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 25 39、下面的程序代码输出的结果是多少? 25 40、final, finally, finalize的区别。 27 ...
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 27 39、下面的程序代码输出的结果是多少? 28 40、final, finally, finalize的区别。 30 ...
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 25 39、下面的程序代码输出的结果是多少? 25 40、final, finally, finalize的区别。 27 ...
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 25 39、下面的程序代码输出的结果是多少? 25 40、final, finally, finalize的区别。 27 ...
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 25 39、下面的程序代码输出的结果是多少? 25 40、final, finally, finalize的区别。 27 ...
38、try {}里有一个return语句,那么紧跟在这个try后的finally {}里的code会不会被执行,什么时候被执行,在return前还是后? 25 39、下面的程序代码输出的结果是多少? 25 40、final, finally, finalize的区别。 ...