法律咨询东莞网站建设,学网站建设去什么学校,韶关市住房和城乡建设管理局网站,营口旅游网站建设有两个长度相同的字符串 s1 和 s2#xff0c;且它们其中 只含有 字符 x 和 y#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候#xff0c;你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个…有两个长度相同的字符串 s1 和 s2且它们其中 只含有 字符 x 和 y你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间绝对不能发生在同一个字符串内部。也就是说我们可以交换 s1[i] 和 s2[j]但不能交换 s1[i] 和 s1[j]。
最后请你返回使 s1 和 s2 相同的最小交换次数如果没有方法能够使得这两个字符串相同则返回 -1 。 示例 1
输入s1 xx, s2 yy
输出1
解释
交换 s1[0] 和 s2[1]得到 s1 yxs2 yx。
示例 2
输入s1 xy, s2 yx
输出2
解释
交换 s1[0] 和 s2[0]得到 s1 yys2 xx 。
交换 s1[0] 和 s2[1]得到 s1 xys2 xy 。
注意你不能交换 s1[0] 和 s1[1] 使得 s1 变成 yx因为我们只能交换属于两个不同字符串的字符。
示例 3
输入s1 xx, s2 xy
输出-1示例 4
输入s1 xxyyxyxyxx, s2 xyyxyxxxyx
输出4提示
1 s1.length, s2.length 1000s1, s2 只包含 x 或 y。思路 当你s1和s2不等时无非就是yx或者xy要获得最小交换次数那么我们在此次交换最好解决下次的交换问题。如果有x0个xy且x0为偶数,则xy的交换次数为x02。如果有y0个xy且y为偶数,则xy的交换次数为y0/2。如果两者同时为奇数则只需要记录x0-1y0-1/22次交换。xy奇偶不同则必不可能相同直接返回-1。
class Solution {
public:int minimumSwap(string s1, string s2) {//两个都不相同换or贪心 int size s1.size();int x 0, y 0;for(int i 0;isize;i){if(s1[i]xs2[i]y) x;if(s1[i]ys2[i]x) y;}if(!(x%2)!(y%2)) return (xy)/2;else if(x%2y%2) return(xy)/21;return -1;}
};
