练习题替换子串得到平衡字符串-Toy模板网

这篇具有很好参考价值的文章主要介绍了练习题替换子串得到平衡字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

示例 1：

输入：s = "QWER"
输出：0
解释：s 已经是平衡的了。

示例 2：

输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

示例 3：

输入：s = "QQQW"
输出：2
解释：我们可以把前面的 "QQ" 替换成 "ER"。

示例 4：

输入：s = "QQQQ"
输出：3
解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。

提示：

1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符

提交代码

//替换子串得到平衡字符串 

//只含四种已定字符
//求替换子串的最小长度 
//平衡子串的四种字符的个数都是相等的
//字符串长度确定是4的倍数
//连续一段元素的群体关系
//滑动窗口 
//首先遍历字符串，明确四种字符的个数

#include<iostream>
#include<string>
#include<algorithm>
using namespace std; 

string s;//字符串
int result = (int)(1e5);//结果 
int n;//字符串长度 
int cnt[4];//四种字符的个数
int m = 0;//需要修改的字符的个数 

//判断指针指向的字符是什么
int judge(int p){
	if(s[p] == 'Q'){
		return 0;
	}else if(s[p] == 'W'){
		return 1;
	}else if(s[p] == 'E'){
		return 2;
	}else{
		return 3;
	}
} 

//滑动窗口
void slidingWindow(){
	int left = 0,right = 0;//左右指针
	//int mm = m;//已修改的字符的个数
	int c;//标记是哪种字符
	int res = 0;//记录子串长度 
	int t[4];//各字符个数的副本
	
	//复制字符个数副本
	copy(begin(cnt),end(cnt),begin(t));
	
	//先单独判断第一个字符
	c = judge(left);
	if(cnt[c] > n / 4){
		t[c]--;
		m--;
	} 
	
	//循环尝试固定左指针
	for(;left < n && left <= right;left++){
		//移动右指针 
		while(m > 0 && right < n - 1){
			//还未替换完
			right++;
			//判断新并入的字符是哪一个
			c = judge(right);
			if(t[c] > n / 4){
				//该字符需要替换
				m--;
				t[c]--; 
			}else{
				t[c]--;
			}
		}
		
		//当前替换子串长度
		if(m == 0){
			res = right - left + 1;
			result = min(res,result);
		}else{
			break;
		}
		
		//printf("left=%d,right=%d\n",left,right);	
		
		//排除最左侧的字符
		c = judge(left);
		if(cnt[c] > n / 4){
			//被替换过
			t[c]++;
			m++; 
			
			if(t[c] <= n / 4){
				m = 0;
			}
		}
		
		//printf("m=%d,res=%d\n",m,res);	
	} 
} 

int main(){
	//输入整数数组  
	/*int t; 
	
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		nums1.push_back(t);
	}*/
	
	//输入字符串
	cin >> s; 
	
	//-------------------------------
	
	n = s.size();//字符串长度 
	
	//确认四种字符的个数
	for(int i = 0;i < n;i++){
		if(s[i] == 'Q'){
			cnt[0]++;
		}else if(s[i] == 'W'){
			cnt[1]++;
		}else if(s[i] == 'E'){
			cnt[2]++;
		}else{
			cnt[3]++;
		}
	} 
	
	//确定需要修改的次数
	for(int i = 0;i < 4;i++){
		if(cnt[i] > n / 4){
			m += cnt[i] - n / 4;
		}
	}
	
	if(m == 0 || m == 1){
		//特殊情况
		result = m; 
	}else{
		//一般情况
		//滑动窗口
		slidingWindow(); 
	}
	
	//输出结果
	printf("%d",result);
	
	return 0;
}

总结

解题思路：替换一个子串其实就是改变一段连续元素的群体关系，故使用滑动窗口（同向双指针）。注意当舍去最左侧元素且该最左侧元素变化了的时候，新生成的子串可能仍成立，因为剩余子串中仍可能含有该元素但是未变。

注意：

将一个数组的所有元素复制到另一个数组中，可以使用copy(begin(nums1),end(nums1),begin(nums2));文章来源地址https://www.toymoban.com/news/detail-802706.html

到了这里，关于练习题替换子串得到平衡字符串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！