這篇文章給大家分享的是一道根據(jù)一個整數(shù)生成括號對數(shù)的題目。文章使用多種方法實(shí)現(xiàn)這道題，小編覺得挺實(shí)用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。
根據(jù)一個整數(shù)生成所有的有效的括號組合,這個整數(shù)表示括號的對數(shù).
對于n對括號,總共2n個字符,每個字符可以為左括號或右括號,所以總共2^(2n)中組合,暴力法就是枚舉各個組合,然后判斷它們是否為有效的組合:
重慶分公司
重慶分公司
public void f(char c[],int pos,List result)
{
if(pos == c.length)
{
if(valid(c))
result.add(Arrays.toString(c).replaceAll("(\\[)|(\\])| |,",""));
}
else
{
c[pos] = '(';
f(c,pos+1,result);
c[pos] = ')';
f(c,pos+1,result);
}
}
public boolean valid(char [] f)
{
int len = 0;
for(char c:f)
{
if(c == '(' )
{
if(++len > f.length/2)
return false;
}
else if(len-- <=0)
return false;
}
return len == 0;
} 首先加上左括號,進(jìn)入下一輪遞歸,同時把加括號的位置加1,然后到達(dá)2n長度后,判斷是否有效,有效的話加入結(jié)果數(shù)組,然后回到上一層的遞歸,把當(dāng)前位置的括號換成右括號,接著再次進(jìn)入下一輪遞歸,一樣直到2n長度,繼續(xù)判斷是否有效,這樣不斷遞歸就會枚舉了所有的組合.
看來不太理想啊.
深搜的話是暴力的改進(jìn),暴力的話不管序列是什么狀態(tài)都直接添加括號,而深搜的話,當(dāng)序列有效時才添加括號.
添加左括號的條件:當(dāng)前的左括號數(shù)量小于n.
添加右括號的條件:當(dāng)前左括號的數(shù)量小于右括號的數(shù)量.
public void f(String c,int n,int l,int r,List result)
{
if(l == n && r == n)
result.add(c);
else
{
if(l < r)
return ;
if(l < n)
f(c+"(",n,l+1,r,result);
if(r < n)
f(c+")",n,l,r+1,result);
}
} c為上一次遞歸的結(jié)果,l,r分別表示左括號與右括號的數(shù)量,遞歸的結(jié)束條件是左右括號的數(shù)量均為n,繼續(xù)遞歸的條件是左右括號的數(shù)量小于n.
設(shè)f(n)表示n對括號的所有有效序列,則有
具體來說:
f(3) = ( + f(0) + ) + f(2)
f(3) = ( + f(1) + ) + f(1)
f(3) = ( + f(2) + ) + f(0)這三個都是三對括號的有效序列,因此f(3)最后的結(jié)果是這三個有效序列組成的數(shù)組.
因?yàn)閒(n)不一定為一個有效序列,因此返回值為一個數(shù)組,剩下的只需要遍歷這個數(shù)組,把它們添加到最終結(jié)果數(shù)組中去:
public List f(int n)
{
List s = new ArrayList<>();
if(n == 0)
s.add("");
for(int i=0;i l = f(i);
List r = f(n-i-1);
for(String ll:l)
{
for(String rr:r)
{
s.add("("+ll+")"+rr);
}
}
}
return s;
} 若n為0,添加一個空序列然后返回,若n不為0,l表示i對括號的所有有效序列,r表示n-i-1對括號的所有有效序列,然后只需要遍歷這兩個序列,在兩邊加上左括號與右括號即可.
這個...好像沒有深搜快.
上面的遞歸的動規(guī)沒有保存之前計算過的結(jié)果,比如計算n=3的時候,
f(3) = ( + f(0) + ) + f(2)
f(3) = ( + f(1) + ) + f(1)
f(3) = ( + f(2) + ) + f(0)f(2):
f(2) = ( + f(1) + ) + f(0)
f(2) = ( + f(0) + ) + f(1)f(1)
f(1) = ( + f(0) + ) + f(0)只是計算f(3),計算了
f(2):2次
f(1):2+2*2=6次
f(0):2+2*2+6*2=18次當(dāng)n增大時,計算的重復(fù)度會變得更大,因此可以考慮用一個數(shù)組存儲之前計算的結(jié)果,需要時直接取出來即可.
public List generateParenthesis(int n)
{
List> s = new ArrayList<>();
s.add(Arrays.asList(""));
s.add(Arrays.asList("()"));
for(int n1 = 2;n1<=n;++n1)
{
List t = new ArrayList<>();
for(int i=0;i l = s.get(i);
List r = s.get(n1-i-1);
for(String ll:l)
{
for(String rr:r)
{
t.add("("+ll+")"+rr);
}
}
}
s.add(t);
}
return s.get(n);
} 可以先看最后的return,因?yàn)閟保存了0到n的所有結(jié)果,所以,直接get即可.
然后設(shè)置一個臨時的n1,表示當(dāng)前要計算的n1對括號的序列,當(dāng)n1增加時,表示已經(jīng)完成了計算n1對括號的序列,t為結(jié)果,添加到s中去.直到n1與n相等,計算完最后一個n1后,直接返回s的最后一個序列.
嗯,快了1ms,看來優(yōu)化還是有效果的.
關(guān)于根據(jù)一個整數(shù)生成括號對數(shù)的方法就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果喜歡這篇文章，不如把它分享出去讓更多的人看到。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
