1. 题目
https://leetcode-cn.com/problems/remove-outermost-parentheses/
https://leetcode.com/problems/remove-outermost-parentheses/
去除一个字符串里面的最外层括号，字符串只包括 ( 和 ) 这两个字符。
() => 空字符串((())) => (())(()()) => ()()(()())(()) => ()()()
2. 思路
思路 1 - 利用 stack
- 用 stack 来存左括号，遇到右括号之后 pop 一个左括号；
- pop 之后 stack 为空，就证明找到了最外层的右括号；
- 如当前 stack count 大于 0，说明现在处于里层，需要把这个字符存起来；
实现 1
这是第一次的实现，用了两个 stack，一个是存括号的，一个是存 character index 的。
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
|
public class Solution
{
public string RemoveOuterParentheses(string S)
{
Stack<char> stack = new Stack<char>();
Stack<int> toRemove = new Stack<int>();
List<char> arr = S.ToCharArray().ToList();
int start = 0;
int end = 0;
for (int i = 0; i < arr.Count(); i++){
char c = arr[i];
if (c == '('){
if (stack.Count() == 0)
start = i;
stack.Push(c);
}
else
{
stack.Pop();
if (stack.Count() == 0)
{
// found a primitive parenthese
end = i;
toRemove.Push(start);
toRemove.Push(end);
}
}
}
while (toRemove.Count() > 0)
arr.RemoveAt(toRemove.Pop());
StringBuilder sb = new StringBuilder();
sb.Append(arr.ToArray());
return sb.ToString();
}
}
|
实现 2
参考了别人的解题思路之后，发现不需要分为两步（找 index，去除 character），而是可以在遍历 char array 的时候直接根据 count 来 build string。
这个方法里面最重要的就是 foreach 里面的 if 判断顺序，我们必须先去掉右括号，再决定是否要把当前字符加入最终结果，这个判断结束之后再把左括号加进去。
为什么要用这个顺序呢？
- 假如当前字符是最外层的左括号，那么在这个左括号加入 stack 之前，stack count 一定等于 0；
- 假如当前字符是最外层的右括号，那么在 pop 之前，stack count 一定大于 0；
所以我们要先 pop，再判断 count，最后 push。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class Solution
{
public string RemoveOuterParentheses(string S)
{
StringBuilder sb = new StringBuilder();
Stack<char> stack = new Stack<char>();
char[] arr = S.ToCharArray();
foreach (char c in arr)
{
if (c == ')')
stack.Pop();
if (stack.Count() > 0)
sb.Append(c);
if (c == '(')
stack.Push(c);
}
return sb.ToString();
}
}
|
思路 2. 计算剩余括号数量
这个思路比较巧妙，因为根据题意，我们可以发现左括号和右括号的数量是一样的，所以就用一个专门的变量来存左括号数量，假如左括号数量大于 0 ，加入 final string。
这个解法不需要用 stack。
值得注意的是 left++ > 0 和 --left > 0 这两个比较，第一个用的是后++，第二个用的是前–。
区别在于：
- i++（后++）是先用后算，先把 i 的值用来做比较，再把 i 的值 + 1；
- ++i（前++）是先算后用，先把 i 的值 + 1，再使用这个新的值作比较；
也就是说，当我们输入 () 的时候，left++ > 0 会保证左括号不被加入最终结果（先用后算， 0 > 0 不成立，left = 0+1 = 1）；
而 –left > 0 会保证右括号不被加入最终结果（因为先算后用，left = 1-1 = 0，0 > 0 不成立）；
这样也就能保证最外层的括号不被加入最终结果了~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class Solution
{
public string RemoveOuterParentheses(string S)
{
int left = 0;
StringBuilder sb = new StringBuilder();
char[] arr = S.ToCharArray();
for (int i = 0; i < arr.Count(); i++)
{
char c = arr[i];
if (c == '(' && left++ > 0) // 先用后算，先和 0 比较，再加 1
{
sb.Append('(');
}
if (c == ')' && --left > 0) // 先算后用，先-1，再和 0 比较
sb.Append(')');
}
return sb.ToString();
}
}
|
3. 复盘
复杂度
时间复杂度：O(n)
空间复杂度：O(n)
注意点
- 用 StringBuilder 来储存结果，因为 string 是 immutable type，每操作一次就创建一个新的 string，在内存方面不如 StringBuilder 友好；
- 在【思路 1-实现 1】里面，由于 char array 不能用 RemoveAtIndex 之类的方法来去掉不需要的括号，所以我先把 char array 转成了一个 List，然后在 StringBuilder 里面转回 array；
- 前++ 是先算后用，后++是先用后算
延伸阅读
- C# array vs arraylist
- C# array vs arraylist vs list
简单来说：
- Array 是长度固定的对象，定义之后不能改变长度，可以改变元素的值，所有元素类型一致；
- ArrayList 长度不固定，可以增减元素，元素类型可以不一致；
- List 介于两者之间，保证了元素类型一致，且长度可以被改变；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// Array
int[] Array = new int[5];
for(int i = 0; i < Array.Length; i++)
{
Array[i] = i + 5;
}
Array[0] = 10;
// ArrayList
ArrayList arrayList = new ArrayList();
arrayList.Add(6);
arrayList.Add("123");
arrayList.RemoveAt(0);
// List
List<int> list = new List<int>();
list.Add(6);
list.Add(8);
list.RemoveAt(0);
|
结语
欢迎大家分享更好的解法~
