Menukar rentetan binari yang diberikan kepada rentetan binari yang lain, dengan operan minimum membalikkan semua bit kecuali satu

Dalam masalah ini, kita perlu menukar satu rentetan binari kepada rentetan binari yang lain dengan membalikkan aksara rentetan itu. Kita boleh menyimpan sebarang set bit dan membalikkan bit lain, dan kita perlu mengira jumlah operasi untuk melaksanakan rentetan lain dengan melakukan ini.

Kami boleh menyelesaikan masalah berdasarkan jumlah pasangan "01" dan "10" dalam rentetan yang diberikan.

Pernyataan Masalah- Kami diberi dua rentetan yang sama panjang, dinamakan str1 dan str2, mengandungi aksara "0" dan "1", mewakili rentetan binari. Kita perlu menukar rentetan str1 kepada str2 dengan melakukan perkara berikut.

• Kita boleh memilih mana-mana bit set dan membalikkan semua bit lain. Flip bit bermaksud menukar "0" kepada "1" dan "1" kepada "0".

• Jika str1 tidak boleh ditukar kepada str2, cetak -1.

Contoh

Masuk

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

Output

3

Penjelasan−

• Dalam operasi pertama, kami mengekalkan "1" indeks kedua tidak berubah dan menyelak semua aksara lain dalam str1. Oleh itu, str1 akan menjadi 111110000.

• Dalam operasi kedua, kami mengekalkan "1" pada indeks ke-0 tidak berubah dan menyelak semua aksara lain. Oleh itu, str1 akan menjadi 100001111.

• Dalam operasi terakhir, kami menyimpan "1" pada indeks ke-5. Oleh itu, str1 akan menjadi 011111000.

Masuk

 str1 = "0000", str2 = "1111";

Output

-1

Penjelasan- Tidak boleh menukar str1 kepada str2 kerana str1 tidak mengandungi sebarang aksara "1" untuk disimpan.

Masuk

 str1 = "0111", str2 = "1000";

Output

-1

Penjelasan- Tidak dapat menukar str1 kepada str2.

Kaedah 1

Kita boleh menyelesaikan masalah dengan memerhati. Pemerhatian ialah apabila kita memegang sebarang bit set tunggal dan melakukan 2 operasi kita mendapat rentetan yang sama. Oleh itu, kita perlu memilih 1 indeks yang berbeza untuk membuat perubahan pada rentetan.

Selain itu, kita perlu melakukan 2 operasi untuk menukar pasangan 01 kepada 10. Sebagai contoh, tinggalkan "1" dalam "01". Jadi, kita dapat "11". Selepas itu, simpan "1" pada indeks ke-0 dalam "11" supaya kita mendapat "10".

Untuk mendapatkan jawapan, 01 (0 -> str1, 1 -> str2) dan 10 (1 -> str1, 0 -> str2) hendaklah sama. Jika tidak, kita boleh mengatakan bahawa jawapan itu tidak wujud.

Matlamat utama kami adalah untuk meminimumkan pasangan "01" dan "10", kerana kami boleh menukar "01" kepada "10" dalam 2 operasi.

Algoritma

Langkah 1- Takrifkan fungsi totalOperatrion() untuk mengira bilangan operasi yang diperlukan untuk menukar str1 kepada str2.

Langkah 1.2 - Mulakan pembolehubah count10 dan count01 untuk menyimpan pasangan "01" dan "10" dalam rentetan.

Langkah 1.3 - Gelung melalui rentetan dan kira pasangan 01 dan 10 dalam kedua-dua rentetan.

Langkah 1.4− Jika kiraan10 dan kiraan01 adalah sama, kembalikan 2*kiraan10. Jika tidak, -1 dikembalikan.

Langkah 2- Tentukan fungsi minimumOperations() untuk mengira operasi minimum yang diperlukan untuk menukar str1 kepada str2.

Langkah 3- Mulakan "ans" dengan nilai maksimum.

Langkah 4- Panggil fungsi totalOperations() menggunakan rentetan asal dan simpan hasilnya dalam pembolehubah "operasi1". Jika nilai pulangan tidak sama dengan -1, nilai minimum daripada ans dan operasi 1 disimpan dalam ans.

Langkah 5- Sekarang, kami akan mengubah suai rentetan untuk meminimumkan pasangan 01 dan 10. Oleh itu, tentukan fungsi stringModification().

Langkah 5.1 - Dalam fungsi, kita mencari pasangan pertama "1ch" dalam rentetan dan lulus "ch" sebagai parameter, yang boleh menjadi "0" atau "1". Jadi pasangan itu sepatutnya kelihatan seperti 1 -> str1 dan ch -> str.

Langkah 5.2- Kembalikan palsu jika tiada pasangan "1ch" ditemui.

Langkah 5.3 − Jika pasangan "1ch" ditemui, biarkan pasangan itu tidak berubah dan balikkan aksara lain str1.

Langkah 6- Jalankan fungsi pengubahsuaian rentetan untuk memastikan pasangan "11" tidak berubah dan flip aksara lain. Selepas itu, fungsi totalOperations() dipanggil semula untuk mencari operasi yang diperlukan untuk menukar str1 kepada str2.

Langkah 7− Jika operasi 2 tidak sama dengan -1, simpan nilai minimum dalam "ans" atau "1 + operasi 2" dalam "ans". Di sini, kami menambah 1 kerana kami mengubah suai rentetan menggunakan satu operasi.

Langkah 8- Ubah suai rentetan dengan membiarkan pasangan "10" pertama tidak berubah, dan hitung operan. Sekali lagi berikan nilai minimum kepada "ans".

Langkah 9− Jika "jawapan" bersamaan dengan INT_MAX, kembalikan −1. Jika tidak, kembalikan ans.

Contoh

#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;
}

Output

Minimum number of operations required are: 3

Kerumitan masa− O(N) kerana kami mengulangi rentetan dalam fungsi stringModification() dan totalOperations().

Kerumitan ruang− O(1) kerana kami mengubah suai rentetan yang sama tanpa menggunakan sebarang ruang tambahan.

Dalam kod, tujuan utama kami adalah untuk mengurangkan bilangan 01 dan 10 pasangan dalam rentetan yang diberikan selepas mengubah suai rentetan untuk meminimumkan operasi. Pengaturcara boleh menggunakan pelbagai input dan cuba memahami jawapannya.

Atas ialah kandungan terperinci Menukar rentetan binari yang diberikan kepada rentetan binari yang lain, dengan operan minimum membalikkan semua bit kecuali satu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!