2023-08-20：用go语言写算法。给定一个由'W'、'A'、'S'、'D'四种字符组成的字符串，长度一定是4的倍数，
你可以把任意连续的一段子串，变成'W'、'A'、'S'、'D'组成的随意状态，
目的是让4种字符词频一样。
返回需要修改的最短子串长度。
完美走位问题。
输入：s = "QQQW"。
输出：2。
解释：我们可以把前面的 "QQ" 替换成 "ER"。
来自华为OD。
来自左程云。
答案2023-08-20：
算法步骤：
1.定义辅助函数，用于判断当前字符词频是否能使四种字符的词频相同。
ok()
2.初始化数组保存每个字符的对应值（'Q': 0, 'W': 1, 'E': 2, 'R': 3）和数组记录每个字符的词频。
arr
cnts
3.使用双指针来搜索每个可能的子串。外层循环控制左指针，内层循环控制右指针。
4.当当前子串不满足要求时，右指针向右移动并更新词频数组，直到子串满足要求。
cnts
5.当子串满足要求时，更新当前最短子串长度。
6.左指针向右移动并更新词频数组，继续搜索可能的子串。
7.返回最短子串长度。
总的时间复杂度为O(n)，其中n是字符串的长度。
总的额外空间复杂度为O(1)，因为只使用了固定大小的数组和常数个变量。
go完整代码如下：
packagemain
import"fmt"
funcbalancedString(sstring)int{
n:=len(s)
arr:=make([]int,n)
cnts:=make([]int,4)
fori:=0;iswitchs[i]{
case'Q':
arr[i]=0
case'W':
arr[i]=1
case'E':
arr[i]=2
case'R':
arr[i]=3
}
cnts[arr[i]]++
}
ans:=n
forl,r:=0,0;lfor!ok(cnts,l,r)&&rcnts[arr[r]]--
r++
}
ifok(cnts,l,r){
ans=min(ans,r-l)
}else{
break
}
cnts[arr[l]]++
}
returnans
}
funcok(cnts[]int,lint,rint)bool{
maxCnt:=max(max(max(cnts[0],cnts[1]),cnts[2]),cnts[3])
changes:=maxCnt*4-cnts[0]-cnts[1]-cnts[2]-cnts[3]
rest:=r-l-changes
returnrest>=0&&rest%4==0
}
funcmin(a,bint)int{
ifareturna
}
returnb
}
funcmax(a,bint)int{
ifa>b{
returna
}
returnb
}
funcmain(){
s:="QQQW"
result:=balancedString(s)
fmt.Println(result)
}
rust完整代码如下：
fnbalanced_string(s:&str)->i32{
letn=s.len()asi32;
letmutarr=Vec::with_capacity(nasusize);
letmutcnts=vec![0;4];
forcins.chars(){
letval=matchc{
'W'=>1,
'E'=>2,
'R'=>3,
_=>0,
};
arr.push(val);
cnts[val]+=1;
}
letmutans=n;
forlin0..n{
letmutr=l;
while!ok(&cnts,l,r)&&rcnts[arr[rasusize]asusize]-=1;
r+=1;
}
ifok(&cnts,l,r){
ans=ans.min(r-l);
}else{
break;
}
cnts[arr[lasusize]asusize]+=1;
}
ans
}
fnok(cnts:&[i32],l:i32,r:i32)->bool{
letmax_cnt=cnts.iter().max().copied().unwrap_or(0);
letchanges=max_cnt*4-cnts[0]-cnts[1]-cnts[2]-cnts[3];
letrest=r-l-changes;
rest>=0&&rest%4==0
}
fnmain(){
lets="QQQW";
letresult=balanced_string(s);
println!("{}",result);
}
c++完整代码如下：
#include
#include
#include
#include
boolok(conststd::vector&cnts,intl,intr);
intbalancedString(conststd::string&str){
intn=str.size();
std::vectorarr(n);
std::vectorcnts(4);
for(inti=0;icharc=str[i];
arr[i]=(c=='W'?1:(c=='E'?2:(c=='R'?3:0)));
cnts[arr[i]]++;
}
intans=n;
for(intl=0,r=0;lwhile(!ok(cnts,l,r)&&rcnts[arr[r++]]--;
}
if(ok(cnts,l,r)){
ans=std::min(ans,r-l);
}
else{
break;
}
cnts[arr[l]]++;
}
returnans;
}
boolok(conststd::vector&cnts,intl,intr){
intmaxCnt=std::max(std::max(cnts[0],cnts[1]),std::max(cnts[2],cnts[3]));
intchanges=maxCnt*4-cnts[0]-cnts[1]-cnts[2]-cnts[3];
intrest=r-l-changes;
returnrest>=0&&rest%4==0;
}
intmain(){
std::strings="QQQW";
intresult=balancedString(s);
std::cout<<"Result:"<return0;
}
c完整代码如下：
#include
#include
#include
intbalancedString(char*s){
intn=strlen(s);
int*arr=(int*)malloc(sizeof(int)*n);
intcnts[4]={0};
for(inti=0;icharc=s[i];
arr[i]=c=='W'?1:(c=='E'?2:(c=='R'?3:0));
cnts[arr[i]]++;
}
intans=n;
for(intl=0,r=0;lwhile(!ok(cnts,l,r)&&rcnts[arr[r++]]--;
}
if(ok(cnts,l,r)){
ans=ans}
else{
break;
}
cnts[arr[l]]++;
}
free(arr);
returnans;
}
intok(int*cnts,intl,intr){
intmaxCnt=cnts[0];
for(inti=1;i<4;i++){
if(cnts[i]>maxCnt){
maxCnt=cnts[i];
}
}
intchanges=maxCnt*4-cnts[0]-cnts[1]-cnts[2]-cnts[3];
intrest=r-l-changes;
returnrest>=0&&rest%4==0;
}
intmain(){
chars[]="QQQW";
intresult=balancedString(s);
printf("%d\n",result);
return0;
}
热门跟贴