Pisahkan 1 dan 0 dalam rentetan binari kepada bahagian yang berasingan

Dalam tutorial ini, kita perlu membahagikan semua 1 dan 0 rentetan binari yang diberikan kepada dua bahagian. Di sini, kita perlu mengambil subrentetan daripada rentetan yang diberikan dan membalikkannya untuk memisahkan bahagian 0 dan 1 yang berlainan. Akhirnya, kita perlu mengira jumlah bilangan penyongsangan yang diperlukan untuk subrentetan untuk membahagi 1 dan 0 kepada separuh.

Pernyataan Masalah - Kami diberi rentetan binari yang sama panjang. Kita perlu mengambil mana-mana subrentetan daripada rentetan yang diberikan beberapa kali dan membalikkannya untuk membahagikannya kepada dua bahagian. Kami perlu mencetak jumlah pembalikan yang diperlukan pada penghujungnya.

Contoh

Input –  str = 0011

Output – 0

Arahan

Kami memerlukan 0 pembalikan kerana tali terbelah dua.

Input –  str = 0011101000

Output – 2

Arahan

• Pertama, ambil subrentetan panjang 2 bermula dari indeks ke-5 dan terbalikkannya. Rentetan yang terhasil ialah 0011110000.

• Selepas itu, ambil tali panjang 6 dari awal dan terbalikkan. Rentetan yang terhasil ialah 1111000000

Input –  str = 010101

Output – 2

Arahan

• Terbalikkan rentetan panjang 2 bermula dari indeks pertama. Rentetan yang terhasil ialah 001101.

• Sekarang, terbalikkan rentetan panjang 3 bermula dari indeks kedua. Rentetan terakhir ialah 000111.

Kaedah 1

Kaedah ini akan mengira jumlah bilangan elemen bersebelahan yang berbeza. Selepas itu, kita boleh mengatakan bahawa jumlah pembalikan yang diperlukan ialah kiraan / 2.

Mari kita memahaminya dengan menyahpepijat input sampel.

Input –  str = 00111010

Jadi, jumlah bilangan elemen bersebelahan berbeza ialah 4. Di sini, str[1] != str[2], str[4] != str[5], str[5] != str[6] dan str[6] != str[7].

Jadi, nilai kiraan ialah 4, dan jawapannya ialah kiraan/2, iaitu bersamaan dengan 2.

Algoritma

• Langkah 1 - Mulakan pembolehubah "cnt" kepada 0.

• Langkah 2 - Gunakan gelung for dan ulangi rentetan.

• Langkah 3 − Dalam gelung for, jika elemen semasa tidak sama dengan elemen sebelumnya, naikkan nilai pembolehubah 'cnt' sebanyak 1.

• Langkah 4 − Jika nilai 'cnt' ialah nombor ganjil, kembalikan (cnt -1) /2. Jika tidak, kembalikan cnt/2.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <bits/stdc++.h>
using namespace std;
//  function to find the minimum number of reversals required to segregate 1s and 0s in a separate half
int minimumReversal(string str, int len){
   int cnt = 0; // initialize count with zero
   for (int i = 1; i < len; i++){
   
      // if the adjacent elements are not the same, then the increment count
      if (str[i] != str[i - 1]){
         cnt++;
      }
   }
   
   // For odd count
   if (cnt % 2 == 1){
      return (cnt - 1) / 2;
   }
   return cnt / 2; // For even count
}
int main(){
   string str = "00111010";
   int len = str.size();
   cout << "Minimum number of operations required is : " << minimumReversal(str, len);
   return 0;
}

Output

Minimum number of operations required is : 2

Kerumitan masa - O(N) kerana kami mengulangi rentetan.

Kerumitan ruang - O(N) kerana kami menggunakan ruang tetap untuk menyimpan kiraan.

Di sini kami telah menggunakan logik yang perlu diterbalikkan apabila dua elemen bersebelahan yang berbeza ditemui. Tambahan pula, dalam satu operasi terbalik, kita boleh menetapkan dua elemen, jadi kita mengembalikan kiraan/2 sebagai nilai hasil.

Atas ialah kandungan terperinci Pisahkan 1 dan 0 dalam rentetan binari kepada bahagian yang berasingan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!