两个公司的网站建设,做网站有钱,网站空间 按流量计费,wordpress gif封面链接#xff1a;
https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal/
题意#xff1a;
给定字符串s1,s2#xff0c;仅由x,y组成
每次可以在两边各挑一个字符交换
求让s1等于s2的最小步骤
解#xff1a;
1000啊1000#xff0c;双指针贪一下就过了 …链接
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花费两步就是解决一个xyyx优先做费用一步的操作数量为xy/2yx/2
然后做费用两步的操作由于总数为偶数所以用xy%2*2如果有剩余的xy就一定会有对应的yx
ans为xy/2yx/2xy%2*2
实际代码
贪
#includeiostream
using namespace std;
int solve(string s1, string s2)
{int ans0;int lg1s1.length(),lg2-1;string t1,t2;for(int i0;ilg1;i){if(s1[i]!s2[i]){t1s1[i];t2s2[i];}}lg2t1.length();//处理掉不需要处理的位置 //coutt1 and t2endl;for(int i0;ilg2;i){if(t1[i]- || t2[i]-) continue;for(int ji1;jlg2;j){if(t1[j]- || t2[j]-) continue;string temp1,temp2;temp1temp1t1[i]t1[j];temp2temp2t2[i]t2[j];couttemp1 temp2endl;if((temp1xx temp2yy)||(temp1yy temp2xx)){ans1;t1[i]t1[j]t2[i]t2[j]-;}}}//步骤一 处理所有一步的移动 //coutstep1 done!endl;//coutt1 t2endl;for(int i0;ilg2;i){if(t1[i]- || t2[i]-) continue;for(int ji1;jlg2;j){if(t1[j]- || t2[j]-) continue;string temp1,temp2;temp1temp1t1[i]t1[j];temp2temp2t2[i]t2[j];couttemp1 temp2endl;if((temp1xy temp2yx)||(temp1yx temp2xy)){ans2;t1[i]t1[j]t2[i]t2[j]-;}}}//步骤二 处理所有两步的移动 //coutstep2 done!endl;//coutt1 t2endl;for(int i0;ilg2;i){if(t1[i]!-||t2[i]!-){ans-1;break;}}//步骤三 检查是否全部处理完毕 //coutstep3 done!endl;return ans;
}
int main()
{string s1,s2;cins1s2;int anssolve(s1,s2);coutansendl;
}改
#includeiostream
using namespace std;
int solve(string s1, string s2)
{int ans0;int lg1s1.length(),lg2-1;string t1,t2;for(int i0;ilg1;i){if(s1[i]!s2[i]){t1s1[i];t2s2[i];}}lg2t1.length();//处理掉不需要处理的位置 //coutt1 and t2endl;int xy0,yx0;for(int i0;ilg2;i){if(t1[i]x t2[i]y){xy;}else yx;}//已知去除了不需要处理的位置//任意两位上都是2x2y不会出现处理不了的问题//判断是否是奇数位需要处理即会剩下一个xy//if((xyyx)%21) return -1;//奇数位奇数位 if(lg2%21) return -1;return xy/2yx/2xy%2*2;
}
int main()
{string s1,s2;cins1s2;int anssolve(s1,s2);coutansendl;
}限制
1 s1.length, s2.length 1000s1, s2 只包含 x 或 y。
