欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

去除最少括号输出合法的括号字符串

程序员文章站 2022-06-16 09:16:21
 今天去福田的一家公司面试,某某奇公司。让我做一道算法题,大概这样:要求写一个函数,输入参数为一个字符串,含有小写字母和’(’,’)'字符,要求去掉最少的括号是字符串成为一个合法的括号字符串。例如:输入"))(("输出""输入"nc(kjn(d)ca))"输出"nc(kjn(d)ca)“或"nc(kjn(dca))”。 反正就是要让括号能匹配,成对出现。我当时就懵了,因为算法一直没怎么研究,最近几天都是在看cocos引擎部分,昨天还看了android。我知道可以用stack来解决括号匹配的问题...

 今天去福田的一家公司面试,某某奇公司。让我做一道算法题,大概这样:
要求写一个函数,输入参数为一个字符串,含有小写字母和’(’,’)'字符,要求去掉最少的括号使字符串成为一个合法的括号字符串。
例如:
输入"))(("
输出""
输入"nc(kjn(d)ca))"
输出"nc(kjn(d)ca)" 或"nc(kjn(dca))" 。
 反正就是要让括号能匹配,成对出现。我当时就懵了,因为算法一直没怎么研究,最近几天都是在看cocos引擎部分,昨天还看了android。我知道可以用stack来解决括号匹配的问题,以前有看过检测括号是否匹配的算法,但有点忘了,而且这个不是单纯检测是否合法,还要去除最少括号。最后还是没做出来。然后也没应聘上。
下午回家躺床上在想这个问题,想着想着就想出来了。代码如下:

//用数组模拟栈
char *minMoveToValidArray(char *str){
	int nNum = strlen(str);

	char *stackCh = new char[nNum];
	char *strTemp = new char[nNum+1];
	
	char *pStr = strTemp;
	int nCurIndex = 0;
	for (int i = 0; i < nNum;++i)
	{
		if (str[i]=='(')
		{
			//放入左括号
			stackCh[nCurIndex++] = str[i];

			*pStr++ = str[i];
		}else if (str[i]==')')
		{
			if (nCurIndex==0|| stackCh[nCurIndex-1]!='(')
			{
				//舍弃右括号
			}
			else{
				//放入右括号
				--nCurIndex;
				*pStr++ = str[i];
			}
		}else{
			//放入非括号字符
			*pStr++ = str[i];
		}
	}
	*pStr = '\0';

	int nMax = strlen(strTemp);
	int nLeftCount = nCurIndex;
	int nCount = nCurIndex;
	if (nCount == 0)
	{
		//没有需要去除的左括号
		strcpy_s(str, nNum + 1, strTemp);
		str[nNum] = '\0';
	}
	else{
		//最后需要去除后面那些无法匹配的左括号
		for (int i = nMax - 1, j = nMax - 1 - nCount; i >= 0; --i)
		{

			if (strTemp[i] != '(' || nLeftCount <= 0)
			{
				str[j--] = strTemp[i];
			}
			else if (nLeftCount>0){
				--nLeftCount;
			}
		}
		str[nMax - nCount] = '\0';
	}

	delete strTemp;
	delete stackCh;

	return str;
}

//用到栈结构
char *minMoveToValidStack(char *str){
	int nNum = strlen(str);

	stack<char> stackCh;
	
	char *strTemp = new char[nNum + 1];

	char *pStr = strTemp;
	int nCurIndex = 0;
	for (int i = 0; i < nNum; ++i)
	{
		if (str[i] == '(')
		{
			//放入左括号
			stackCh.push(str[i]);
			*pStr++ = str[i];
		}
		else if (str[i] == ')')
		{
			if (stackCh.empty() || stackCh.top() != '(')
			{
				//舍弃右括号
			}
			else{
				//放入右括号
				stackCh.pop();
				*pStr++ = str[i];
			}
		}
		else{
			//放入非括号字符
			*pStr++ = str[i];
		}
	}
	*pStr = '\0';

	int nMax = strlen(strTemp);
	int nLeftCount = stackCh.size();
	int nCount = nLeftCount;
	if (nCount == 0)
	{
		//没有需要去除的左括号
		strcpy_s(str, nNum + 1, strTemp);
		str[nNum] = '\0';
	}
	else{
		//最后需要去除后面那些无法匹配的左括号
		for (int i = nMax - 1, j = nMax - 1 - nCount; i >= 0; --i)
		{
			if (strTemp[i] != '(' || nLeftCount <= 0)
			{
				str[j--] = strTemp[i];
			}
			else if (nLeftCount > 0){
				--nLeftCount;
			}
		}
		str[nMax - nCount] = '\0';
	}

	delete []strTemp;

	return str;
}

 基本思路就是遍历字符串,如果是非括号字符或者左括号的话就放到目标字符串里,如果是右括号的话就判断能否跟栈顶的括号配对,可以的话也放进目标字符串里,不可以的话就说明是需要舍弃的,就不放进去。到最后的话目标字符串的后面可能有一些左括号没匹配,也需要将它们去除,最后剩下的就是我们需要的字符串了。
 简单测试了几下,都能输出正确结果,也没做优化。如果有错误请赐教。
ps:最后想吐槽一次,用纸写代码真反人类。


以下是题外话。
虽然面试没成功,但遇到了以前公司的同事,他在这公司里做没多久,感谢他认出了我,叫住了我。我在离开的时候心情不好闷头走,是有听到有人叫我名字,但我以为是听错了就没回头。最后还是他跑出来追我。他人挺nice的。聊了几句,最后加了wx。让我心情也没那么郁闷了。缘分真是一个圆。

本文地址:https://blog.csdn.net/dan452819043/article/details/114328534

相关标签: C++ 算法