笔记|第十二届蓝桥杯——Java软件开发（省赛）（括号序列（笔记15））数据结构|算法|字符串|java

第十二届蓝桥杯——Java软件开发（省赛）：括号序列【问题描述】: 给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几
种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。
【输入格式】: 输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。
【输出格式】: 输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 (109 + 7) 的余数。
【样例输入】: ((()
【样例输出】: 5
【评测用例规模与约定】：对于 40% 的评测用例，|s| ≤ 200。
对于所有评测用例，1 ≤ |s| ≤ 5000。
【代码展示】：（这次注释写的挺多，应该没问题）

import java.util.HashSet; import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next(); int n = run1(str); StringBuffer sb = new StringBuffer(str); String target=""; //存要添加的括号类型（ or ） if(n<0) {//若n<0，表示）比（多，应补（ target="("; }else if(n>0) {//相反 target=")"; } n = Math.abs(n); //n可能为负数，取绝对值 run2(sb,n,target); System.out.println(hashset.size()%((int)Math.pow(10, 9)+7)); } //判断 static Stack> stack = new Stack>(); private static boolean check(StringBuffer sb) { stack.clear(); //节省空间，每次清除上次的残留 for(int i=0; i.length(); i++) { if((sb.charAt(i))=='('){//如果是（括号，入栈 stack.push("("); }else if(sb.charAt(i)==')'){//如果是）括号 if(stack.size()==0) {//如果当前符号为）括号，且栈空，说明没有与之匹配的（括号，不合格，返回false return false; }else { stack.pop(); //...，栈不是空，存在可匹配的（括号，栈弹出顶元素即可 } } } if(stack.size()==0) {//经过一轮操作，若栈为空，匹配成功，返回true return true; }else { return false; //经过一轮操作，若栈不为空，意味着栈中还有（括号，则匹配失败，返回false } } //插入符号 static HashSet> hashset = new HashSet>(); //保存插入后满足括号匹配的字符串（HashSet自动去重，不过线程不安全，这里不影响）， private static void run2(StringBuffer sb, int n, String target) { if(n<=0) {//当n<=0时，意味着已经完成一次插入，接下来进行判断即可 boolean f = check(sb); if(f) { hashset.add(sb.toString()); //满足条件，添加到hashset中 } return; } for(int i=0; i.length(); i++) { StringBuffer temp = new StringBuffer(sb.toString()); //每次应该创一个sb的副本进行操作（易错点！！！！一开始我也这里错的） temp.insert(i, target); //将target插到temp的位置i run2(temp,n-1,target); //这个就不用解释了吧 } } //查看最少缺几个括号 private static int run1(String str) { int count1=0; //统计左括号 int count2=0; //同理 for(int i=0; i.length(); i++) { if(str.charAt(i)=='(') { count1++; } if(str.charAt(i)==')') { count2++; } } return count1-count2; } }

【笔记|第十二届蓝桥杯——Java软件开发（省赛）（括号序列（笔记15））】总结：用到了栈（用于判断），HashSet（保存结果），递归（循环插入），题目不是很难，和以前做过的括号匹配很类似，又要看的我找找然后发出来。
今天学习到这里结束（考研的一个晚上，想码点程序出来放松放松哈哈），溜了溜了…