打印n对括号的全部有效组合(即左右括号正确配对)
打印n对括号的全部有效组合(即左右括号正确配对)
一贱书生 发表于1年前
打印n对括号的全部有效组合(即左右括号正确配对)
  • 发表于 1年前
  • 阅读 60
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

/**
 * 功能:打印n对括号的全部有效组合(即左右括号正确配对)。

 */

 

两种方法:

方法一:

[java] view plain copy

 

  1. /** 
  2.  * 思路:在括号的最前面或者原有的每对括号里面插入一对括号。至于其他任意位置,比如字符串的末尾,都会跟之前的情况重复。 
  3.  * 注意:将字符串放进结果列表之前,必须检查列表有无重复。 
  4.  * @param remaining 
  5.  * @return 
  6.  */  
  7. public static HashSet<String> generateParens(int remaining){  
  8.     HashSet<String> set=new HashSet<String>();  
  9.       
  10.     if(remaining==0)  
  11.         set.add("");  
  12.     else{  
  13.         HashSet<String> prev=generateParens(remaining-1);  
  14.         for(String str:prev){  
  15.             //括号内插入  
  16.             for(int i=0;i<str.length();i++){  
  17.                 if(str.charAt(i)=='('){  
  18.                     String s=insertInside(str,i);  
  19.                     set.add(s);//插入元素之前,HashSet会自动检查有无重复  
  20.                 }  
  21.             }  
  22.             //括号最前面插入  
  23.             if(!set.contains("()"+str))  
  24.                 set.add("()"+str);  
  25.         }  
  26.     }                 
  27.     return set;       
  28. }  
  29.   
  30. /** 
  31.  * 在每对括号内插入 
  32.  * @param str 
  33.  * @param leftIndex 
  34.  * @return 
  35.  */  
  36. public static String insertInside(String str,int leftIndex){  
  37.     String left=str.substring(0,leftIndex+1);//左括号之后插入括号,所以需要leftIndex+1  
  38.     String right=str.substring(leftIndex+1);  
  39.     return left+"()"+right;  
  40. }  

 

 

方法二:

 

[java] view plain copy

 

  1. /** 
  2.  * 思路:从头开始构造字符串,避免出现重复字符串。注意加入左括号和右括号,只要字符串仍然有效。 
  3.  * 每次递归调用,都有一个索引指向字符串的某个字符。选择左括号和右括号: 
  4.  *      1)左括号:只要左括号还没有用完,就可以插入左括号。 
  5.  *      2)右括号:只要不造成语法错误,就可以插入右括号(右括号比左括号多,即语法错误)。 
  6.  * 因此,只需记录允许插入的左右括号数目。如果还有左括号可用,就插入一个左括号,然后递归。 
  7.  * 如果后括号比左括号多,(即使用中的左括号比右括号多),就插入一个右括号,然后递归。 
  8.  *  
  9.  * 在字符串的每一个索引对应位置插入左括号和右括号,而且绝对不会重复索引!!! 
  10.  * @param count 
  11.  * @return 
  12.  */  
  13. public static ArrayList<String> generateParens2(int count){  
  14.     ArrayList<String> list=new ArrayList<String>();  
  15.     char[] str=new char[count*2];  
  16.     addParens(list,count,count,str,0);  
  17.       
  18.     return list;  
  19. }  
  20.   
  21. public static void addParens(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {  
  22.     // TODO Auto-generated method stub  
  23.     if(leftRem<0||rightRem<leftRem)  
  24.         return;  
  25.       
  26.     if(leftRem==0&&rightRem==0){  
  27.         String s=String.copyValueOf(str);  
  28.         list.add(s);  
  29.     }  
  30.       
  31.     if(leftRem>0){  
  32.         str[count]='(';  
  33.         addParens(list, leftRem-1, rightRem, str, count+1);  
  34.     }  
  35.       
  36.     if(rightRem>leftRem){  
  37.         str[count]=')';  
  38.         addParens(list, leftRem, rightRem-1, str, count+1);  
  39.           
  40.     }  
共有 人打赏支持
粉丝 16
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: