东城响应式网站建设亿速云

链接：

https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal/

题意：

给定字符串s1,s2，仅由x,y组成

每次可以在两边各挑一个字符交换

求让s1等于s2的最小步骤

解：

1000啊1000，双指针贪一下就过了

优先选择xx组合yy，只需要一步，然后处理xy和yx

然后发现好像太敷衍了，又想了想

在预先处理掉不需要考虑的位置（原来就相同的位置）情况下

可以发现，剩下的如果是偶数位，一定可以换完，因为任意两位一定含有2x2y，因为s1[i]!=s2[i]

所以判断一下新字符串长度，得出是否为-1

然后算一下每位上xy和yx的数量，因为花费一步可以解决两个xy或者两个yx，花费两步就是解决一个xy+yx，优先做费用一步的操作，数量为xy/2+yx/2

然后做费用两步的操作，由于总数为偶数，所以用xy%2*2，如果有剩余的xy就一定会有对应的yx

ans为xy/2+yx/2+xy%2*2

实际代码：

贪：

#include<iostream>
using namespace std;
int solve(string s1, string s2)
{int ans=0;int lg1=s1.length(),lg2=-1;string t1,t2;for(int i=0;i<lg1;i++){if(s1[i]!=s2[i]){t1+=s1[i];t2+=s2[i];}}lg2=t1.length();//处理掉不需要处理的位置 //cout<<t1<<" and "<<t2<<endl;for(int i=0;i<lg2;i++){if(t1[i]=='-' || t2[i]=='-') continue;for(int j=i+1;j<lg2;j++){if(t1[j]=='-' || t2[j]=='-') continue;string temp1,temp2;temp1=temp1+t1[i]+t1[j];temp2=temp2+t2[i]+t2[j];cout<<temp1<<" "<<temp2<<endl;if((temp1=="xx" && temp2=="yy")||(temp1=="yy" && temp2=="xx")){ans+=1;t1[i]=t1[j]=t2[i]=t2[j]='-';}}}//步骤一 处理所有一步的移动 //cout<<"step1 done!"<<endl;//cout<<t1<<" "<<t2<<endl;for(int i=0;i<lg2;i++){if(t1[i]=='-' || t2[i]=='-') continue;for(int j=i+1;j<lg2;j++){if(t1[j]=='-' || t2[j]=='-') continue;string temp1,temp2;temp1=temp1+t1[i]+t1[j];temp2=temp2+t2[i]+t2[j];cout<<temp1<<" "<<temp2<<endl;if((temp1=="xy" && temp2=="yx")||(temp1=="yx" && temp2=="xy")){ans+=2;t1[i]=t1[j]=t2[i]=t2[j]='-';}}}//步骤二 处理所有两步的移动 //cout<<"step2 done!"<<endl;//cout<<t1<<" "<<t2<<endl;for(int i=0;i<lg2;i++){if(t1[i]!='-'||t2[i]!='-'){ans=-1;break;}}//步骤三 检查是否全部处理完毕 //cout<<"step3 done!"<<endl;return ans;
}
int main()
{string s1,s2;cin>>s1>>s2;int ans=solve(s1,s2);cout<<ans<<endl;
}

改：

#include<iostream>
using namespace std;
int solve(string s1, string s2)
{int ans=0;int lg1=s1.length(),lg2=-1;string t1,t2;for(int i=0;i<lg1;i++){if(s1[i]!=s2[i]){t1+=s1[i];t2+=s2[i];}}lg2=t1.length();//处理掉不需要处理的位置 //cout<<t1<<" and "<<t2<<endl;int xy=0,yx=0;for(int i=0;i<lg2;i++){if(t1[i]=='x' && t2[i]=='y'){xy++;}else yx++;}//已知去除了不需要处理的位置//任意两位上都是2x2y不会出现处理不了的问题//判断是否是奇数位需要处理，即会剩下一个xy//if((xy+yx)%2==1) return -1;//奇数位？奇数位！ if(lg2%2==1) return -1;return xy/2+yx/2+xy%2*2;
}
int main()
{string s1,s2;cin>>s1>>s2;int ans=solve(s1,s2);cout<<ans<<endl;
}

限制：

• 1 <= s1.length, s2.length <= 1000
• s1, s2 只包含 'x' 或 'y'。