Java移除无效括号的方法实现

目录

一、题目

给你一个由 ‘(‘、’)’ 和小写字母组成的字符串 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移除无效括号内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！