注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

#算法面试题# 陆续摘录。。。  

2012-11-27 17:53:22|  分类: IT就业篇 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1.找出所有的四元组(a,b,c,d),满足a^3+b^3=c^3+d^3 (a,b,c,d <= N)。要求O(N^2*logN)的时间,O(N)的空间。
答:先看另外一道很有趣的问题:给定两个排好序的数组A和B,两数组长度都为N,我们从两个数组各取一个元素求和,这样就得到了N^2个和,要求把这N^2个和按序输出,空间不能超过O(N)。方法是建立一个堆,开始时堆中的元素A[1]+B[1], A[1]+B[2], …, A[1]+B[N],每次从堆中取最小元素输出,然后看看这个元素是怎么来的,假设是A[i]+B[j],就把A[i+1]+B[j]插入堆。回到本问题,现在只是A,B数组都是1^3, 2^3, … N^3而已,用同样算法,如果发现相邻两次输出的值相同,说明找到了一组解。空间显然是O(N),因为共输出N^2个元素,每次堆操作是O(logN),所以时间是O(N^2*logN)
2.盒子中有n张卡片,上面的数字分别为k1,k2,...,kn。你有4次机会,每抽一次,记录下卡片上的数字,再将卡片放回盒子中。如果4个数字的和等于m。则你就赢得游戏,否则就是输。直觉上,赢的可能性太低了。请你给出程序,判断是否有赢的可能性。尽量提高方法的效率。
答:

这个题目最直接的方法就是四重循环遍历,n^4的时间复杂度,比较恐怖,但确实一个很好的起点。不用觉得很丢人,只要我们持续改进即可。

假设a,b,c是k1到kn中的三个数字,是否存在d使得,a+b+c+d=m?d在k1到kn中。和题目中的意思是一样的,变换等式如下:

d = m - a - b - c

如果满足上式,就是说,要在k1到k2中查找d,即:查找m - a - b - c,找到就存在;找不到,就是不存在。查找有线性查找,二分查找等。四重循环最内一层循环,可以认为是线性的查找,如果想更快一些,可以应用二分查找,而二分查找需要k1到kn是排序的,则先对n个数字进行排序,时间复杂度O(nlogn)。然后最内一层循环,改为二分查找,时间复杂度为O(n^3logn)。所以总的时间复杂度为O(n^3logn)。

经过上面的分析,我们可以得到启发,既然可以提出一个d,那么就可以再提出一个c。将a+b+c+d=m转换为c+d=m-a-b。这样,我们可以枚举k1到kn的两个数的和,然后对n2个和,进行排序,时间复杂度为o(n^2logn)。然后遍历n^2个和,设每一个和为pair,查找是否存在m-pair,同样二分查找,时间复杂度为O(n^2logn)。总的时间复杂度为O(n^2logn)。

经过上面的层层分析,大家能否发现,对于算法的持续改进,还是有一些窍门的,大家细心领悟。领悟得多了,必会有更大的进步。

  评论这张
 
阅读(207)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017