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

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，搜索+强剪枝Descripti onGeorge took sticks of the same len gth and cut them ran domly un til all parts became

2、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 len gths expressed in un its a

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

4、blue/article/details/2966056思路二：1.le n=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呢？如果没有退出

5、搜索，肯定会在之后的搜索中使用aj，因为所有的小S必须都使用。之后的aj和最初尝试的aj有什么不同呢？没有不 同，它们等价，因此之后也不会成功，不需要继续搜索。都一致：先对这些数进行排序；1. #in elude 2. #in elude 3. using n amespaee std;4.4. int sticks64, n, len, num;(num 为可以得到多少对)5. bool used64;7.6. bool eompare( int a, int b)7. 8. return a b;9. 12.13. bool dfs( int cur, int left, int leve

6、l)14. /cur:当前已经计算的木棒编号，left:该段还剩的长度，level:已经成功的木棒 数15. if(left = 0) /匹配一根木棒成功16. if(level = num-2)17. returntrue;18. for(eur = 0; usedeur; eur+)/ 找到第一个还没被用的19. ;20. usedeur = true;21. if(dfs(eur+1, le n-stickscur, level+1)22. returntrue;23. usedeur = false;24. return false;1.32.33

7、.5.56.57. else if(cur = n-1)/ 最后一根了return false;for( int i = cur; i left)con ti nue;usedi = true;if(dfs(i, left-sticksi, level)return true;usedi = false;1.1. 不行的话，就不会使用这个return false;int mai n()while(ci nn) if(n = 0)break;int sum = 0;fo

8、r( int i = 0; i n; i+) scan f(%d, &sticksi);sum += sticksi;sort(sticks, sticks+n, compare); /由大到小排序bool end = false;for(len = sticks0; len = sum/2 ; len+) if(sum%le n = 0) 58.usedO = true;59.num = sum/le n;60.if(dfs(0, le n-sticksO, 0) 61.end = true;62.prin tf(%dn, le n);63.break;64.65.used0 = false

9、;66.67.68.if(!e nd)69.printf(%dn, sum);70.memset(used, 0, sizeof(used);71.72.system(pause);73.return 0;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)例

10、子3： Cn=拥有n+1个叶子节点的二叉树的数量。例如4个叶子节点的所有二叉树形态：分析：卡特兰数”除了可以使用 公式计算Cn=C (n，2n)-C( n-1，2n)，也可以采用分级排列法”来求解。以n对括弧的合法匹配为例，对于一个序列()而言，有两个左括弧，和一个右括弧，可以看成 抵消了一对括弧，还剩下一个左括弧等待抵消”，那么说明还可以在末尾增加一个右括弧，或者一个左括弧，没有左括弧剩余的时候，不能添加右括弧。arr = new doublen + 1;/arr 代表有k个括弧的时候，剩余(个数为i的排列方案个数arr1=1；double Catala n(i nt n)if (n = 0

11、) return 1;for (int i = 2; i = 2 * n; i+)var m = i = n ? i : 2 * n + 1 - i;for (i nt 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）maxLe nln cr0=1;maxLenlncri表示以i结尾的最长递增子序列长度。代码如下：/*maxLenlnc

12、ri表示以i结尾的最大递增子串长度*/maxLenlncri = max maxLenlncrk+1 if aiak ( k=0&k0);int maxLe nln cr(i nt* p, int len)int* maxLe nlncr=new in tle n;int maxLe n=1;/*Default value=1*/for(i nt i=0; ile n; i+)maxLe nln cri = 1;for(i nt i=1; ile n; i+)for(i nt k=0; k ak)maxLe nln cri=max(maxLe nln crk+1, 1);if(maxLe nl

13、n crimaxLe n)maxLe n=maxLe nln cri;retur n maxLe n;5. 一种分情况的二分：首先观察这个序列，先下降，然后突然上升(暂且叫断点吧)，接着又下降，而且有个性质(* )断点前面的所有数都比断点后面的所有数小！令当前二分的区间是l,h，那么这个区间有 3中可能性：(1) 落在断点前的那个下降区间里面；(2) 落在断点后的那个下降区间里面；(3 )跨区间。我们看怎么判断当前落在哪个区间里，另a是原来的数组如果al ah，由性质(*)得到不可能是跨区间的(否则因为I在断点前的区间,h在断点后的区间，那么肯定有alah)，那么只可能是(1)或者(2)，这样这个区间就是普通的下降区间，用常规的二分在这个区间