【每日一题】—— B. Ternary String （Educational Codeforces Round 87 (Rated for Div. 2)）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】—— B. Ternary String （Educational Codeforces Round 87 (Rated for Div. 2)）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🌏博客主页：PH_modest的博客主页
🚩当前专栏：每日一题
💌其他专栏：
🔴 每日反刍
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.题目描述

题目大意：给你一串由1、2、3组成的数组，让你求一个最短的子串，要求这个子串包含1、2、3

题目链接：B. Ternary String （Educational Codeforces Round 87 (Rated for Div. 2)）

二.思路分析

双指针

用指针L，R来遍历数组，判断L和R区间内是否有满足条件的字串，如果有将它和上一次的比较存下较小的，然后左指针L往右移动，继续判断，缩小范围 ~~（小写的L不太看得清，就用大写的方便友友们看思路）~~

三.代码展示

//双指针
//用指针l，r来遍历数组，判断l和r区间内是否有满足条件的字串，如果有将它和上一次的比较存下较小的，然后左指针l往右移动，继续判断，缩小范围
//
#include<iostream>
#include<cstring>
#define int long long
using namespace std;

char s[200020];

void solve()
{
	int a=0,b=0,c=0;//记录1,2,3出现的次数
	int l=0,r=0;
	int mins=1e9;
	cin>>s;
	while(r<=strlen(s))//由于数据较小，可以直接遍历
	{
		if(a&&b&&c)//处理这段包含1、2、3的数列，将l往后移动一个，并且减去原来l位置上数字的个数
		{
			if(s[l]=='1')a--;
			if(s[l]=='2')b--;
			if(s[l]=='3')c--;
			l++;
		}
		else//如果还没有找到一段包含1,2,3的序列，r就继续往后找
		{
			if(s[r]=='1') a++;
			if(s[r]=='2') b++;
			if(s[r]=='3') c++;
			r++;
		}
		if(a&&b&&c)//a,b,c都不为0说明当前序列包含了1,2,3
		{
			int ret=r-l;//计算当前序列的长度
			mins=min(ret,mins);//和上一次进行比较，存储较小的值
		}
	}
	if(mins==1e9)//如果mins没有变还是原来赋值的1e9，说明数组中没有这样的序列，直接返回0
	{
		cout<<"0"<<"\n";
	}
	else
	{
		cout<<mins<<"\n";
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

最后：

每日一题系列旨在养成刷题的习惯，所以对代码的解释并不会特别详细，但足够引导大家写出来，选的题目都不会特别难，但也不是特别简单，比较考验大家的基础和应用能力，我希望能够将这个系列一直写下去，也希望大家能够和我一起坚持每天写代码。

之后每个星期都会不定期更新codeforces和atcoder上的题目，想要学习算法的友友们千万别错过了，有什么疑问欢迎大家在评论区留言！

今天晚上cf有div.3的比赛，想第一时间看到题目解析的就赶紧关注我呦~
之后基本上每场比赛比完第二天都会出前几题的题目解析哦~

在这里送大家一句话：广积粮，缓称王！文章来源地址https://www.toymoban.com/news/detail-604958.html

到了这里，关于【每日一题】—— B. Ternary String （Educational Codeforces Round 87 (Rated for Div. 2)）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！