建设银行的官方网站,建设网站的价格表,网站有备案 去掉备案,上海专业做网站公司电话来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
有两个长度相同的字符串 s1 和 s2#xff0c;且它们其中 只含有 字符 x 和 y#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候力扣LeetCode
描述
有两个长度相同的字符串 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[i] 为 “x”s2[i] 为 “y”用 xy 表示这种情况出现的次数。另一种情况是 s1[i] 为 “y”s2[i] 为 “x”用 yx 表示这种情况出现的次数。现在需要通过最少次数的交换使得 xy 和 yx 都为 0。交换的方法有两种
示例 1可以通过一次交换使得 xy 或 yx 的值减少 2。示例 2可以通过两次交换使得 xy 和 yx 的值各减少 1。
为了使用尽可能少的交换次数需要从以下顺序考虑
第一种交换方式更有效率应该尽可能采用第一种交换方式。如果还未能使 xy 和 yx 都为 0则应该采用第二种交换方式。如果 xy 和 yx 都为 1则可以通过两次第二种交换来使得 xy 和 yx 都为 0否则不能使 xy 和 yx 都为 0。这里也可以预先判断如果 xy 和 yx 之和为奇数则没有方法能够使得字符串相等。
代码
class Solution {
public:int minimumSwap(string s1, string s2) {int xy 0, yx 0;int n s1.size();for (int i 0; i n; i) {char a s1[i], b s2[i];if (a x and b y) {xy;}if (a y and b x) {yx;}}if ((xy yx) % 2 1) {return -1;}return xy / 2 yx / 2 xy % 2 yx % 2;}
};执行用时0 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗6 MB, 在所有 C 提交中击败了93.67%的用户 复杂度分析 时间复杂度O(n)其中 n 是字符串的长度。需要遍历两个字符串一遍。 空间复杂度O(1)只需要常数空间。 authorLeetCode-Solution
