雅虎搜狐创新工场微软算法题(doc 8页).doc_第1页
雅虎搜狐创新工场微软算法题(doc 8页).doc_第2页
雅虎搜狐创新工场微软算法题(doc 8页).doc_第3页
雅虎搜狐创新工场微软算法题(doc 8页).doc_第4页
雅虎搜狐创新工场微软算法题(doc 8页).doc_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、雅虎:1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)某一个元素也加一,现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。2.一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值比如3,2,4,3,6 可以分成3,2,4,3,6 m=1; 3,62,4,3 m=23,32,46 m=3 所以m的最大值为3解:poj 1011,搜索+强剪枝DescriptionGeorge took sticks of the same length and cut them randomly until all parts became at mo

2、st 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are inte

3、gers greater than zero.Output The output should contains the smallest possible length of original sticks, one per line.首先说一下这个题的解题思想。1.选取某一个开始长度,开始组合小木棒,这个开始长度的限制条件为 不小于木棒最大长度,不大于所有木棒长度和,能被长度和整除2.从可用的最长的那根小木棒开始组合木棒,找出所有的结果集,找到结果集后开始组合下一根木棒。3.直到所有的小木棒都被组合完成,搜索结束。/night_blue/article

4、/details/2966056思路二:1.len=maxai & len|sum(ai)2.为了避免重复搜索,令每个大S的组成中,小S的长度依次递减,这样就需要在搜索之前对ai排序;全部的大S的第一段小S依次递减3.如果在某层搜索中,尝试将aj加入到第i个大S的组成中,如果最终aj没有被使用,且aj+1=aj,不需要继续尝试aj+14.如果此次是在尝试第i个大S的第一段小S aj,aj为当前可以被使用的最长的小S,如果此次尝试失败,直接退出搜索,即退回到对第i-1个大S的搜索。试想:失败说明现在使用aj是不可行的,那么什么时候使用aj呢?如果没有退出搜索,肯定会在之后的搜索中使用aj,因为所

5、有的小S必须都使用。之后的aj和最初尝试的aj有什么不同呢?没有不同,它们等价,因此之后也不会成功,不需要继续搜索。都一致:先对这些数进行排序;1. #include2. #include3. usingnamespacestd; 4. 5. intsticks64,n,len,num; (num为可以得到多少对)6. boolused64; 7. 8. boolcompare(inta,intb) 9. 10. returnab; 11. 12. 13. booldfs(intcur,intleft,intlevel) 14. /cur:当前已经计算的木棒编号,left:该段还剩的长度,le

6、vel:已经成功的木棒数15. if(left=0)/匹配一根木棒成功16. if(level=num-2) 17. returntrue; 18. for(cur=0;usedcur;cur+) /找到第一个还没被用的19. ; 20. usedcur=true; 21. if(dfs(cur+1,len-stickscur,level+1) 22. returntrue; 23. usedcur=false; 24. returnfalse; 25. else 26. if(cur=n-1) /最后一根了27. returnfalse; 28. for(inti=cur;ileft) 34

7、. continue; 35. usedi=true; 36. if(dfs(i,left-sticksi,level) 37. returntrue; 38. usedi=false; 1.1. /不行的话,就不会使用这个39. 40. returnfalse; 41. 42. 43. 44. intmain() 45. 46. while(cinn) 47. if(n=0) 48. break; 49. intsum=0; 50. for(inti=0;in;i+) 51. scanf(%d,&sticksi); 52. sum+=sticksi; 53. 54. sort(sticks,

8、sticks+n,compare);/由大到小排序55. boolend=false; 56. for(len=sticks0;len=sum/2;len+) 57. if(sum%len=0) 58. used0=true; 59. num=sum/len; 60. if(dfs(0,len-sticks0,0) 61. end=true; 62. printf(%dn,len); 63. break; 64. 65. used0=false; 66. 67. 68. if(!end) 69. printf(%dn,sum); 70. memset(used,0,sizeof(used);

9、71. 72. /system(pause);73. return0; 74. 搜狐:3.四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和()卡特兰数(Catalan)例子1:Cn= n对括号正确匹配组成的字符串数,例如 3对括号能够组成:() ()() ()()() ()() ()()例子2:Cn= n+1个数相乘,所有的括号方案数。例如, 4个数相乘的括号方案为:(ab)c)d (a(bc)d (ab)(cd) a(bc)d) a(b(cd)例子3:Cn= 拥有 n+1 个叶子节点的二叉树的数量。例如 4个叶子节点的所有二叉树形态:分析:“卡特兰数”除了可以使用公式计算

10、Cn=C(n,2n)-C(n-1,2n),也可以采用“分级排列法”来求解。以 n对括弧的合法匹配为例,对于一个序列 ()而言,有两个左括弧,和一个右括弧,可以看成“抵消了一对括弧,还剩下一个左括弧等待抵消”,那么说明还可以在末尾增加一个右括弧,或者一个左括弧,没有左括弧剩余的时候,不能添加右括弧。arr = new doublen + 1;/arr代表有 k个括弧的时候,剩余 (个数为 i的排列方案个数 arr1 = 1; double Catalan(int n) if (n = 0) return 1; for (int i = 2; i = 2 * n; i+) var m = i =

11、n ? i : 2 * n + 1 - i; for (int j = (i - 1) & 1; j 0) arrj - 1 += arrj; if (j j位置的这些括号的最大组成种数,dpij = dpi-1j-1 /i是(,j是),并且他们搭配 + sigama(dpik * dpk+1j), i与k搭配,k+1与j搭配, ik0 iak & k=0&k0)maxLenIncr0=1;maxLenIncri 表示以i结尾的最长递增子序列长度。代码如下:/*maxLenIncri 表示以i结尾的最大递增子串长度*/maxLenIncri = max maxLenIncrk+1 if aia

12、k ( k=0&k0);int maxLenIncr(int* p, int len) int* maxLenIncr=new intlen; int maxLen=1; /*Default value=1*/ for(int i=0; ilen; i+) maxLenIncri = 1; for(int i=1; ilen; i+) for(int k=0; k ak) maxLenIncri=max(maxLenIncrk+1, 1); if(maxLenIncrimaxLen) maxLen=maxLenIncri; return maxLen;5. 一种分情况的二分:首先观察这个序列,先下降,然后突然上升(暂且叫断点吧),接着又下降,而且有个性质(*)断点前面的所有数都比断点后面的所有数小!令当前二分的区间是l,h,那么这个区间有3中可能性:(1)落在断点前的那个下降区间里面;(2)落在断点后的那个下降区间里面;(3)跨区间。我们看怎么判断当前落在哪个区间里,另a是原来的数组 如果al ah,由性质(*)得到不可能是跨区间的(否则因为l在断点前的区间,h在断点后的区间,那么肯定有alah),那么只可能是(1)或者(2),这样这个区间就是普通的下降区间,用常规的二分在这个区间里找数。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论