C++ 中使字符串相等所需的最小交换次数


假设我们有两个长度相等的字符串 s1 和 s2,它们只包含字母“x”和“y”。我们的任务是使这两个字符串彼此相等。我们可以交换属于不同字符串的任意两个字符,这意味着 - 交换 s1[i] 和 s2[j]。我们必须找到使 s1 和 s2 相等所需的最小交换次数,或者如果不可能这样做,则返回 -1。因此,如果字符串为 s1 =“xy”和 s2 =“yx”,则输出将为 2。如果我们交换 s1[0] 和 s2[0],则 s1 = "yy",s2 = "xx"。然后交换 s1[0] 和 s2[1],s1 = "xy",s2 = "xy"。

为了解决这个问题,我们将遵循以下步骤:

  • 将 x1、x2、y1 和 y2 设置为 0
  • 对于 i 从 0 到 s1 的大小
    • a := s1[i] 和 b := s2[i]
    • 如果 a 与 b 不相同,则
      • 如果 a = 'x',则将 x1 增加 1,否则将 y1 增加 1
      • 如果 b = 'x',则将 x2 增加 1,否则将 y2 增加 1
  • 如果 (x1 + x2) 为奇数或 (y1 + y2) 为奇数,则返回 -1
  • 返回 x1/2 + y1/2 + (x1 模 2) * 2

示例(C++)

让我们看看以下实现,以便更好地理解:

 在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumSwap(string s1, string s2) {
      int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
      for(int i = 0; i < s1.size(); i++){
         char a = s1[i];
         char b = s2[i];
         if(a != b){
            if(a == 'x')x1++;
            else y1++;
            if(b == 'x')x2++;
            else y2++;
         }
      }
      if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
      return x1/2 + y1/2 + (x1 % 2) * 2;
   }
};
main(){
   Solution ob;
   cout <<ob.minimumSwap("xy", "yx");
}

输入

"xy"
"yx"

输出

2

更新于:2020-04-30

445 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告