Maksimumkan bilangan aksara minoriti yang boleh dialih keluar daripada subrentetan rentetan binari yang diberikan, dilaksanakan dalam C++

Usaha semasa kami melibatkan memaksimumkan bilangan yang mana kami boleh memadam sebarang kejadian yang mengandungi aksara minoriti dalam bahagian yang terdiri sepenuhnya oleh sama ada '0' atau '1 '. Matlamat akhir hanyalah untuk mencapai pemadaman maksimum yang mungkin sambil tetap menghormati semua peraturan dan kekangan yang diberikan.

Sintaks

Untuk memastikan pemahaman yang menyeluruh tentang kod yang akan datang, mari kita mula-mula membiasakan diri dengan sintaks kaedah yang akan digunakan sebelum meneroka algoritma dan strategi −

int maximizeDeletions(string binaryString, int startIndex, int endIndex)

Algoritma

Algoritma yang memaksimumkan penyingkiran beberapa aksara dalam subrentetan rentetan binari tertentu boleh diterangkan melalui langkah berikut:

• Pertama, mari mulakan dengan memulakan pembolehubah yang dipanggil pemadaman kepada sifar. Tujuan utama pembolehubah ini adalah untuk memantau kiraan operasi pemadaman yang berlaku.

• Menentukan kekerapan digit '0' dan '1' berlaku dalam subrentetan tertentu rentetan binari. Setiap kejadian nombor ini boleh dikira secara berasingan.

• Untuk menentukan watak minoriti, kita mesti merujuk kepada kiraan yang diperolehi dalam langkah sebelumnya.

• Mengalih keluar semua aksara yang kurang kerap daripada subrentetan dan mengemas kini kiraan pemadaman dengan sewajarnya.

• Kembalikan nilai akhir yang dipadam sebagai hasilnya

Kaedah 1: Kaedah traversal

Pelaksanaan pendekatan kami melibatkan merentasi subrentetan rentetan binari secara linear dan kemudian memadamkan aksara minoriti sekaligus.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <iostream>
#include <algorithm>
using namespace std;

int maximizeDeletionsLinear(string binaryString, int startIndex, int endIndex) {
   int countZero = 0;
   int countOne = 0;

   for (int i = startIndex; i <= endIndex; i++) {
      if (binaryString[i] == '0') {
         countZero++;
      } else {
         countOne++;
      }
   }

   int deletions = endIndex - startIndex + 1 - min(countZero, countOne);
   return deletions;
}

int main() {
   string binaryString;
   int startIndex, endIndex;

   cout << "Enter the binary string: ";
   cin >> binaryString;
   cout << "Enter the start index: ";
   cin >> startIndex;
   cout << "Enter the end index: ";
   cin >> endIndex;

   int deletions = maximizeDeletionsLinear(binaryString, startIndex, endIndex);
   cout << "Maximum deletions: " << deletions << endl;
   
   return 0;
}

Output

Enter the binary string: 1011010011
Enter the start index: 2
Enter the end index: 8
Maximum deletions: 2

Penjelasan

Dalam kaedah 1, kami menggunakan traversal linear untuk memaksimumkan bilangan beberapa aksara yang dialih keluar daripada subrentetan rentetan binari yang diberikan. Dengan mengulangi subrentetan yang ditentukan, kita boleh menentukan bilangan kejadian '0' dan '1' untuk setiap kejadian dalam bahagian itu. Selepas mengenal pasti aksara yang kurang kerap dalam rantau atau kumpulan itu (iaitu mencari "minoriti"), kita boleh mengira bilangan pemadaman yang mungkin dengan menolak kiraan masing-masing daripada kiraan semua aksara dalam wilayah yang ditentukan itu.

Ini membawa kepada kaedah yang cekap yang mendedahkan penyelesaian yang mudah tetapi praktikal - hanya memerlukan satu laluan pada rentetan awal kami - yang menjadikan kaedah ini sangat sesuai untuk rentetan input yang lebih pendek.

Kaedah Kedua: Tetingkap Gelongsor

Teknik tetingkap gelongsor adalah satu lagi pendekatan yang cekap untuk menyelesaikan masalah ini Ia melibatkan penggunaan tetingkap bersaiz tetap untuk melintasi subrentetan rentetan binari

. Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <iostream>
#include <algorithm>
using namespace std;

int maximizeDeletionsSlidingWindow(string binaryString, int startIndex, int endIndex) {
   int left = startIndex;
   int right = startIndex;
   int countZero = 0;
   int countOne = 0;
   int deletions = 0;

   while (right <= endIndex) {
      if (binaryString[right] == '0') {
         countZero++;
      } else {
         countOne++;
      }

      while (min(countZero, countOne) > 0) {
         if (binaryString[left] == '0') {
            countZero--;
         } else {
            countOne--;
         }
         left++;
      }

      deletions = max(deletions, right - left + 1);
      right++;
   }

   return deletions;
}

int main() {
   string binaryString;
   int startIndex, endIndex;

   cout << "Enter the binary string: ";
   cin >> binaryString;
   cout << "Enter the start index: ";
   cin >> startIndex;
   cout << "Enter the end index: ";
   cin >> endIndex;

   int deletions = maximizeDeletionsSlidingWindow(binaryString, startIndex, endIndex);
   cout << "Maximum deletions: " << deletions << endl;

   return 0;
}

Output

Enter the binary string: Enter the start index: Enter the end index: Maximum deletions: 0

Penjelasan

Kaedah 2 melibatkan penggunaan teknik tetingkap gelongsor untuk memaksimumkan penyingkiran sebilangan kecil aksara. Menggunakan tetingkap saiz tetap, kami mengulangi subrentetan, mengemas kini kiraan '0 dan '1 apabila tetingkap bergerak. Dengan melaraskan sempadan tetingkap berdasarkan kiraan, kami mengenal pasti sebilangan kecil aksara dan mengira bilangan maksimum kemungkinan pemadaman. Pendekatan ini mengurangkan bilangan pengiraan berlebihan dengan meluncurkan tetingkap dengan cekap, menjadikannya lebih sesuai untuk input yang lebih besar dan menyediakan penyelesaian yang lebih pantas.

KESIMPULAN

Dalam artikel ini, kami meneroka masalah bagaimana untuk memaksimumkan penyingkiran sebilangan kecil aksara daripada subrentetan rentetan binari yang diberikan. Kami membincangkan dua pendekatan - traversal linear dan teknik tingkap gelongsor. Kedua-dua kaedah menyediakan penyelesaian yang cekap untuk mencapai hasil yang diinginkan. Dengan memahami algoritma dan mengkaji contoh kod boleh laku yang disediakan, anda boleh menggunakan konsep ini untuk menyelesaikan masalah yang serupa dalam projek anda sendiri. Ingat untuk menganalisis masalah, memilih pendekatan yang paling sesuai, dan melaksanakannya dengan sewajarnya.

Atas ialah kandungan terperinci Maksimumkan bilangan aksara minoriti yang boleh dialih keluar daripada subrentetan rentetan binari yang diberikan, dilaksanakan dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!