Leetcode1247. 交换字符使得字符串相同

Leetcode1247. 交换字符使得字符串相同

​

Every day a leetcode：Day 1，2022.1.1

题目来源：1247. 交换字符使得字符串相同

解法：贪心

由于要求交换次数尽量少，故：

• 本来相同位置就有相同的字符，不需要交换。
• 本来相同位置字符不同，需要交换。交换为两组字符交换，本质上只有两种情形：

1. 如示例1，对于"xx"和"yy"组合，只需交换1次。

2. 如示例2，对于"xy"和"yx"组合，需要交换2次。

​
综上所述，我们可以得出如下结论：

1. xy与yx的组数之和必须为偶数，否则返回-1；
2. 优先进行(1)类交换，剩余的进行(2)类交换(贪心的思想)

因此我们先计算xy和yx组合各自的个数，然后找到需要1次变化的，和需要2次变化的，计算结果即可。

设xy为s1[i]=x,s2[i]=y的次数，yx为s1[i]=y,s2[i]=x的次数。

则：

• 当xy+yx为奇数时，无法完成匹配，return -1
• 当xy和yx均为奇数时，各拿一组进行(2)类交换，其余进行(1)类交换，共需(xy-1)/2+(yx-1)/2+2=(xy+yx)/2+1次
• 当xy和yx均为偶数时，全部进行(1)类交换，共需(xy+yx)/2次

两种情况合并为：(xy+1)/2+(yx+1)/2次

代码为：

int minimumSwap(char * s1, char * s2){
    int len=strlen(s1);
    int xy=0,yx=0;
    for(int i=0;i 
提交结果：
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5693682.html