Java怎么移除无效的括号

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

目录

• 一、题目
  

• 二、示例
  

• 三、解法1
  

• 四、解法2
  

一、题目

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

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

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

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

二、示例

))((  -》   (leetode  -》  leetode leetode)  -》  leetode (lee(to)de  -》  lee(to)de lee(to)de)  -》  lee(to)de (lee(t(c)o)de  -》  lee(t(c)o)de lee(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怎么移除无效的括号这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！