将给定的二进制字符串转换为另一个二进制字符串，最少操作数为翻转除一个以外的所有位

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

我们可以根据给定字符串中“01”和“10”对的总数来解决问题。

问题陈述- 我们给出了两个长度相同的字符串，分别名为 str1 和 str2，包含“0”和“1”字符，表示二进制字符串。我们需要通过执行以下操作将字符串 str1 转换为 str2。

• 我们可以选择任何设置的位并翻转所有其他位。翻转位意味着将“0”转换为“1”，将“1”转换为“0”。

• 如果无法将 str1 转换为 str2，则打印 -1。

示例

输入

str1 = "001001111", str2 = "011111000";

输出

3

解释−

• 在第一个操作中，我们保持第二个索引的“1”不变，并翻转 str1 中的所有其他字符。因此，str1 将是 111110000。

• 在第二个操作中，我们保持第 0 个索引的“1”不变，并翻转所有其他字符。因此，str1 将是 100001111。

• 在最后一个操作中，我们将“1”保存在第 5 个索引处。因此，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和操作1中的最小值存储在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 步− 如果操作 2 不等于 -1，则将“ans”或“1 + 操作 2”中的最小值存储在“ans”中。这里，我们添加了 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对的数量，以尽量减少操作。程序员可以使用各种输入并尝试理解答案。

以上是将给定的二进制字符串转换为另一个二进制字符串，最少操作数为翻转除一个以外的所有位的详细内容。更多信息请关注PHP中文网其他相关文章！