C++ 通过翻转所有位(除了任何一个)将给定的二进制字符串转换为另一个的最小操作次数

在这个问题中，我们需要通过翻转字符串的字符将一个二进制字符串转换为另一个二进制字符串。我们可以保留任何一个已设置的位并翻转其他位，我们需要计算通过这样做来实现另一个字符串所需的总操作数。

我们可以根据给定字符串中”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。例如，保持“01”中的‘1’。这样，我们就得到了“11”。然后，在“11”中保持第0个索引处的‘1’，这样我们就得到了“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’从’ans’或’1 + operation2’中存储最小值。这里，我们加1是因为我们使用了一次操作来修改字符串。

步骤8 - 保持第一个’10’对不变，并计算操作次数。再次将最小值分配给’ans’。

步骤9 - 如果’ans’等于INT_MAX，则返回-1。否则，返回ans。

示例

#include <bits/stdc++.h>
using namespace std;

// counting 01 and 10 pairs
int totalOperations(string str1, string str2) {
    int len = str1.size();
    int count10 = 0, count01 = 0;
    for (int p = 0; p < len; p++) {
        // If characters at p index are not same
        if (str1[p] != str2[p]) {
            // Increase count01 if 0(str1)-1(str2), else count10 if 1(str1)-0(str2)
            if (str1[p] == '0')
                count01++;
            else
                count10++;
        }
    }
    // If we have euqal number of 01 and 10 pairs, we need 2 operations to flip one pair.
    if (count01 == count10)
        return 2 * count01;
    return -1;
}
bool StringModification(string &temp1, string &temp2, char ch) {
    int len = temp1.size();
    int index = -1;
    // Find the pair of 1c character. (1 -> temp1, c -> temp2)
    for (int p = 0; p < len; p++) {
        if (temp1[p] == '1' && temp2[p] == ch) {
            index = p;
            break;
        }
    }
    // return 0 if pair is not found
    if (index == -1)
        return false;
    // Flip other characters in both strings
    for (int p = 0; p < len; p++) {
        if (p != index) {
            if (temp1[p] == '1')
                temp1[p] = '0';
            else
                temp1[p] = '1';
        }
    }
    return true;
}
// finding minimum operations
int minimumOperations(string str1, string str2) {
    int ans = INT_MAX;
    // first case with initial strings
    int operation1 = totalOperations(str1, str2);
    if (operation1 != -1)
        ans = min(ans, operation1);
    string temp1 = str1, temp2 = str2;
    // Case 2, modification for 11 pair
    if (StringModification(temp1, temp2, '1')) {
        // get operations after modification
        int operation2 = totalOperations(temp1, temp2);
        // adding 1 to operation2 as we have done one modification initially
        if (operation2 != -1)
            ans = min(ans, 1 + operation2);
    }
    // Case 3 modification for 10 pair
    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 to S2 conversion is not possible";
    }
    else{
        cout << "Minimum number of operations required are: " << ans << "\n";
    }
    return 0;
}

输出

Minimum number of operations required are: 3

时间复杂度 − O(N)，因为我们在函数stringModification()和totalOperations()中遍历字符串。

空间复杂度 − O(1)，因为我们在不使用额外空间的情况下修改相同的字符串。

在代码中，我们的主要目的是在修改字符串以最小化操作之后减少给定字符串中01和10对的数量。程序员可以使用各种输入并尝试理解答案。