判断有多少组有效括号
package com.parker.example;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* @Author: Parker
* @CreateTime: 2020-07-17 16:08
* @Description: 判断有多少组有效括号 - 刷题
*/
public class Test5 {
/** 前缀 */
private static char PREFIX = '(';
/** 后缀 */
private static char POSTFIX = ')';
public static void main(String[] args) {
String s = ") ((( ((( )";
String s1 = "((() ((( ((( ))))";
int count;
// 暴力解法
//count = m1(s);
// 压栈解法
count = m2(s1);
System.out.println(count);
}
/**
* 暴力求解
* @param s
* @return
*/
public static int m1(String s) {
int count = 0;
// 非法判断
if(s.length() < 1){
return count;
}
// 匹配寄存器
Map<Integer,Integer> cMap = new HashMap<>(s.length());
for (int i = 0; i < s.length(); i++) {
// 为 )直接跳过
if(s.charAt(i) != PREFIX){
continue;
}
for (int k = 1+i; k < s.length(); k++) {
if(s.charAt(k) == POSTFIX && cMap.get(k) == null){
count++;
// 后缀起始计数器
cMap.put(k,k);
break;
}
}
}
return count;
}
/**
* 压栈求解
* @param s
* @return
*/
public static int m2(String s){
int count = 0;
// 非法判断
if(s.length() < 1){
return count;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
// 如果是 ( 压栈
if(s.charAt(i) == PREFIX){
stack.push(s.charAt(i));
}else if(s.charAt(i) == POSTFIX){
if(!stack.isEmpty()){
char peek = stack.peek();
if(PREFIX == peek){
count++;
// 出栈
stack.pop();
}
}
}
}
return count;
}
}
我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=1dhp3tfisfirp