Bilangan minimum penyingkiran untuk membuat rentetan terdiri daripada rentetan 0s diikuti dengan rentetan 1s

Soalan "Pemadaman minimum untuk penyambungan rentetan 0 subrentetan" melibatkan kerja dengan rentetan. Diberikan sebagai input rentetan 0s dan 1s, hasilnya ialah integer yang mencerminkan bilangan minimum 0s yang mesti dihapuskan untuk menjana subrentetan 0s berturut-turut.

Dalam erti kata lain, masalah itu boleh dirumuskan semula sebagai: diberi rentetan yang terdiri daripada 0s dan 1s, berapa 0s yang perlu dihapuskan untuk menjadikan rentetan yang tinggal mengandungi tempoh berterusan 0s.

Algoritma

Langkah pertama: permulaan pembolehubah

• Tentukan pembolehubah kiraan untuk merekodkan panjang jujukan sifar semasa.

• Tentukan pembolehubah max_count untuk menjejaki jujukan sifar terpanjang yang ditemui setakat ini.

• Tetapkan kedua-dua pembolehubah kepada 0.

Langkah 2: Rentas rentetan

Gunakan gelung untuk mengulangi setiap aksara dalam rentetan.

Langkah ketiga: pengesanan sifar

Jika aksara semasa ialah sifar, naikkan pembolehubah kiraan.

Langkah 4: Satu ujian

• Jika aksara semasa ialah 1, bandingkan pembolehubah kiraan dengan pembolehubah max_count.

• Jika pembolehubah kiraan lebih tinggi daripada pembolehubah max_count, tetapkan pembolehubah max_count sama dengan pembolehubah kiraan.

• Tetapkan semula pembolehubah kiraan kepada 0.

Langkah 5: Kitaran Selesai

Ulang proses ini sehingga semua aksara dalam rentetan telah diproses.

Langkah 6: Pengiraan pemadaman minimum

Bilangan minimum pemadaman yang diperlukan untuk mengalih keluar semua sifar supaya yang selebihnya tidak dipisahkan oleh sebarang sifar boleh dikira dengan menolak max_count daripada panjang rentetan.

Langkah 7: Output Keputusan

Cetak keputusan ke konsol.

Kaedah untuk diikuti

• kaedah dinamik

• Kaedah lelaran

Kaedah 1: Kaedah dinamik

Pengaturcaraan dinamik boleh digunakan untuk menyelesaikan masalah ini dengan cekap. Untuk mencipta subrentetan 0s berturut-turut, kita boleh mencipta tatasusunan dp[], dengan dp[i] mewakili bilangan minimum 0s yang perlu dihapuskan daripada subrentetan s[0...i]. Bilangan minimum 0s untuk dihapuskan daripada subrentetan kosong ialah 0, jadi kita boleh memulakan dp[0] kepada 0.

Kemudian, kita boleh mengulangi rentetan s dan mengemas kini dp[i] kepada −

• Jika s[i] ialah "0", maka dp[i] = dp[i-1], kerana kita boleh memasukkan s[i] dalam subrentetan 0 berturut-turut atau padam.

• Apabila s[i] ialah "1", kita mesti mendapatkan indeks j yang paling hampir dengan i, yang mengandungi subrentetan 0s berturut-turut. Ini boleh dilakukan dengan mengulangi daripada i-1 kepada 0 dan melihat sama ada subrentetan s[j...i] mengandungi 0 berturut-turut. Jika indeks j ditemui, maka dp[i] = dp[j-1] + (i-j+1), dengan dp[j-1] mewakili bilangan minimum 0 yang mesti disingkirkan daripada subrentetan s[. . .j-1] dan (i-j+1) ialah jumlah bilangan 1 yang mesti dihapuskan untuk mendapatkan subrentetan s[j...i] 0 berturut-turut. Jika tiada indeks j seperti itu ditemui, maka dp[i] = dp[i-1], kerana kita tidak boleh mengandungi s[i] dalam subrentetan 0s berturut-turut.

  Akhir sekali, untuk mendapatkan subrentetan 0s berturut-turut, bilangan minimum 0s yang perlu dikeluarkan daripada keseluruhan rentetan s diberikan oleh dp[n-1], dengan n ialah panjang rentetan s .

Contoh 1

Atur cara berikut menggunakan kaedah yang kita bincangkan di atas dengan terlebih dahulu membaca rentetan input daripada input standard dan kemudian mengenal pasti semua subrentetan 0. Kemudian hitung panjang 0 subrentetan terpanjang dan panjang rentetan yang dijana dengan menggabungkan setiap 0 subrentetan. Untuk menentukan bilangan minimum penyingkiran yang diperlukan, ia akhirnya menolak panjang 0 subrentetan terpanjang daripada jumlah kesemua 0 subrentetan dan memaparkan hasilnya kepada output standard.

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

int main() {
   string s = "100100011000110"; // constant input string

   vector<pair<int, int>> substrings; // vector to store start and end indices of each substring of 0s

   int start = -1;
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '0') {
         if (start == -1) {
         start = i;
         }
      } else {
         if (start != -1) {
         substrings.push_back(make_pair(start, i - 1));
         start = -1;
         }
      }
   }
   if (start != -1) {
      substrings.push_back(make_pair(start, s.length() - 1));
   }

   int totalLength = 0;
   for (auto& p : substrings) {
      totalLength += p.second - p.first + 1;
   }

   int maxLength = 0;
   for (auto& p : substrings) {
      int len = p.second - p.first + 1;
      if (len > maxLength) {
         maxLength = len;
      }
   }

   int removals = totalLength - maxLength;
   cout << "Input string: " << s << endl;
   cout << "Minimum removals: " << removals << endl;

   return 0;
}

Output

Input string: 100100011000110
Minimum removals: 6

Kaedah 2: Kaedah berulang

Kaedah ini menggunakan kaedah lelaran terus untuk melintasi aksara rentetan yang diberikan mengikut aksara sambil mengemas kini nilai dua pembolehubah kiraan dan max_count. Kaedah ini mengemas kini nilai pembolehubah kiraan dan max_count berdasarkan sama ada aksara semasa ialah 0 atau 1. Ia kemudian memberikan perbezaan antara max_count dan panjang 0 subrentetan terpanjang.

Terjemahan bahasa Cina bagi

Contoh 2

ialah:

Contoh 2

Kod ialah perisian C++ yang mengira bilangan minimum penyingkiran yang diperlukan untuk mengalih keluar semua sifar daripada rentetan binari supaya selebihnya tidak dipisahkan oleh sebarang sifar. Fungsi min_deletions mengambil rentetan binari sebagai input dan menggunakan gelung untuk melelaran melalui setiap aksara dalam rentetan. Gelung menambah pembolehubah kiraan setiap kali ia menemui sifar dan menetapkannya semula kepada sifar apabila ia menemui satu. Nilai maksimum pembolehubah kiraan disimpan dalam max_count, dan akhirnya panjang rentetan ditolak daripada max_count untuk mendapatkan bilangan pemadaman minimum yang diperlukan. Hasilnya kemudian dipaparkan kepada pengguna.

#include <iostream> 
#include <string> 
using namespace std; 
 
int min_deletions(string str) { 
   int count = 0, max_count = 0; 
   for (char c : str) { 
      if (c == '0') { 
         count++; 
      } else { 
         max_count = max(max_count, count); 
         count = 0; 
      } 
   } 
    return str.length() - max_count; 
} 
 
int main() { 
   string str = "100010011000110"; 
   int deletions = min_deletions(str); 
   cout << "Minimum deletions needed: " << deletions << endl; 
   return 0; 
} 

Output

Minimum deletion needed: 12 

KESIMPULAN

Menentukan semua subrentetan 0, mengira panjang rentetan yang dihasilkan dengan menggabungkan setiap subrentetan 0, dan menentukan panjang subrentetan terpanjang 0 ialah tiga langkah untuk menyelesaikan masalah yang diberikan. Panjang 0 subrentetan terbesar kemudiannya boleh ditolak daripada jumlah kesemua 0 subrentetan untuk mendapatkan bilangan pemadaman minimum yang diperlukan.

Kaedah yang kami gunakan untuk mendapatkan jawapan adalah mudah, cekap dan berjalan dalam masa linear, menjadikannya sesuai untuk input yang besar. Tetapi ia boleh dipertingkatkan lagi dengan menggunakan kaedah yang lebih canggih seperti pengaturcaraan dinamik.

Atas ialah kandungan terperinci Bilangan minimum penyingkiran untuk membuat rentetan terdiri daripada rentetan 0s diikuti dengan rentetan 1s. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!