怎样​根据一个整数生成括号对数-创新互联

这篇文章给大家分享的是一道根据一个整数生成括号对数的题目。文章使用多种方法实现这道题，小编觉得挺实用的，因此分享给大家做个参考。一起跟随小编过来看看吧。

1 题目

根据一个整数生成所有的有效的括号组合,这个整数表示括号的对数.

2 暴力法

对于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;
}

首先加上左括号,进入下一轮递归,同时把加括号的位置加1,然后到达2n长度后,判断是否有效,有效的话加入结果数组,然后回到上一层的递归,把当前位置的括号换成右括号,接着再次进入下一轮递归,一样直到2n长度,继续判断是否有效,这样不断递归就会枚举了所有的组合.

看来不太理想啊.

3 深搜

深搜的话是暴力的改进,暴力的话不管序列是什么状态都直接添加括号,而深搜的话,当序列有效时才添加括号.
添加左括号的条件:当前的左括号数量小于n.
添加右括号的条件:当前左括号的数量小于右括号的数量.

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为上一次递归的结果,l,r分别表示左括号与右括号的数量,递归的结束条件是左右括号的数量均为n,继续递归的条件是左右括号的数量小于n.

4 动态规划

设f(n)表示n对括号的所有有效序列,则有

具体来说:

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

这三个都是三对括号的有效序列,因此f(3)最后的结果是这三个有效序列组成的数组.
因为f(n)不一定为一个有效序列,因此返回值为一个数组,剩下的只需要遍历这个数组,把它们添加到最终结果数组中去:

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对括号的所有有效序列,然后只需要遍历这两个序列,在两边加上左括号与右括号即可.

这个...好像没有深搜快.

5 动规优化

上面的递归的动规没有保存之前计算过的结果,比如计算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次

当n增大时,计算的重复度会变得更大,因此可以考虑用一个数组存储之前计算的结果,需要时直接取出来即可.

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,因为s保存了0到n的所有结果,所以,直接get即可.
然后设置一个临时的n1,表示当前要计算的n1对括号的序列,当n1增加时,表示已经完成了计算n1对括号的序列,t为结果,添加到s中去.直到n1与n相等,计算完最后一个n1后,直接返回s的最后一个序列.

嗯,快了1ms,看来优化还是有效果的.

关于根据一个整数生成括号对数的方法就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果喜欢这篇文章，不如把它分享出去让更多的人看到。

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。