Minimumkan bilangan lilitan supaya tiada pasangan sifar berturut-turut dalam rentetan

Di sini, kita perlu memanipulasi rentetan binari supaya ia tidak mengandungi sebarang sifar berturut-turut Jika kita mendapati sifar berturut-turut, kita perlu menukar sebarang sifar kepada 1. Jadi, kita perlu mengira jumlah bilangan 0. kepada 1 penukaran yang harus kita lakukan untuk mengalih keluar semua sifar berturut-turut daripada rentetan.

Pernyataan Masalah − Kami diberi rentetan binari ‘str’ yang hanya mengandungi 0 dan 1. Kita perlu mencari bilangan lilitan minimum yang diperlukan supaya rentetan yang terhasil tidak mengandungi sifar berturut-turut.

Contoh Contoh

Input –  0101001

Output – 1

Penjelasan

Kita perlu membalikkan hanya sifar kedua kepada sifar terakhir.

Input –  str = 00100000100

Output – 4

Penjelasan

Kita perlu membalikkan sifar ke-2, ke-5, ke-7 dan ke-11 untuk menghapuskan semua pasangan sifar berturut-turut.

Input –  0101010101

Output – 0

Penjelasan

Kami tidak perlu melakukan apa-apa membalikkan kerana tiada sifar berturut-turut dalam rentetan.

Kaedah 1

Dalam kaedah ini, kami akan mengulangi rentetan dari awal hingga akhir dan menyelak aksara jika ia mengandungi sebarang sifar berturut-turut. Akhir sekali, kita boleh mendapatkan bilangan lilitan minimum yang diperlukan untuk mengalih keluar semua sifar berturut-turut daripada rentetan binari yang diberikan.

Algoritma

• Langkah 1 − Mulakan pembolehubah 'cnt' dengan sifar, menyimpan jumlah lilitan.

• Langkah 2 − Lelaran melalui rentetan binari menggunakan gelung.

• Langkah 3 − Jika aksara pada indeks 'I' dan indeks 'I +1' ialah 0, balikkan aksara seterusnya dan naikkan nilai pembolehubah 'cnt' sebanyak 1.

• Langkah 4 - Apabila lelaran gelung for selesai, kembalikan nilai 'cnt'.

Contoh

#include <bits/stdc++.h>
using namespace std;
// Function to get the total number of minimum flips required so the string does not contain any consecutive 0’s
int findCount(string str, int len){

   // initialize the count
   int cnt = 0;
   
   // iterate over the string
   for (int i = 0; i < len - 1; i++){
   
      // If two consecutive characters are the same
      if (str[i] == '0' && str[i + 1] == '0'){
      
         // Flip the next character
         str[i + 1] = '1';
         
         // increment count
         cnt++;           
      }
   }
   return cnt;
}
int main(){
   string str = "00100000100";
   int len = str.length();
   cout << "The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - " << findCount(str, len);
   return 0;
}

Output

The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - 4

Kerumitan masa − O(N), sambil kita melelang melalui rentetan binari.

Kerumitan ruang − O(1), kerana kami menggunakan ruang tetap untuk menyimpan jumlah kiraan.

Kesimpulan

Kami belajar mengira bilangan lilitan minimum yang diperlukan untuk mengalih keluar pasangan sifar berturut-turut daripada rentetan binari yang diberikan. Pengguna boleh cuba mengira bilangan lilitan minimum yang diperlukan untuk mengeluarkan pasangan berturut-turut daripada rentetan binari yang diberikan.

Atas ialah kandungan terperinci Minimumkan bilangan lilitan supaya tiada pasangan sifar berturut-turut dalam rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!