Rumah > Artikel > pembangunan bahagian belakang > 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.
Input – 0101001
Output – 1
Kita perlu membalikkan hanya sifar kedua kepada sifar terakhir.
Input – str = 00100000100
Output – 4
Kita perlu membalikkan sifar ke-2, ke-5, ke-7 dan ke-11 untuk menghapuskan semua pasangan sifar berturut-turut.
Input – 0101010101
Output – 0
Kami tidak perlu melakukan apa-apa membalikkan kerana tiada sifar berturut-turut dalam rentetan.
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.
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'.
#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; }
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.
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!