牛客春招刷题训练营 - 2025.3.14 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 字符个数统计

简要题意

数一个字符串中的互异字符数。

Solution

标记一下每个字符是否见过即可。

Code

void R()
{
	map<char,bool> vis;
	string s;
	cin>>s;
	for (char c:s)
		vis[c]=1;
	cout<<vis.size()<<'\n';
	return;
}

Medium 删除字符串中出现次数最少的字符

简要题意

如标题所述。

Solution

记录一下各个字符出现次数，取出最小值，再输出原字符串。

特别地，如果当前输出字符的出现次数等于最小值，将其跳过。

Code

void R()
{
	vector<int> vis(26);
	string s;
	cin>>s;
	for (char c:s)
		vis[c-'a']++;

	int mn=1e9;
	for (int i=0;i<26;i++)
		if (vis[i])
			mn=min(mn,vis[i]);
	for (char c:s)
		if (vis[c-'a']!=mn)
			cout<<c;
	return;
}

Hard 四则运算

简要题意

给一个简单的算术表达式，求其结果。

Solution

还是小模拟。

其实编程求后缀表达式值比求中缀更容易，所以我直接把它转成后缀。

具体来说就是：

用一个栈存符号，遍历中缀表达式。

如果遍历到的是数字，直接丢进表达式；

如果遍历到的是算术运算符，把栈顶优先级不低于它的运算符丢进表达式（遇到左括号也要停下），自己进栈；

如果遍历到的是左括号，直接丢进栈里；

如果遍历到的是右括号，一直弹栈到最近的左括号，弹出来的符号都插进表达式里。

需要留意的是负号 or 减号的处理：如果原表达式中 - 前面不是数字也不是右括号，就说明它是负号，否则就是减号。负号前面补个 就可以一起处理。

对于后缀表达式，它没有烦人的括号，我们遇到一个算符就把最近两个数拿来算就好。

Code

void R()
{
	string s;
	cin>>s;
	vector<int> sgn,val,exp;
	constexpr int S=1e3+7;

	auto isr=[&](char c)->bool
	{
		return c==')'||c==']'||c=='}';
	};

	for (int i=0;i<s.size();i++)
	{
		char c=s[i];
		if (isdigit(c))
		{
			if (i&&isdigit(s[i-1]))
			{
				exp.back()*=10;
				exp.back()+=c-'0';
			}
			else exp.push_back(c-'0');
		}
		else if (isr(c))
		{
			while (sgn.back()!=S)
			{
				exp.push_back(sgn.back());
				sgn.pop_back();
			}
			sgn.pop_back();
		}
		else if (c=='+'||c=='-')
		{
			while (!sgn.empty()&&sgn.back()!=S)
			{
				exp.push_back(sgn.back());
				sgn.pop_back();
			}
			if (c=='-'&&(!i||(!isdigit(s[i-1])&&!isr(s[i-1]))))
				exp.push_back(0);
			sgn.push_back(c=='+'?S+1:S+2);
		}
		else if (c=='*'||c=='/')
		{
			while (!sgn.empty()&&sgn.back()>S+2)
			{
				exp.push_back(sgn.back());
				sgn.pop_back();
			}
			sgn.push_back(c=='*'?S+3:S+4);
		}
		else sgn.push_back(S);
	}
	while (!sgn.empty())
	{
		exp.push_back(sgn.back());
		sgn.pop_back();
	}

	for (int x:exp)
	{
		if (x<S)
			val.push_back(x);
		else
		{
			int p=val.back();
			val.pop_back();
			if (x==S+1)
				val.back()+=p;
			else if (x==S+2)
				val.back()-=p;
			else if (x==S+3)
				val.back()*=p;
			else
				val.back()/=p;
		}
	}
	cout<<val.back();
	return;
}