雅虎搜狐創(chuàng)新工場(chǎng)微軟算法題

1、雅虎:1. 對(duì)于一個(gè)整數(shù)矩陣，存在一種運(yùn)算，對(duì)矩陣中任意元素加一時(shí)，需要其相鄰(上下左右) 某一個(gè)元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個(gè)全零矩陣經(jīng)過(guò)上述運(yùn)算得到。2. 個(gè)整數(shù)數(shù)組，長(zhǎng)度為 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，搜索+強(qiáng)剪枝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.首先說(shuō)一下這個(gè)題的解題思想。1. 選取某一個(gè)開(kāi)始長(zhǎng)度，開(kāi)始組合小木棒，這個(gè)開(kāi)始長(zhǎng)度的限制條件為不小于木棒最大長(zhǎng)度，不大于所有木棒長(zhǎng)度和，能被長(zhǎng)度和整除2. 從可用的最長(zhǎng)的那根小木棒開(kāi)始組合木棒，找出所有的結(jié)果集，找到結(jié)果集后開(kāi)始組合下一根木棒。3. 直到所有的小木棒都被組合完成，搜索結(jié)束。http:/blog.csd n.n et/night_

4、blue/article/details/2966056思路二：1.le n=maxai & len |sum(ai)2. 為了避免重復(fù)搜索，令每個(gè)大S的組成中，小S的長(zhǎng)度依次遞減，這樣就需要在搜索之前對(duì)ai排序；全部的大 S的第一段小S依次遞減3. 如果在某層搜索中，嘗試將aj加入到第i個(gè)大S的組成中，如果最終aj沒(méi)有被使用，且aj+1=aj，不需要繼續(xù)嘗試 aj+14. 如果此次是在嘗試第i個(gè)大S的第一段小S aj，aj為當(dāng)前可以被使用的最長(zhǎng)的小S,如果此次嘗試失敗，直接退出搜索，即退回到對(duì)第 i-1個(gè)大S的搜索。試想：失敗說(shuō)明現(xiàn)在使 用aj是不可行的，那么什么時(shí)候使用aj呢？如果沒(méi)有退出

5、搜索，肯定會(huì)在之后的搜索中使用aj，因?yàn)樗械男必須都使用。之后的aj和最初嘗試的aj有什么不同呢？沒(méi)有不 同，它們等價(jià)，因此之后也不會(huì)成功，不需要繼續(xù)搜索。都一致：先對(duì)這些數(shù)進(jìn)行排序；1. #in elude 2. #in elude 3. using n amespaee std;4.4. int sticks64, n, len, num;(num 為可以得到多少對(duì))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:當(dāng)前已經(jīng)計(jì)算的木棒編號(hào)，left:該段還剩的長(zhǎng)度，level:已經(jīng)成功的木棒 數(shù)15. if(left = 0) /匹配一根木棒成功16. if(level = num-2)17. returntrue;18. for(eur = 0; usedeur; eur+)/ 找到第一個(gè)還沒(méi)被用的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. 不行的話(huà)，就不會(huì)使用這個(gè)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. 四對(duì)括號(hào)可以有多少種匹配排列方式？比如兩對(duì)括號(hào)可以有兩種：()()和()卡特蘭數(shù)(Catalan)例子1:Cn=n對(duì)括號(hào)正確匹配組成的字符串?dāng)?shù)，例如3對(duì)括號(hào)能夠組成：()()() ()()() ()()()()例子2 : Cn= n+1個(gè)數(shù)相乘，所有的括號(hào)方案數(shù)。例如，4個(gè)數(shù)相乘的括號(hào)方案為：(ab)c)d(a(bc)d (ab)(cd) a(bc)d) a(b(cd)例

10、子3： Cn=擁有n+1個(gè)葉子節(jié)點(diǎn)的二叉樹(shù)的數(shù)量。例如4個(gè)葉子節(jié)點(diǎn)的所有二叉樹(shù)形態(tài)：分析：卡特蘭數(shù)”除了可以使用 公式計(jì)算Cn=C (n，2n)-C( n-1，2n)，也可以采用分級(jí)排列法”來(lái)求解。以n對(duì)括弧的合法匹配為例，對(duì)于一個(gè)序列()而言，有兩個(gè)左括弧，和一個(gè)右括弧，可以看成 抵消了一對(duì)括弧，還剩下一個(gè)左括弧等待抵消”，那么說(shuō)明還可以在末尾增加一個(gè)右括弧，或者一個(gè)左括弧，沒(méi)有左括弧剩余的時(shí)候，不能添加右括弧。arr = new doublen + 1;/arr 代表有k個(gè)括弧的時(shí)候，剩余(個(gè)數(shù)為i的排列方案?jìng)€(gè)數(shù)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位置的這些括號(hào)的最大組成種數(shù)，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結(jié)尾的最長(zhǎng)遞增子序列長(zhǎng)度。代碼如下：/*maxLenlnc

12、ri表示以i結(jié)尾的最大遞增子串長(zhǎng)度*/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. 一種分情況的二分：首先觀察這個(gè)序列，先下降，然后突然上升(暫且叫斷點(diǎn)吧)，接著又下降，而且有個(gè)性質(zhì)(* )斷點(diǎn)前面的所有數(shù)都比斷點(diǎn)后面的所有數(shù)小！令當(dāng)前二分的區(qū)間是l,h，那么這個(gè)區(qū)間有 3中可能性：(1) 落在斷點(diǎn)前的那個(gè)下降區(qū)間里面；(2) 落在斷點(diǎn)后的那個(gè)下降區(qū)間里面；(3 )跨區(qū)間。我們看怎么判斷當(dāng)前落在哪個(gè)區(qū)間里，另a是原來(lái)的數(shù)組如果al ah，由性質(zhì)(*)得到不可能是跨區(qū)間的(否則因?yàn)镮在斷點(diǎn)前的區(qū)間,h在斷點(diǎn)后的區(qū)間，那么肯定有alah)，那么只可能是(1)或者(2)，這樣這個(gè)區(qū)間就是普通的下降區(qū)間，用常規(guī)的二分在這個(gè)區(qū)間