文档章节

打印n对括号的全部有效组合(即左右括号正确配对)

一贱书生
 一贱书生
发布于 2016/11/22 10:39
字数 598
阅读 60
收藏 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.     }  

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
XYNUOJ 1792 括号配对问题

1792: 括号配对问题时间限制: 3 Sec 内存限制: 64 MB 提交: 39 解决: 19 [提交][状态][讨论版] 题目描述 现在,有一行括号序列,请你检查这行括号是否配对。 输入 第一行输入一个数N(0...

dear_jia
04/12
0
0
第五周 项目3 - 括号的匹配

【项目 - 括号的匹配】 假设表达式中允许三种括号:圆括号、方括号和大括号。编写一个算法,判断表达式中的各种左括号是否与右括号匹配。 例如,输入2+(3+4)2+{[3]}-8,输出匹配正确;输入2...

a18560280409
2017/12/13
0
0
Jzoj4209 已经没有什么好害怕的了

小Y 最近开始学习算法姿势,但是因为小R 非常BB,给了她很多B6 题,所以她觉得自己已经没有什么前途了。 于是小R 给了她一些稍微简单的题,让她觉得已经没有什么好害怕的了,其中一道是这样的...

JacaJava
01/17
0
0
LeetCode 22. Generate Parentheses(括号生成)

原题 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: 题目: 给出 n 代表生成括......

dby_freedom
09/25
0
0
Leetcode打卡 | No.22 括号生成

No.22 括号生成 题目 : 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。 例如,给出 n = 3,生成结果为: 这一题和之前一题看起来类似 ,但难度...

技术小能手
08/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS 安装PHP5和PHP7

安装PHP5 下载解压二进制包 [root@test-a src]# cd /usr/local/src/[root@test-a src]# wget http://cn2.php.net/distributions/php-5.6.32.tar.bz2[root@test-a src]# tar jxvf php-5.6......

野雪球
51分钟前
3
0
windows上类似dnsmasq的软件Dual DHCP DNS Server

官网地址:http://dhcp-dns-server.sourceforge.net/官网定向的下载地址:https://sourceforge.net/projects/dhcp-dns-server/files/ 设置参考地址:http://blog.51cto.com/zhukeqiang/18264......

xueyuse0012
今天
3
0
LinkedHashMap源码解析

前言 HashMap中的元素时无序的,也就是说遍历HashMap的时候,顺序和放入的顺序是不一样的。 如果需要有序的Map,就可以采用LinkedHashMap. LinkedHashMap通过维护一个包含所有元素的双向链表,...

grace_233
今天
3
0
初识flask

文档 0.10.1版本 http://www.pythondoc.com/flask/index.html 1.0.2版本 https://dormousehole.readthedocs.io/en/latest/ 安装flask $ pip3 install flaskCollecting flask Downloading......

yimingkeji
昨天
5
0
Akka系统《sixteen》译

Actor是一个封装状态(state)和行为(behavior)的对象,它们只通过交换消息通信(放入收件人邮箱的邮件)。从某种意义上说,Actor是最严格的面向对象编程形式,但它更适合将他们视为人:在与Act...

woshixin
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部