Java怎么移除無效的括號(hào)

這篇文章主要講解了“Java怎么移除無效的括號(hào)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Java怎么移除無效的括號(hào)”吧！

目錄

• 一、題目
  

• 二、示例
  

• 三、解法1
  

• 四、解法2
  

一、題目

給你一個(gè)由 ‘('、')' 和小寫字母組成的字符串 s。

你需要從字符串中刪除最少數(shù)目的 ‘(' 或者 ‘)' （可以刪除任意位置的括號(hào))，使得剩下的「括號(hào)字符串」有效。

有效「括號(hào)字符串」應(yīng)當(dāng)符合以下 任意一條 要求：

空字符串或只包含小寫字母的字符串
可以被寫作 AB（A 連接 B）的字符串，其中 A 和 B 都是有效「括號(hào)字符串」
可以被寫作 (A) 的字符串，其中 A 是一個(gè)有效的「括號(hào)字符串」

二、示例

))((  -》  

(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) {
  // 初始化"("和")"的個(gè)數(shù)為0
  int left = 0;
  int right = 0;

  // 將字符串轉(zhuǎn)換為char數(shù)組
  char[] chars = str.toCharArray();

  // 從左到右標(biāo)記多余的")"右括號(hào)
  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;

  // 從右到左標(biāo)記多余的"("左括號(hào)
  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 的區(qū)別

• 相同點(diǎn)：大家都返回棧頂?shù)闹怠?/p>

• 不同點(diǎn)：peek 不改變棧的值(不刪除棧頂?shù)闹?，pop會(huì)把棧頂?shù)闹祫h除。

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) {
  // 記錄要?jiǎng)h除括號(hào)的下標(biāo)，然后從后往前刪除坐標(biāo)
  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怎么移除無效的括號(hào)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)Java怎么移除無效的括號(hào)這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！