一、題目
給你一個由 ‘('、')' 和小寫字母組成的字符串 s。
你需要從字符串中刪除最少數(shù)目的 ‘(' 或者 ‘)' （可以刪除任意位置的括號)，使得剩下的「括號字符串」有效。
有效「括號字符串」應當符合以下 任意一條 要求：
空字符串或只包含小寫字母的字符串
可以被寫作 AB（A 連接 B）的字符串，其中 A 和 B 都是有效「括號字符串」
可以被寫作 (A) 的字符串，其中 A 是一個有效的「括號字符串」
二、示例
|
1
2
3
4
5
6
7
8
9
10
|
))(( -》 (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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
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) { // 初始化"("和")"的個數(shù)為0 int left = 0; int right = 0; // 將字符串轉換為char數(shù)組 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 的區(qū)別
- 相同點：大家都返回棧頂?shù)闹怠?/li>
- 不同點：peek 不改變棧的值(不刪除棧頂?shù)闹?，pop會把棧頂?shù)闹祫h除。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
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移除無效括號的方法實現(xiàn)的文章就介紹到這了,更多相關Java移除無效括號內容請搜索服務器之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://xiaoer.blog.csdn.net/article/details/115921023
