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

13/13雅虎：1.關(guān)于一個整數(shù)矩陣，存在一種運算，對矩陣中任意元素加一時，需要其相鄰（上下左右）某一個元素也加一，現(xiàn)給出一正數(shù)矩陣，推斷其是否能夠由一個全零矩陣通過上述運算得到。

2.一個整數(shù)數(shù)組，長度為n，將其分為m份，使各份的和相等，求m的最大值

比如{3，2，4，3，6}能夠分成{3，2，4，3，6}m=1;

{3,6}{2,4,3}m=2

{3,3}{2,4}{6}m=3因此m的最大值為3解：poj1011，搜索+強剪枝DescriptionGeorgetooksticksofthesamelengthandcutthemrandomlyuntilallpartsbecameatmost50unitslong.Nowhewantstoreturnstickstotheoriginalstate,butheforgothowmanystickshehadoriginallyandhowlongtheywereoriginally.Pleasehelphimanddesignaprogramwhichcomputesthesmallestpossibleoriginallengthofthosesticks.Alllengthsexpressedinunitsareintegersgreaterthanzero.

OutputTheoutputshouldcontainsthesmallestpossiblelengthoforiginalsticks,oneperline.

首先講一下那個題的解題思想。1.選取某一個開始長度，開始組合小木棒，那個開始長度的限制條件為不小于木棒最大長度，不大于所有木棒長度和，能被長度和整除2.從可用的最長的那根小木棒開始組合木棒，找出所有的結(jié)果集，找到結(jié)果集后開始組合下一根木棒。3.直到所有的小木棒都被組合完成，搜索結(jié)束。/night_blue/article/details/2966056思路二：1.len>=max{a[i]}&&len|sum(a[i])

2.為了幸免重復搜索，令每個大S的組成中，小S的長度依次遞減，如此就需要在搜索之前對a[i]排序；全部的大S的第一段小S依次遞減

3.假如在某層搜索中，嘗試將a[j]加入到第i個大S的組成中，假如最終a[j]沒有被使用，且a[j+1]==a[j]，不需要接著嘗試a[j+1]

4.假如此次是在嘗試第i個大S的第一段小Sa[j]，a[j]為當前能夠被使用的最長的小S，假如此次嘗試失敗，直接退出搜索，即退回到對第i-1個大S的搜索。試想：失敗講明現(xiàn)在使用a[j]是不可行的，那么什么時候使用a[j]呢？假如沒有退出搜索，確信會在之后的搜索中使用a[j]，因為所有的小S必須都使用。之后的a[j]和最初嘗試的a[j]有什么不同呢？沒有不同，它們等價，因此之后也可不能成功，不需要接著搜索。都一致：先對這些數(shù)進行排序；#include

<iostream>

#include

<algorithm>

using

namespace

std;

int

sticks[64],

n,

len,

num;

（num為能夠得到多少對）bool

used[64];

bool

compare(int

a,

int

b)

{

return

a

>

b;

}

bool

dfs(int

cur,

int

left,

int

level)

{

//cur:

當前差不多計算的木棒編號，left:該段還剩的長度，level:差不多成功的木棒數(shù)

if(left

==

0)

{//匹配一根木棒成功

if(level

==

num-2)

return

true;

for(cur

=

0;

used[cur];

cur++)

//找到第一個還沒被用的

;

used[cur]

=

true;

if(dfs(cur+1,

len-sticks[cur],

level+1))

return

true;

used[cur]

=

false;

return

false;

}

else

{

if(cur

>=

n-1)

//最后一根了

return

false;

for(int

i

=

cur;

i

<

n;

i++)

{

if(used[i])

continue;

if((sticks[i]

==

sticks[i-1])

&&

!used[i-1])

//

continue;

if(sticks[i]

>

left)

continue;

used[i]

=

true;

if(dfs(i,

left-sticks[i],

level))

return

true;

used[i]

=

false;

//不行的話，就可不能使用那個

}

return

false;

}

}

int

main()

{

while(cin>>n)

{

if(n

==

0)

break;

int

sum

=

0;

for(int

i

=

0;

i

<

n;

i++)

{

scanf("%d",

&sticks[i]);

sum

+=

sticks[i];

}

sort(sticks,

sticks+n,

compare);

//由大到小排序

bool

end

=

false;

for(len

=

sticks[0];

len

<=

sum/2;

len++)

{

if(sum%len

==

0)

{

used[0]

=

true;

num

=

sum/len;

if(dfs(0,

len-sticks[0],

0))

{

end

=

true;

printf("%d\n",

len);

break;

}

used[0]

=

false;

}

}

if(!end)

printf("%d\n",

sum);

memset(used,

0,

sizeof(used));

}

//system("pause");

return

0;

}

搜狐：

3.四對括號能夠有多少種匹配排列方式？比如兩對括號能夠有兩種：（）（）和（（））卡特蘭數(shù)(Catalan)例子1：Cn=n對括號正確匹配組成的字符串數(shù)，例如3對括號能夠組成：((()))()(())()()()(())()(()())例子2：Cn=n+1個數(shù)相乘，所有的括號方案數(shù)。例如，4個數(shù)相乘的括號方案為：((ab)c)d(a(bc))d(ab)(cd)a((bc)d)a(b(cd))例子3：Cn=擁有n+1個葉子節(jié)點的二叉樹的數(shù)量。例如4個葉子節(jié)點的所有二叉樹形態(tài)：分析：“卡特蘭數(shù)”除了能夠使用公式計算Cn=C（n，2n）-C（n-1，2n），也能夠采納“分級排列法”來求解。以n對括弧的合法匹配為例，關(guān)于一個序列(()而言，有兩個左括弧，和一個右括弧，能夠看成“抵消了一對括弧，還剩下一個左括弧等待抵消”，那么講明還能夠在末尾增加一個右括弧，或者一個左括弧，沒有左括弧剩余的時候，不能添加右括弧。

arr=newdouble[n+1];//arr代表有k個括弧的時候，剩余"("個數(shù)為i的排列方案個數(shù)arr[1]=1;

doubleCatalan(intn)

{

if(n==0)return1;

for(inti=2;i<=2*n;i++)

{

varm=i<=n?i:2*n+1-i;

for(intj=(i-1)&1;j<=m;j+=2)

{

if(j>0)arr[j-1]+=arr[j];

if(j<n)arr[j+1]+=arr[j];

arr[j]=0;

}

}

returnarr[0];

}

創(chuàng)新工場：

4.求一個數(shù)組的最長遞減子序列比如{9，4，3，2，5，4，3，2}的最長遞減子序列為{9，5，4，3，2}

微軟：5.一個數(shù)組是由一個遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個數(shù)。

我的方法：1.講法一：網(wǎng)上有人提出兩個弱推斷條件如下：（原題的必要條件，非充要）

1)將矩陣分成黑白棋盤格,所有黑色格子的數(shù)字和等于白色格子的.

2)對任意一個位置,他的值不大于周圍(上下左右)4個臨格的數(shù)值的和.

2.poj1011，搜索+強剪枝

3.Catalon?沒驗證，然而DP能夠：dp[i][j]表示從i->j位置的這些括號的最大組成種數(shù)，dp[i][j]=dp[i-1][j-1]//i是(,j是)，同時他們搭配

+sigama(dp[i][k]*dp[k+1][j]),

i與k搭配，k+1與j搭配,

i<k<j枚舉初始條件：dp[i][i+1]=1(長度為2只能是"()")，dp[i][i]=0（長度為1不能搭配）

4.DP求LCS問題的變形確信用動態(tài)規(guī)劃來做，想了一下：前n個元素組成的子數(shù)組中的最長遞減子序列和前n+1個元素組成的子數(shù)組中最長遞減子序列沒有太大的關(guān)系；需要把問題轉(zhuǎn)化一下，再由大問題轉(zhuǎn)化為小問題；

能夠發(fā)覺以數(shù)組第n+1個元素為結(jié)尾的最長遞減子序列和以第1,2,3，。。。n個元素為結(jié)尾的最長遞減子序列長度有關(guān)系；而此序列的最長遞減子序列的長度確信是以數(shù)組第1,2,3,4n為結(jié)尾的最長遞減子序列中的最大值，so記錄一下最大值就能夠了；

首先看該問題的子問題，關(guān)于第i(i>0i<N)個元素而言，以其結(jié)尾的遞增子序列長度由前i-1個數(shù)組成的所有遞增子序列長度來決定。因此該問題就分為了i-1個子問題。maxLenIncr[i]=max{maxLenIncr[k]+1,1}if(a[i]>a[k]&&k>=0&&k<i&&i>0)maxLenIncr[0]=1;maxLenIncr[i]表示以i結(jié)尾的最長遞增子序列長度。代碼如下：/*maxLenIncr[i]表示以i結(jié)尾的最大遞增子串長度*/maxLenIncr[i]=max{maxLenIncr[k]+1ifa[i]>a[k]}(k>=0&&k<I&&i>0);intmaxLenIncr(int*p,intlen){

int*maxLenIncr=newint[len];

intmaxLen=1;

/*Defaultvalue=1*/

for(inti=0;i<len;i++)

{

maxLenIncr[i]=1;

}

for(inti=1;i<len;i++)

{

for(intk=0;k<i;k++)

{

if(a[i]>a[k])

{

maxLenIncr[i]=max(maxLenIncr[k]+1,1);

if(maxLenIncr[i]>maxLen)

max