一道笔试题

和同学聊天时提到了在新浪面试记中说的那道编程题,这里再描述一遍题目:从1到100中取5个不相同的数,相加小于100,有多少种方法。

给她看了我的方法:

大神问了循环边界的确定方法,然后给出一个改进的版本:

既然是递增排列,那么循环初始值就不用像我的方法那样定死了,然后是最去掉一层循环,意思是最 后一个数有多少种情况是可以直接算出来的,99-sum得最后一个数的最大值,然后最后一个数一定是从m+1开始,所以又 num=99-sum-(m+1)+1 = 99-sum-m;

跑一下,确实快了很多,1ms以内解决问题,我之前的是要144ms左右。

然后继续看代码,发现循环边界确定的其实是有问题的,之前只是确定了边界的最大值,然而最大值并不是固定不变的,比如i=1时,j可以取到23,但是i=2时,j只能到22了,也就是说循环边界应该动态确定,修改iprfunc(),如下:

解释一下,i确定之后,最大情况:j+(j+1)+(j+2)+(j+3) = 99-i,所以 j<(99-i-6)/4 + 1,余下的同理。跑一下,2至3毫秒之间。还是比大神的慢一些。

结合大神的思想,去掉一层循环:

然后测试一下:

终于比大神的快一些了:

不知道此类问题有没有通用的算法,比如1到n中取m个数。如果路过的大神知道,还望不吝赐教。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注