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

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

Easy 找出字符串中第一个只出现一次的字符

简要题意

如题。

Solution

先扫一遍字符串，记录每个字母出现次数，再扫一遍找第一个合法字母就好。

Code

void R()
{
	string s;
	cin>>s;
	map<char,int> cnt;
	for (char c:s) cnt[c]++;
	for (char c:s)
		if (cnt[c]==1)
		{
			cout<<c;
			return;
		}
	cout<<"-1\n";
	return;
}

Medium 字符统计

简要题意

将在字符串中出现过的字符按出现次数为第一关键字，ASCII 码为第二关键字排序。

Solution

跟 EZ 差不多，只不过第二次按 ASCII 序遍历。

Code

void R()
{
	int n,k,ans=0;
	cin>>n>>k;
	queue<int> q;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	sort(a.begin(),a.end());
	for (int x:a)
	{
		q.push(x);
		while (abs(q.front()-x)>k)
			q.pop();
		ans=max(ans,int(q.size()));
	}
	cout<<ans;
	return;
}

Hard 相差不超过k的最多数

简要题意

给一个数组，求最多能选多少个数使得所选所有数的极差不超过 。

Solution

对数组排序，我们选出的一定是连续的一段。

用 queue 维护已选数，如果首尾相差超过 就把队首出队，过程中队列最大长度就是答案。

Code

void R()
{
	int n,k,ans=0;
	cin>>n>>k;
	queue<int> q;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	sort(a.begin(),a.end());
	for (int x:a)
	{
		q.push(x);
		while (x-q.front()>k)
			q.pop();
		ans=max(ans,int(q.size()));
	}
	cout<<ans;
	return;
}