怎樣?根據(jù)一個(gè)整數(shù)生成括號(hào)對(duì)數(shù)-創(chuàng)新互聯(lián)

這篇文章給大家分享的是一道根據(jù)一個(gè)整數(shù)生成括號(hào)對(duì)數(shù)的題目。文章使用多種方法實(shí)現(xiàn)這道題，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧。

創(chuàng)新互聯(lián)公司致力于網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè),成都網(wǎng)站設(shè)計(jì),集團(tuán)網(wǎng)站建設(shè)等服務(wù)標(biāo)準(zhǔn)化，推過(guò)標(biāo)準(zhǔn)化降低中小企業(yè)的建站的成本，并持續(xù)提升建站的定制化服務(wù)水平進(jìn)行質(zhì)量交付，讓企業(yè)網(wǎng)站從市場(chǎng)競(jìng)爭(zhēng)中脫穎而出。 選擇創(chuàng)新互聯(lián)公司，就選擇了安全、穩(wěn)定、美觀的網(wǎng)站建設(shè)服務(wù)！

1 題目

根據(jù)一個(gè)整數(shù)生成所有的有效的括號(hào)組合,這個(gè)整數(shù)表示括號(hào)的對(duì)數(shù).

2 暴力法

對(duì)于n對(duì)括號(hào),總共2n個(gè)字符,每個(gè)字符可以為左括號(hào)或右括號(hào),所以總共2^(2n)中組合,暴力法就是枚舉各個(gè)組合,然后判斷它們是否為有效的組合:

public void f(char c[],int pos,List<String> 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;
}

首先加上左括號(hào),進(jìn)入下一輪遞歸,同時(shí)把加括號(hào)的位置加1,然后到達(dá)2n長(zhǎng)度后,判斷是否有效,有效的話(huà)加入結(jié)果數(shù)組,然后回到上一層的遞歸,把當(dāng)前位置的括號(hào)換成右括號(hào),接著再次進(jìn)入下一輪遞歸,一樣直到2n長(zhǎng)度,繼續(xù)判斷是否有效,這樣不斷遞歸就會(huì)枚舉了所有的組合.

看來(lái)不太理想啊.

3 深搜

深搜的話(huà)是暴力的改進(jìn),暴力的話(huà)不管序列是什么狀態(tài)都直接添加括號(hào),而深搜的話(huà),當(dāng)序列有效時(shí)才添加括號(hào).
添加左括號(hào)的條件:當(dāng)前的左括號(hào)數(shù)量小于n.
添加右括號(hào)的條件:當(dāng)前左括號(hào)的數(shù)量小于右括號(hào)的數(shù)量.

public void f(String c,int n,int l,int r,List<String> 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分別表示左括號(hào)與右括號(hào)的數(shù)量,遞歸的結(jié)束條件是左右括號(hào)的數(shù)量均為n,繼續(xù)遞歸的條件是左右括號(hào)的數(shù)量小于n.

4 動(dòng)態(tài)規(guī)劃

設(shè)f(n)表示n對(duì)括號(hào)的所有有效序列,則有

具體來(lái)說(shuō):

f(3) = ( + f(0) + ) + f(2)
f(3) = ( + f(1) + ) + f(1)
f(3) = ( + f(2) + ) + f(0)

這三個(gè)都是三對(duì)括號(hào)的有效序列,因此f(3)最后的結(jié)果是這三個(gè)有效序列組成的數(shù)組.
因?yàn)閒(n)不一定為一個(gè)有效序列,因此返回值為一個(gè)數(shù)組,剩下的只需要遍歷這個(gè)數(shù)組,把它們添加到最終結(jié)果數(shù)組中去:

public List<String> f(int n)
{
   List<String> s = new ArrayList<>();
   if(n == 0)
     s.add("");
   for(int i=0;i<n;++i)
   {
     List<String> l = f(i);
     List<String> r = f(n-i-1);
     for(String ll:l)
     {
       for(String rr:r)
       {
         s.add("("+ll+")"+rr);
       }
     }
   }
   return s;
}

若n為0,添加一個(gè)空序列然后返回,若n不為0,l表示i對(duì)括號(hào)的所有有效序列,r表示n-i-1對(duì)括號(hào)的所有有效序列,然后只需要遍歷這兩個(gè)序列,在兩邊加上左括號(hào)與右括號(hào)即可.

這個(gè)...好像沒(méi)有深搜快.

5 動(dòng)規(guī)優(yōu)化

上面的遞歸的動(dòng)規(guī)沒(méi)有保存之前計(jì)算過(guò)的結(jié)果,比如計(jì)算n=3的時(shí)候,

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)

只是計(jì)算f(3),計(jì)算了

f(2):2次
f(1):2+2*2=6次
f(0):2+2*2+6*2=18次

當(dāng)n增大時(shí),計(jì)算的重復(fù)度會(huì)變得更大,因此可以考慮用一個(gè)數(shù)組存儲(chǔ)之前計(jì)算的結(jié)果,需要時(shí)直接取出來(lái)即可.

public List<String> generateParenthesis(int n) 
{
   List<List<String>> s = new ArrayList<>();
   s.add(Arrays.asList(""));
   s.add(Arrays.asList("()"));
   for(int n1 = 2;n1<=n;++n1)
   {
     List<String> t = new ArrayList<>();
     for(int i=0;i<n1;++i)
     {
       List<String> l = s.get(i);
       List<String> 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è)置一個(gè)臨時(shí)的n1,表示當(dāng)前要計(jì)算的n1對(duì)括號(hào)的序列,當(dāng)n1增加時(shí),表示已經(jīng)完成了計(jì)算n1對(duì)括號(hào)的序列,t為結(jié)果,添加到s中去.直到n1與n相等,計(jì)算完最后一個(gè)n1后,直接返回s的最后一個(gè)序列.

嗯,快了1ms,看來(lái)優(yōu)化還是有效果的.

關(guān)于根據(jù)一個(gè)整數(shù)生成括號(hào)對(duì)數(shù)的方法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果喜歡這篇文章，不如把它分享出去讓更多的人看到。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站題目：怎樣?根據(jù)一個(gè)整數(shù)生成括號(hào)對(duì)數(shù)-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)路徑：http://muchs.cn/article38/dpdepp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、虛擬主機(jī)、網(wǎng)站維護(hù)、域名注冊(cè)、企業(yè)建站、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)