米鼠商城

多快好省,买软件就上米鼠网

最新项目

人才服务

靠谱的IT人才垂直招聘平台

程序设计思维与实践 Week5 作业 C-平衡字符串

  • Ellison
  • 7
  • 2020-03-24 08:24

题目链接:C-平衡字符串

题目描述: 一个长度为 n 的字符串 s,其中仅包含 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符。 如果四种字符在字符串中出现次数均为 n/4,则其为一个平衡字符串。 现可以将 s 中连续的一段子串替换成相同长度的只包含那四个字符的任意字符串,使其变为一个平衡字符串,问替换子串的最小长度? 如果 s 已经平衡则输出0。

Input: 一行字符表示给定的字符串s

Output: 一个整数表示答案

Sample Input-1: QWER

Sample Output-1: 0

Sample Input-2: QQWE

Sample Output-2: 1

Sample Input-3: QQQW

Sample Output-3: 2

Sample Input-4: QQQQ

Sample Output-4: 3

Note: 1<=n<=10^5 n是4的倍数 字符串中仅包含字符 ‘Q’, ‘W’, ‘E’ 和 ‘R’.

思路: 本题中要选择连续的最小字符串,而不是直接统计每个字母对于n/4的差距。但是统计差距还是必要的过程。解题采用尺取法,即设计头尾双指针,通过判断首尾之间的字符串接受替换之后字符串是否保持平衡。在程序编写中,自定义change函数完成"QWER"四个字符和对应数字的映射,用acc数组保存累积的字符数,flag函数判断acc数组是否已经满足要求。进行尺取过程中,如果acc满足条件就执行移动过程,然后用首尾坐标相减并+2(表示首尾两个位置),得出最小替换字符串。复杂度是O(n)。

总结: 见到题目时还以为是之前的方法,然后发现不对路,在课上学习尺取法时还在关注前面的内容,然后重新回顾了一遍,发现这种类似遍历数组的方法实则缩小了复杂度。每种做题方法都是优化程序的,而做题的关键是发现本题应用哪种方法,现在作业知道往哪一方面靠拢,但是随机出题就不能保证方法正确了。

代码:

#include<iostream>
#include<string.h>
using namespace std;
int count[4],acc[4];
bool used[100005];
int ans=1e+5;
string s;
int change(char ch){
    if(ch=='Q')
    	return 0;
    else if(ch=='W')
    	return 1;
    else if(ch=='E')
    	return 2;
    else if(ch=='R')
    	return 3;
    return -1;
}
bool flag(){
	for(int i=0;i<4;i++)
		if(count[i]>acc[i])
			return false;
	return true;
}
int balance(){
	int head=0,tail=0;
    for(int i=0;i<s.length();i++){
    	if(s[i]=='Q')
    		count[0]++;
    	else if(s[i]=='W')
    		count[1]++;
    	else if(s[i]=='E')
    		count[2]++;
    	else if(s[i]=='R')
    		count[3]++;
    	else break;
    }
    for(int i=0;i<4;i++){
    	if(count[i]>s.length()/4)
    		count[i]-=s.length()/4;
    	else
    		count[i]=0;
    }
    if(!count[0]&&!count[1]&&!count[2]&&!count[3])
    	return 0;
    while(head<s.length()){
    	int op=change(s[head]);
    	if(count[op]){
    		acc[op]++;
    		if(flag()){
    			while(tail<=head){
    				op=change(s[tail]);
    				tail++;
    				if(count[op])
    					acc[op]--;
    				if(!flag())
    					break;
    			}
    			ans=min(ans,head-tail+2);
    		}
    	}
    	head++;
    }
    return ans;
}
int main()
{
	cin>>s;
	memset(count, 0, sizeof(count));
	memset(acc, 0, sizeof(acc));
	cout<<balance()<<endl;
	return 0;
}


这里给大家推荐一个在线软件复杂项交易平台:米鼠网 https://www.misuland.com

米鼠网自成立以来一直专注于从事软件项目人才招聘软件商城等,始终秉承“专业的服务,易用的产品”的经营理念,以“提供高品质的服务、满足客户的需求、携手共创双赢”为企业目标,为中国境内企业提供国际化、专业化、个性化、的软件项目解决方案,我司拥有一流的项目经理团队,具备过硬的软件项目设计和实施能力,为全国不同行业客户提供优质的产品和服务,得到了客户的广泛赞誉。



如有侵权请联系邮箱(service@misuland.com)

猜你喜欢

评论留言