Luna Tech

Tutorials For Dummies.

删除最外层的括号(Leetcode)

2020-12-30


1. 题目

https://leetcode-cn.com/problems/remove-outermost-parentheses/

https://leetcode.com/problems/remove-outermost-parentheses/

去除一个字符串里面的最外层括号,字符串只包括 () 这两个字符。


2. 思路

思路 1 - 利用 stack

  1. 用 stack 来存左括号,遇到右括号之后 pop 一个左括号;
  2. pop 之后 stack 为空,就证明找到了最外层的右括号;
  3. 如当前 stack count 大于 0,说明现在处于里层,需要把这个字符存起来;

实现 1

这是第一次的实现,用了两个 stack,一个是存括号的,一个是存 character index 的。


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 判断顺序,我们必须先去掉右括号,再决定是否要把当前字符加入最终结果,这个判断结束之后再把左括号加进去。

为什么要用这个顺序呢?

所以我们要先 pop,再判断 count,最后 push。


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 这两个比较,第一个用的是后++,第二个用的是前–。

区别在于:

也就是说,当我们输入 () 的时候,left++ > 0 会保证左括号不被加入最终结果(先用后算, 0 > 0 不成立,left = 0+1 = 1); 而 –left > 0 会保证右括号不被加入最终结果(因为先算后用,left = 1-1 = 0,0 > 0 不成立); 这样也就能保证最外层的括号不被加入最终结果了~


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)

注意点

延伸阅读

  1. C# array vs arraylist
  2. C# array vs arraylist vs list

简单来说:

  1. Array 是长度固定的对象,定义之后不能改变长度,可以改变元素的值,所有元素类型一致;
  2. ArrayList 长度不固定,可以增减元素,元素类型可以不一致;
  3. List 介于两者之间,保证了元素类型一致,且长度可以被改变;
// 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);

结语

欢迎大家分享更好的解法~