Java怎么移除无效的括号

这篇文章主要讲解了“Java怎么移除无效的括号”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Java怎么移除无效的括号”吧！

目录

• 一、题目
  

• 二、示例
  

• 三、解法1
  

• 四、解法2
  

一、题目

给你一个由 ‘('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 ‘(' 或者 ‘)' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

有效「括号字符串」应当符合以下 任意一条 要求：

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

二、示例

))((  -》  (leetode  -》  leetodeleetode)  -》  leetode(lee(to)de  -》  lee(to)delee(to)de)  -》  lee(to)de(lee(t(c)o)de  -》  lee(t(c)o)delee(t(c)o)de)  -》  lee(t(c)o)de

三、解法1

public class Test { public static void main(String[] args) {  String s1 = "))((";  System.out.println(s1 + "  -》  " + minRemoveToMakeValid(s1));  String s2 = "(leetode";  System.out.println(s2 + "  -》  " + minRemoveToMakeValid(s2));  String s3 = "leetode)";  System.out.println(s3 + "  -》  " + minRemoveToMakeValid(s3));  String s4 = "(lee(to)de";  System.out.println(s4 + "  -》  " + minRemoveToMakeValid(s4));  String s5 = "lee(to)de)";  System.out.println(s5 + "  -》  " + minRemoveToMakeValid(s5));  String s6 = "(lee(t(c)o)de";  System.out.println(s6 + "  -》  " + minRemoveToMakeValid(s6));  String s7 = "lee(t(c)o)de)";  System.out.println(s7 + "  -》  " + minRemoveToMakeValid(s7)); } public static String minRemoveToMakeValid(String str) {  // 初始化"("和")"的个数为0  int left = 0;  int right = 0;  // 将字符串转换为char数组  char[] chars = str.toCharArray();  // 从左到右标记多余的")"右括号  for (int i = 0; i < chars.length; i++) {   if (chars[i] == '(') {    left++;   } else if (chars[i] == ')') {    right++;   }   if (right > left) {    chars[i] = '#';    left = right = 0;   }  }  left = right = 0;  // 从右到左标记多余的"("左括号  for (int i = chars.length - 1; i >= 0; i--) {   if (chars[i] == '(') {    left++;   } else if (chars[i] == ')') {    right++;   }   if (right < left) {    chars[i] = '#';    left = right = 0;   }  }  return String.valueOf(chars).replaceAll("#", ""); }}

四、解法2

Stack.peek 与Sstack.pop 的区别

• 相同点：大家都返回栈顶的值。

• 不同点：peek 不改变栈的值(不删除栈顶的值)，pop会把栈顶的值删除。

public class Test { public static void main(String[] args) {  String s1 = "))((";  System.out.println(s1 + "  -》  " + minRemoveToMakeValid(s1));  String s2 = "(leetode";  System.out.println(s2 + "  -》  " + minRemoveToMakeValid(s2));  String s3 = "leetode)";  System.out.println(s3 + "  -》  " + minRemoveToMakeValid(s3));  String s4 = "(lee(to)de";  System.out.println(s4 + "  -》  " + minRemoveToMakeValid(s4));  String s5 = "lee(to)de)";  System.out.println(s5 + "  -》  " + minRemoveToMakeValid(s5));  String s6 = "(lee(t(c)o)de";  System.out.println(s6 + "  -》  " + minRemoveToMakeValid(s6));  String s7 = "lee(t(c)o)de)";  System.out.println(s7 + "  -》  " + minRemoveToMakeValid(s7)); } public static String minRemoveToMakeValid(String str) {  // 记录要删除括号的下标，然后从后往前删除坐标  StringBuffer result = new StringBuffer(str);    Stack<Integer> stack = new Stack<>();  ArrayList<Integer> deleteRes = new ArrayList<>();    for (int i = 0; i < str.length(); i++) {   if (str.charAt(i) == '(') {    stack.push(i);   } else if (str.charAt(i) == ')') {    if (stack.empty()) {     deleteRes.add(i);    } else if (str.charAt(stack.peek()) == '(') {     stack.pop();    }   }  }    while (!stack.empty()) {   int temp = stack.peek();   stack.pop();   deleteRes.add(0, temp);  }    deleteRes.sort(Integer::compareTo);    for (int i = deleteRes.size() - 1; i >= 0; i--) {   result.deleteCharAt(deleteRes.get(i));  }    return result.toString(); }}

感谢各位的阅读，以上就是“Java怎么移除无效的括号”的内容了，经过本文的学习后，相信大家对Java怎么移除无效的括号这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！