通过翻转除 1 之外的所有位，以最少的操作将给定的二进制字符串转换为另一个
在这个问题中，我们需要通过翻转字符串的字符将一个二进制字符串转换为另一个二进制字符串。我们可以保留任何设置位并翻转其他位，我们需要计算通过执行此操作获得另一个字符串的总操作数。
我们可以根据给定字符串中"01"和"10"对的总数来解决问题。
问题陈述− 我们给出了两个名为 str1 和 str2 的字符串，它们的长度相同，包含"0"和"1"字符，表示二进制字符串。我们需要通过执行以下操作将字符串 str1 转换为 str2。
我们可以选择任何设置位并翻转所有其他位。翻转位意味着将'0'转换为'1'，将'1'转换为'0'。
如果无法将 str1 转换为 str2，则打印 −1。
示例
输入
str1 = "001001111", str2 = "011111000";
输出
3
解释 −
在第一个操作中，我们保持第 2 个索引的"1"不变，并翻转 str1 中的所有其他字符。因此，str1 将为 111110000。
在第二个操作中，我们保持第 0 个索引的"1"不变，并翻转所有其他字符。因此，str1 将为 100001111。
在最后一个操作中，我们保留第 5 个索引处的"1"。因此，str1 将变为 011111000。
输入
str1 = "0000", str2 = "1111";
输出
-1
解释 − 无法将 str1 转换为 str2，因为 str1 不包含任何要保存的"1"字符。
输入
str1 = "0111", str2 = "1000";
输出
-1
解释 − 无法将 str1 转换为 str2。
方法 1
我们可以通过观察来解决问题。观察结果表明，当我们保留任何单个设置位并执行 2 次操作时，我们可以得到相同的字符串。因此，我们需要选择不同的 1 索引来更改字符串。
此外，我们需要执行 2 个操作才能将 01 对转换为 10。例如，将"1"保留在"01"中。因此，我们得到"11"。之后，将"1"保留在"11"中的第 0 个索引处，这样我们就会得到"10"。
要得到答案，01(0 −> str1, 1 −> str2)和 10(1 −> str1, 0 −> str2)对应该相同。否则，我们可以说答案不存在。
我们的主要目标是最小化"01"和"10"对，因为我们可以在 2 次操作中将"01"转换为"10"。
算法
步骤 1 - 定义 totalOperatrions() 函数来计算将 str1 转换为 str2 所需的操作数。
步骤 1.2 - 初始化 count10 和 count01 变量以将"01"和"10"对存储在字符串中。
步骤 1.3 - 遍历字符串并计算两个字符串中的 01 和 10 对。
步骤 1.4 - 如果 count10 和 count01 相同，则返回 2*count10。否则返回 −1。
步骤 2 − 定义 minimumOperations() 函数来计算将 str1 转换为 str2 所需的最少操作。
步骤 3 − 用最大值初始化'ans'。
步骤 4 − 使用原始字符串调用 totalOperations() 函数，并将结果存储在'operation1'变量中。如果返回值不等于 −1，则将 ans 和 operation1 中的最小值存储在 ans 中。
步骤 5 − 现在，我们将修改字符串以最小化 01 和 10 的对。因此，定义 stringModification() 函数。
步骤 5.1 − 在函数中，我们找到字符串中的第一对'1ch'，并将'ch'作为参数传递，该参数可以是'0'或'1'。因此，该对应为 1 −> str1 和 ch −> str。
步骤 5.2 − 如果未找到"1ch"对，则返回 false。
步骤 5.3 − 如果找到"1ch"对，则保持对原样并翻转 str1 的其他字符。
步骤 6 − 执行 stringModification 函数以保持"11"对原样并翻转其他字符。之后，再次调用 totalOperations() 函数以查找将 str1 转换为 str2 所需的操作。
步骤 7 − 如果 operation2 不等于 −1，则将"ans"或"1 + operation2"中的最小值存储在"ans"中。这里我们添加了 1，因为我们使用一个操作修改了字符串。
步骤 8 − 修改字符串，保持第一个'10'对不变，并计算操作数。再次将最小值分配给'ans'。
步骤 9 − 如果'ans'等于 INT_MAX，则返回 −1。否则，返回 ans。
示例
#include <bits/stdc++.h>
using namespace std;
// 计算 01 和 10 对
int totalOperations(string str1, string str2) {
int len = str1.size();
int count10 = 0, count01 = 0;
for (int p = 0; p < len; p++) {
// 如果 p 索引处的字符不相同
if (str1[p] != str2[p]) {
// 如果 0(str1)-1(str2)，则增加 count01，否则如果 1(str1)-0(str2)，则增加 count10
if (str1[p] == '0')
count01++;
else
count10++;
}
}
// 如果 01 和 10 对的数量相等，则需要 2 次操作来翻转一对。
if (count01 == count10)
return 2 * count01;
return -1;
}
bool StringModification(string &temp1, string &temp2, char ch) {
int len = temp1.size();
int index = -1;
// 查找 1c 字符对。 (1 -> temp1, c -> temp2)
for (int p = 0; p < len; p++) {
if (temp1[p] == '1' && temp2[p] == ch) {
index = p;
break;
}
}
// 如果未找到对，则返回 0
if (index == -1)
return false;
// 翻转两个字符串中的其他字符
for (int p = 0; p < len; p++) {
if (p != index) {
if (temp1[p] == '1')
temp1[p] = '0';
else
temp1[p] = '1';
}
}
return true;
}
// 查找最小操作
int minimumOperations(string str1, string str2) {
int ans = INT_MAX;
// 第一种情况，带有初始字符串
int operation1 = totalOperations(str1, str2);
if (operation1 != -1)
ans = min(ans, operation1);
string temp1 = str1, temp2 = str2;
// 第 2 种情况，针对 11 对进行修改
if (StringModification(temp1, temp2, '1')) {
// 获取修改后的操作
int operation2 = totalOperations(temp1, temp2);
// 将 operation2 加 1，因为我们最初进行了一次修改
if (operation2 != -1)
ans = min(ans, 1 + operation2);
}
// 第 3 种情况，针对 10 对进行修改
temp1 = str1, temp2 = str2;
if (StringModification(temp1, temp2, '0')) {
int operation3 = totalOperations(temp1, temp2);
if (operation3 != -1)
ans = min(ans, 1 + operation3);
}
if (ans == INT_MAX)
return -1;
else
return ans;
}
int main() {
string str1 = "001001111";
string str2 = "011111000";
int ans = minimumOperations(str1, str2);
if (ans == -1){
cout << "无法将 S1 转换为 S2";
}
else{
cout << "所需的最少操作数为:" << ans << "\n";
}
return 0;
}
输出
所需的最少操作数为:3
时间复杂度− O(N)，因为我们在 stringModification() 和 totalOperations() 函数中遍历字符串。
空间复杂度− O(1)，因为我们修改同一个字符串而不使用任何额外空间。
在代码中，我们的主要目的是在修改字符串后减少给定字符串中 01 和 10 的对数，以最小化操作。程序员可以使用各种输入并尝试理解答案。
