雅虎搜狐创新工场微软算法题.doc

雅虎：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 most 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 integers greater than zero.Output The output should contains the smallest possible length of original sticks, one per line.首先说一下这个题的解题思想。1.选取某一个开始长度，开始组合小木棒，这个开始长度的限制条件为 不小于木棒最大长度，不大于所有木棒长度和，能被长度和整除2.从可用的最长的那根小木棒开始组合木棒，找出所有的结果集，找到结果集后开始组合下一根木棒。3.直到所有的小木棒都被组合完成，搜索结束。/night_blue/article/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，因为所有的小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:该段还剩的长度，level:已经成功的木棒数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. 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,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); 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个叶子节点的所有二叉树形态：分析：“卡特兰数”除了可以使用公式计算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 = 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 aiak ( 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），这样这个区间就是普通的下降区间，用常规的二分在这个区间里找数。