Bilangan pergerakan minimum yang diperlukan untuk meletakkan semua 0 sebelum 1 dalam rentetan binari

Pernyataan Masalah

Kami diberi str rentetan binari dan kami diminta untuk mengalih keluar bilangan minimum aksara daripada rentetan supaya kami boleh meletakkan semua sifar sebelum satu.

Contoh

Masuk

str = ‘00110100111’

Output

3

Arahan

Di sini, kita boleh mencapai output 3 dalam dua cara.

Kita boleh mengalih keluar arr[2], arr[3] dan arr[5] atau arr[4], arr[6] dan arr[7] daripada rentetan.

Masuk

str = ‘001101011’

Output

2

Arahan

Kita boleh mengalih keluar arr[4] dan arr[6] serta meletakkan semua sifar sebelum satu.

Masuk

str = ‘000111’

Output

0

Arahan

Dalam rentetan yang diberikan, semua sifar telah diletakkan sebelum 1, jadi kami tidak perlu mengalih keluar sebarang aksara daripada rentetan yang diberikan.

Kaedah 1

Dalam kaedah pertama, kita akan menggunakan dua tatasusunan. Tatasusunan pertama menyimpan semua 1 di sebelah kiri dan tatasusunan lain menyimpan semua 0 di sebelah kanan. Selepas itu, kita boleh menambah elemen pada indeks ke-i dalam kedua-dua tatasusunan dan mencari jumlah minimum.

Algoritma

• Langkah 1 - Tentukan senarai nama sifar dan satu panjang n, dengan n ialah panjang rentetan yang boleh kita peroleh menggunakan kaedah size().

• Langkah 2 - Jika aksara pertama dalam rentetan yang diberikan ialah "1", simpan 1 pada indeks ke-0 tatasusunan "yang" jika tidak, simpan 0.

• Langkah 3 - Gunakan gelung for untuk beralih daripada elemen kedua rentetan. Dalam gelung for, Ones[i] dimulakan dengan nilai yang diperoleh dengan menambah Ones[i-1] kepada 1 atau 0 berdasarkan watak rentetan pada indeks i.

• Langkah 4 - Simpan 1 atau 0 di Zeros[n-1] bergantung pada aksara terakhir dalam rentetan yang diberikan.

• Langkah 5 - Gunakan gelung for untuk mengulangi rentetan bermula dari aksara kedua terakhir dan kemas kini nilai senarai sifar berdasarkan aksara rentetan.

• Langkah 6 - Tentukan pembolehubah "min_zeros_to_remove" dan mulakannya dengan nilai integer maksimum.

• Langkah 7 - Sekarang, ulang melalui senarai "sifar" dan "satu". Akses nilai daripada indeks "i+1" dalam senarai sifar dan indeks "I" dalam senarai "satu". Selepas itu, tambahkan dua elemen ini.

• Langkah 8 - Jika nilai "min_zeros_to_remove" kurang daripada nilai semasa pembolehubah "min_zeros_to_remove", tukar nilainya kepada jumlah dua elemen tatasusunan.

• Langkah 9 - Kembalikan nilai hasil.

Contoh

#include <bits/stdc++.h>
using namespace std;

int minimumZeroRemoval(string str){
   int n = str.size();
   // arrays to store the prefix sums of zeros and ones
   vector<int> zeros(n);
   vector<int> ones(n);
   // compute total number of 1s at the left of each index
   ones[0] = (str[0] == '1') ? 1 : 0;
   for (int i = 1; i < n; i++) {
      ones[i] = ones[i - 1] + ((str[i] == '1') ? 1 : 0);
   }
   // compute total number of 0s at the right of each index
   zeros[n - 1] = (str[n - 1] == '0') ? 1 : 0;
   for (int i = n - 2; i >= 0; i--){
      zeros[i] = zeros[i + 1] + ((str[i] == '0') ? 1 : 0);
   }
   // do the sum of zeros and ones for each index and return the minimum value
   int min_zeros_to_remove = INT_MAX;
   for (int i = 0; i < n - 1; i++){
      min_zeros_to_remove = min(min_zeros_to_remove, zeros[i + 1] + ones[i]);
   }
   return min_zeros_to_remove;
}
int main() {
   string str = "00110100111";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Output

The minimum number of zeros required to remove from the given string is - 3

• Kerumitan masa - O(N) kerana kita memerlukan gelung untuk mengulangi rentetan dan senarai saiz N.

• Kerumitan Ruang - O(N) kerana kami menggunakan dua senarai untuk menyimpan kiraan 1 dan 0.

Kaedah 2

Kaedah ini adalah versi yang dioptimumkan bagi kaedah pertama. Di sini, bukannya senarai, kami menggunakan dua pembolehubah untuk menyimpan kiraan 1s dan 0s.

Algoritma

• Langkah 1 - Tentukan pembolehubah "zeros_right" dan mulakan dengan 0.

• Langkah 2 - Gelung melalui rentetan, kira jumlah bilangan aksara "0" dalam rentetan yang diberikan dan kemas kini nilai pembolehubah "zero_right" dengan sewajarnya.

• Langkah 3 - Tentukan pembolehubah "ones_left" dan mulakannya kepada 0.

• Langkah 4 - Gunakan gelung for untuk mengulangi rentetan. Jika aksara pada indeks i dalam rentetan ialah "1", tingkatkan nilai pembolehubah "ones_left" sebanyak 1. Jika tidak, kurangkan nilai pembolehubah "zeros_right" sebanyak 1.

• Langkah 5 - Jika "zeros_right + Ones_left" kurang daripada nilai semasa pembolehubah "res", kemas kini nilai pembolehubah "res".

Contoh

#include <bits/stdc++.h>
using namespace std;

// function to remove zeros from the string to place all zeros before 1.
int minimumZeroRemoval(string str){
   // counting the total number of zeros in the given string
   int zeros_right = 0;
   for (int i = 0; i < str.size(); i++) {
      if (str[i] == '0')
      zeros_right += 1;
   }
   // variable to store the number of ones from left
   int ones_left = 0;
   // Size of the string
   int len = str.size();
   // variable to store the final result
   int result = INT_MAX;
   // Traverse the string from left to right
   for (int i = 0; i < len; i++){
      // If the current character is '1', then increment ones_left by 1 else, decrement zeros_right by 1
      if (str[i] == '1') {
         ones_left += 1;
      } else {
         zeros_right -= 1;
      }
      // Store the minimum result and zeros_right + ones_left in result
      result = min(result, zeros_right + ones_left);
   }
   // Return the final result
   return result;
}
int main() {
   string str = "001101011";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Output

The minimum number of zeros required to remove from the given string is - 2

• Kerumitan Masa - O(N), apabila kita mengulangi rentetan.

• Kerumitan Ruang - O(1) kerana kami hanya menggunakan ruang malar.

Kesimpulan

Pengguna mempelajari dua cara untuk mengalih keluar bilangan minimum aksara daripada rentetan binari yang diberikan. Kod untuk pendekatan kedua lebih mudah dibaca kerana kami menggunakan pembolehubah untuk menyimpan kiraan sifar dan satu daripada menggunakan senarai.

Atas ialah kandungan terperinci Bilangan pergerakan minimum yang diperlukan untuk meletakkan semua 0 sebelum 1 dalam rentetan binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!