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

华为2020届实习生笔试第二题

程序员文章站 2022-07-13 14:27:37
...
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

//程序的时间复杂度为num*repeat
bool leftbracket(char a)
{
	if ((a =='(') || (a=='{') || (a=='['))
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool rightbracket(char b)
{
	if ((b == ')') || (b == '}') || (b == ']'))
	{
		return true;
	}
	else
	{
		return false;
	}
}

stack <int> lef;
vector <int> rig;
int main()
{
	string str;
	cin >> str;

	//通过之前对这道题的分析,我选中通过下标对字符串进行操作
	int len = str.size();
	if (len > 100)
		return 0;
	//先遍历整个字符串,找到括号(){}[]的下标
	for (int i = 0; i < len; i++)
	{
		if ( leftbracket(str[i]) )
		{
			lef.push(i);
		}

		if (rightbracket(str[i]))
		{
			rig.push_back(i);
		}
	}
	rig.push_back(0);//防止越界
	rig.push_back(0);//防止越界
	int num = lef.size();//字符串中括号的个数
	if (num == 0)
	{
		reverse(str.begin(), str.end());
		cout << str << endl;
		return 0;
	}

	for (int j = 0 ; j < num ; j++)
	{
		int begin = lef.top();//左括号最右边的
		int end = rig[j];//右括号最左边的
		int repeat = str[begin - 1]-'0';//括号里字符重复的个数
		string temp = "";
		string temp1 = "";
		temp = str.substr(begin + 1,end-begin-1);//将括号里面的字符提取出来
		int n = temp.size();//括号里字符的长度
		for (int k = 0; k < repeat; k++)
		{
			temp1 = temp1 + temp;
		}
		str.erase(begin-1, end - begin +2);//将str字符串里面括号及括号里面的字符删除
		str.insert(begin - 1, temp1);//将字符串重复reapeat次后,再插入字符串
		lef.pop();
		if (j<num-1)
		{

			if ((3 + n) >= (n*repeat))
			{
				rig[j + 1] = rig[j + 1] - 3 - n + n*repeat;//当删除插入字符后,后续的右括号的下标都改变了
				rig[j + 2] = rig[j + 2] - 3 - n + n*repeat;//改变后续右括号的字符下标
			}

			if ((3 + n) < (n*repeat))
			{
				rig[j + 1] = rig[j + 1] - 3 - n + n*repeat;
				rig[j + 2] = rig[j + 2] - 3 - n + n*repeat;
			}
		}
	}
	reverse(str.begin(),str.end());
	cout << str << endl;
	system("pause");
	return 0;
}


上一篇: 大小端

下一篇: 大小端