將給定的二進位字串轉換為另一個二進位字串，最少運算元為翻轉除一個以外的所有位

在這個問題中，我們需要透過翻轉字串的字符，將一個二進位字串轉換為另一個二進位字串。我們可以保存任何設定的位元並翻轉其他位，並且我們需要計算總操作以通過這樣做來實現另一個字串。

我們可以根據給定字串中「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中文網其他相關文章！