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
广告