用笔记本做网站服务器,网站开发有前途,viewjs wordpress,广州品牌型网站本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 You are given two strings s1 and s2 of equal length consisting of letters x and y only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].
Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.
Example 1:
Input: s1 xx, s2 yy
Output: 1
Explanation: Swap s1[0] and s2[1], s1 yx, s2 yx.Example 2:
Input: s1 xy, s2 yx
Output: 2
Explanation: Swap s1[0] and s2[0], s1 yy, s2 xx.
Swap s1[0] and s2[1], s1 xy, s2 xy.
Note that you cannot swap s1[0] and s1[1] to make s1 equal to yx, cause we can only swap chars in different strings.Example 3:
Input: s1 xx, s2 xy
Output: -1Constraints:
1 s1.length, s2.length 1000s1, s2 only contain x or y.
题意有两个长度相同的字符串 s1 和 s2且它们其中 只含有 字符 x 和 y需要通过「交换字符」的方式使这两个字符串相同。每次「交换字符」的时候你都可以在两个字符串中各选一个字符进行交换。交换只能发生在两个不同的字符串之间绝对不能发生在同一个字符串内部。最后返回使 s1 和 s2 相同的最小交换次数如果没有方法能使这两个字符串相同则返回 -1 。 解法 贪心
首先忽略所有已经匹配的位置它们根本不会影响答案。对于不匹配的位置有三种基本情况示例中已给出
xx, yy 1次互换xy, xy 2次互换
yx, yx 2次互换
xy, yx 2次互换
yx, xy 2次互换 因此贪心策略是尽可能应用情况1、它需要的交换次数最少如果最后剩下两个字符与另外两个不匹配则应用情况2如果只剩下一个字符与另一个字符不匹配就不可能实现题意了字符串 s1, s2 之间如果存在奇数个位置不同就无法使它们相同。具体代码如下
时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(1)O(1)
class Solution {
public:int minimumSwap(string s1, string s2) {int s1XCnt 0, s1YCnt 0;for (int i 0, n s1.size(); i n; i) {if (s1[i] ! s2[i]) {if (s1[i] x) s1XCnt;else s1YCnt;}}// s1XCnt s2YCnt, s1YCnt s2XCnt// 忽略匹配的字符;跳过不是同个字符的位置来观察(如将不同位置的x连着看,对面是连着的y)// 尽量用xx与对面同样位置yy(或者反过来这边用yy那边用xx)交换,这样交换次数最少,次数为s1XCnt/2s1YCnt/2// 最后可能剩下一对xy与yx,要两次交换才行// 也可能都没剩下,之间返回// 如果最后只剩下一个x与一个y,则无解if (s1XCnt % 2 s1YCnt % 2 1) return -1; // 这边只剩下一个x或yint ans s1XCnt / 2 s1YCnt / 2;return s1XCnt % 2 1 ? ans 2 : ans;}
};
