文档章节

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

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

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 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
【算法系列 二】Stack

栈应用的场景: 1.括号问题 2.后缀表达式 3.深度优先遍历 4.保存现场 1. 给定字符串,仅由“()[]{}”六个字符组成。设计算法,判断该字符串是否有效。 括号必须以正确的顺序配对,如“()”、...

Hosee
2016/03/01
90
0
C语言中使用大括号与给函数命名的正确方法(转载)

使用大括号的正确方法: 在C中,使用大括号的方法无所谓对还是错——只要每个开括号后都有一个闭括号,你的程序中就不再会出现与大括号有关的问题。然而,有三种著名的大括号格式经常被使用:...

oldpan
2014/07/30
0
0
数据结构中用栈解决的问题

假设表达式中允许包括三种括号:圆括号,方括号,大括号。编写一算法,判断表达式中的括号是否正确配对。利用数据结构中的栈

鲁琴
2013/03/27
128
5
Catalan数(卡特兰数)

由于Catalan数经常会在算法题或面试题中出现,在这里做一下小小的总结。 介绍 Catalan数是组合数学中一个常在各种计数问题中出现的数列。一般项公式为 Cn的另一个表达形式为 一般来讲,我们编...

Hosee
2015/12/07
124
0
玩转文件搜索利器-----find!!!

1.What is find? 在linux当中用于文件搜索的命令主要用两个,一个是locate,另一个就是find。我们平常使用最多就是find命令,现在我们就来一步步学习find命令,刚刚接触到find命令的同学可能...

Becaning
2014/03/05
0
0
求24点,算术式解析

题目: 给定任意4个正整数,利⽤用加,减,乘,除,括号这⼏几个运算符,编程计 算所有由这4个数字计算出24的表达式,并输出计算表达式。 输出结果要求:加法,乘法需要去重,(( a + b ) c)...

梦想游戏人
2016/10/26
47
0
正则表达式应用替换/删除/校验/测试技巧

正则表达式应用替换/删除/校验/测试技巧 实例目录 【1】 正则表达式应用——替换指定内容到行尾 【2】 正则表达式应用——数字替换 【3】 正则表达式应用——删除每一行行尾的指定字符 【4】...

sinat_34719507
2017/01/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周一乱弹 —— 如果是你喜欢的女同学找你借钱

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @guanglun :分享Michael Learns To Rock的单曲《Fairy Tale》 《Fairy Tale》- Michael Learns To Rock 手机党少年们想听歌,请使劲儿戳(这...

小小编辑
37分钟前
9
3
NNS域名系统之域名竞拍

0x00 前言 其实在官方文档中已经对域名竞拍的过程有详细的描述,感兴趣的可以移步http://doc.neons.name/zh_CN/latest/nns_protocol.html#id30 此处查阅。 我这里主要对轻钱包开发中会用到的...

暖冰
今天
0
0
32.filter表案例 nat表应用 (iptables)

10.15 iptables filter表案例 10.16/10.17/10.18 iptables nat表应用 10.15 iptables filter表案例: ~1. 写一个具体的iptables小案例,需求是把80端口、22端口、21 端口放行。但是,22端口我...

王鑫linux
今天
0
0
shell中的函数&shell中的数组&告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析

影夜Linux
今天
0
0
Linux网络基础、Linux防火墙

Linux网络基础 ip addr 命令 :查看网口信息 ifconfig命令:查看网口信息,要比ip addr更明了一些 centos 7默认没安装ifconfig命令,可以使用yum install -y net-tools命令来安装。 ifconfig...

李超小牛子
今天
1
0
[机器学习]回归--Decision Tree Regression

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很...

wangxuwei
昨天
1
0
Redis做分布式无锁CAS的问题

因为Redis本身是单线程的,具备原子性,所以可以用来做分布式无锁的操作,但会有一点小问题。 public interface OrderService { public String getOrderNo();} public class OrderRe...

算法之名
昨天
11
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
昨天
1
0
数据结构与算法1

第一个代码,描述一个被称为BankAccount的类,该类模拟了银行中的账户操作。程序建立了一个开户金额,显示金额,存款,取款并显示余额。 主要的知识点联系为类的含义,构造函数,公有和私有。...

沉迷于编程的小菜菜
昨天
1
0
从为什么别的队伍总比你的快说起

在机场候检排队的时候,大多数情况下,别的队伍都要比自己所在的队伍快,并常常懊悔当初怎么没去那个队。 其实,最快的队伍只能有一个,而排队之前并不知道那个队快。所以,如果有六个队伍你...

我是菜鸟我骄傲
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部