Bilangan minimum lilitan awalan diperlukan untuk menukar rentetan binari kepada rentetan yang lain

Dalam masalah ini, kita perlu menukar rentetan binari pertama kepada rentetan binari kedua dengan membalikkan awalannya. Untuk mendapatkan bilangan minima lambungan awalan, kita perlu mengulangi penghujung rentetan dan jika aksara tidak sepadan ditemui dalam kedua-dua rentetan, kita perlu membalikkan awalan rentetan pertama.

Pernyataan Masalah − Kami diberi dua rentetan binari berbeza dipanggil pertama dan kedua. Dua rentetan binari adalah sama panjang, N. Kita perlu menukar rentetan pertama kepada rentetan kedua dengan membalikkan awalannya. Di sini kita perlu mengira jumlah bilangan lilitan awalan yang diperlukan untuk menukar satu rentetan kepada rentetan yang lain. Flip bermaksud menukar '0' kepada '1' dan '1' kepada '0'.

Contoh Contoh

Input –  first = "001", second = "000"

Output – 2

Penjelasan

• Pertama, kita perlu membalikkan awalan panjang 3 untuk rentetan pertama, dan rentetan yang terhasil ialah 110.

• Selepas ini kita perlu membalikkan awalan panjang 2 dan rentetan yang terhasil ialah 000 yang sama dengan rentetan kedua.

Input –  first = "10", second = "01"

Output – 1

Penjelasan

Kami perlu membalikkan awalan panjang 2, dan rentetan yang terhasil ialah '01', yang sama dengan rentetan kedua.

Input –  first = "11", second = "11"

Output – 0

Penjelasan

Memandangkan kedua-dua rentetan adalah sama, kita tidak perlu melakukan apa-apa membalikkan.

Pendekatan 1

Dalam kaedah ini, kami mengulangi dari hujung rentetan dan jika kami menemui aksara yang tidak sepadan, kami menyelak semua aksara dalam awalan panjang 'I + 1'. Ini adalah cara mudah untuk menyelesaikan masalah.

Algoritma

• Langkah 1 - Takrifkan pembolehubah 'cnt' dan mulakannya kepada 0.

• Langkah 2 − Mula melintasi rentetan dari hujung menggunakan gelung.

• Langkah 3 − Jika pertama[i] dan kedua[i] tidak sama, kita perlu menyelak semua aksara awalan yang panjangnya sama dengan I + 1.

• Langkah 4 − Gunakan sarang untuk gelung untuk lelaran melalui awalan panjang yang sama dengan I + 1, dan flip setiap aksaranya dengan melaksanakan fungsi flipBits().

• Langkah 4.1 − Kami mengembalikan '0' jika aksara semasa ialah '1' dan '1' jika aksara semasa ialah '0' dalam fungsi flipBits().

• Langkah 5 − Naikkan nilai pembolehubah 'cnt' sebanyak 1 apabila kita menyelak awalan.

• Langkah 6 - Kembalikan nilai pembolehubah 'cnt'.

Contoh

#include <bits/stdc++.h>
using namespace std;
char flipBits(char ch){
   // if the bit is '0', flip it to '1', else flip it to '0'.
   return (ch == '0') ? '1' : '0';
}
int minimumFlips(string first, string second, int n){
   // to store the count of flips
   int cnt = 0;
   
   // Traverse the string
   for (int i = n - 1; i >= 0; i--){
   
      // If first[i] is not equal to second[i]
      if (first[i] != second[i]){
      
         // flip the bits
         for (int j = 0; j <= i; j++){
            first[j] = flipBits(first[j]);
         }
         cnt++;
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Output

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Pendekatan 2

Dalam pendekatan ini, kami akan menggunakan pembolehubah 'terbalik' untuk menjejaki sama ada bit semasa dibalikkan atau tidak, dan bukannya menyelak setiap bit awalan setiap kali Kami juga mengoptimumkan kerumitan masa kod dalam pendekatan ini.

Algoritma

• Langkah 1 − Takrifkan pembolehubah 'cnt' dan mulakan dengan '0' Selain itu, takrifkan pembolehubah 'terbalik' dan mulakan dengan nilai palsu.

• Langkah 2 - Lintas tali bermula dari hujung. Jika aksara [i] dan kedua [i] pertama tidak sepadan, ikut langkah ini.

• Langkah 2.1 − Jika nilai 'terbalik' adalah palsu, naikkan nilai pembolehubah 'cnt' sebanyak 1 dan tukar nilai pembolehubah 'terbalik' kepada benar.

• step 3 − - Jika kedua -dua aksara sepadan, dan nilai 'terbalik' adalah benar, kita perlu flip sedikit lagi. ' kepada palsu.

Contoh

Mari kita nyahpepijat algoritma di atas dengan mengambil contoh.

Input – first = ‘001’, second = ‘000’

• Dalam langkah pertama, yang pertama [2] dan yang kedua [2] tidak sepadan, dan nilai 'terbalikkan' adalah palsu. Oleh itu, nilai 'cnt' akan menjadi 1 dan 'terbalik' akan menjadi benar. Di sini, dengan menukar nilai 'terbalik' kepada benar, kami menganggap bahawa kami telah menyongsangkan awalan secara hampir.

• Selepas itu, pertama[1] dan kedua[1] sepadan, tetapi nilai 'terbalik' adalah benar Jadi, nilai 'cnt' akan menjadi 2, dan 'terbalik' adalah palsu.

• Seterusnya, padanan[0] dan kedua[0] pertama, dan nilai ‘terbalikkan’ adalah palsu, jadi, kita tidak perlu melakukan sebarang operasi.

• Akhir sekali, ia mengembalikan 'cnt', yang mempunyai nilai 2.

#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of flips of prefixes required to convert the first binary string to the second
int minimumFlips(string first, string second, int N){

   // number of flips
   int cnt = 0;
   
   // to track whether the current bit is already flipped.
   // When we flip a bit 2 times, it becomes the same as the original bit.
   bool inverted = false;
   
   // Traverse the given string
   for (int i = N - 1; i >= 0; i--){
   
      // If A[i] is not equal to B[i]
      if (first[i] != second[i]){
      
         // If the current bit is not already flipped
         if (!inverted){
            cnt++; // Increase the count of flips
            inverted = true; // Invert all prefix bits
         }
      }
      else{
      
         // If A[i] is equal to B[i], but a current bit is flipped, we need to flip it again
         if (inverted){
         
            // Increase the count of flips
            cnt++;
            
            // Update inverted to false
            inverted = false;
         }
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Output

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Kesimpulan

Kami mempelajari dua kaedah untuk mencari bilangan minimum sebalikan awalan yang diperlukan untuk menukar satu rentetan kepada rentetan yang lain. Logiknya adalah untuk mengulangi rentetan dari hujung dan membalikkan awalan jika kita menemui aksara yang tidak sepadan.

Kami mengoptimumkan sekeping kod kedua dari segi kerumitan masa dengan menggunakan pembolehubah "terbalik" untuk menjejaki awalan terbalik dan bukannya menyongsangkannya seperti pendekatan pertama.

Atas ialah kandungan terperinci Bilangan minimum lilitan awalan diperlukan untuk menukar rentetan binari kepada rentetan yang lain. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!