Menjadikan rentetan binari yang diberikan sama dengan berulang kali menggantikan dua 0 berturut-turut dengan satu 1

Dalam mana-mana bahasa pengaturcaraan, rentetan binari ialah koleksi aksara 0 dan 1. Pada setiap peringkat, rentetan binari mengikut pendekatan bahawa rentetan hanya boleh mengandungi dua aksara ini.

Watak dalam rentetan berterusan ialah aksara yang indeksnya berbeza sebanyak 1. Mari kita pertimbangkan dua indeks, i dan j, ia dikatakan selanjar jika |j-i| = 1.

Dalam C++, jika dua rentetan adalah setara, ia bermakna:

• Watak yang sepadan dalam dua rentetan adalah sama.

• Panjang rentetan adalah sama dan aksara pada indeks yang sepadan bertepatan.

Beberapa contoh untuk menggambarkan penyataan masalah adalah seperti berikut -

Contoh Contoh

str1 - "10001"

str2 - "101"

Penyelesaian-

str1 tidak boleh ditukar kepada str2 kerana dalam proses menukar str1 untuk mencipta rentetan setara str2, kita akan mendapat str1 sebagai "1011" dan str2 sebagai "101".

Contoh 2 - Mari kita pertimbangkan input berikut −

str1 - "001"

str2 - "11"

Penyelesaian-

str1 boleh ditukar kepada str2 dengan menukar dua sifar pertama kepada 1.

Gunakan padanan aksara dan traversal rentetan dalam C++ untuk menyelesaikan masalah berikut.

Algoritma

• Langkah 1 - Dua penunjuk i dan j digunakan untuk mengulang rentetan s1 dan s2 secara serentak.

• Langkah 2 - Jika aksara pada kedua-dua indeks sepadan, kami menambah penunjuk i dan j.

• Langkah 3 − Jika aksara tidak sama, kami menyemak sama ada aksara pada indeks ke-i dan (i+1) ialah '0' dan sama ada aksara pada indeks ke-j ialah '1 '.

• Langkah 4 - Jika keadaan sedemikian wujud, penukaran boleh dilakukan. Penunjuk i ditambah dengan dua kedudukan dan j ditambah dengan satu kedudukan indeks kerana kedua-dua sifar ditukar kepada satu.

• Langkah 5 - Jika watak tidak sama dan situasi di atas tidak wujud, penukaran tidak boleh dilakukan.

• Langkah 6 − Jika kedua-dua penunjuk i dan j berjaya mencapai kedudukan akhir, s1 boleh ditukar kepada s2.

Contoh

Coretan kod berikut mengambil dua rentetan binari sebagai input dan menyemak sama ada dua rentetan itu boleh bersamaan dengan penggantian aksara mudah berdasarkan syarat yang ditentukan

//including the required libraries
#include <bits/stdc++.h>
using namespace std;

//convert consecutive 0's to 1
bool convertBinary(string s1, string s2){

   //fetching the lengths of both the strings
   int len1 = s1.length();
   int len2 = s2.length();
   string temp ="";

   //maintaining counters of both the strings
   int i = 0, j = 0;

   //iterating over both the strings simultaneously
   while (i < len1 && j < len2) {

      //if both the characters are equivalent in nature
      //skip to next character
      if (s1[i] == s2[j]) {
         temp+=s1[i];

         //incrementing both pointers
         i++;
         j++;
      }

      // if both characters differ
      else {

         // checking if '00' of s1 can be converted to '1' of s2
         if(s2[j]=='1' && s1[i]=='0'){

            //checking if i+1th index exists and is equivalent to 0
            if(i+1 < len1 && s1[i+1]=='0'){

               //conversion is possible
               //skip two 0's of s1 since converted to 1 in s2
               temp+='1';
               i += 2;
               j++;
            } else {
               return false;
            }
         }

         // If not possible to combine
         else {
            return false;
         }
      }
   }
   cout<<"Entered string2 "<<s2<<"\n";
   cout<<"Converted string1 "<<temp<<"\n";

   //check if both the strings are returned to end position
   if (i == len1 && j == len2)
      return true;
      return false;
}

// calling the conversion rate
int main(){
   string str1 = "100100";
   string str2 = "1111";

   //capturing result
   cout<<"Entered string1 "<<str1<<"\n";
   bool res = convertBinary(str1, str2);
   if (res)
      cout << "First string can be converted to second";
   else
      cout << "First string can't be converted to second";
   return 0;
}

Output

Entered string1 100100
Entered string2 1111
Converted string1 1111
First string can be converted to second

Kesimpulan

Memandangkan kaedah ini boleh membandingkan dengan cekap rentetan input aksara mengikut aksara, kerumitan masa ialah O(min(panjang rentetan)). Traversal rentetan adalah aspek penting dalam menyelesaikan masalah rentetan.

Atas ialah kandungan terperinci Menjadikan rentetan binari yang diberikan sama dengan berulang kali menggantikan dua 0 berturut-turut dengan satu 1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!