Minimumkan bilangan 0s yang perlu dialih keluar untuk memaksimumkan panjang subrentetan 1 terpanjang berturut-turut

Dalam artikel ini, kami akan menyelidiki masalah menarik yang melibatkan operasi rentetan C++. Masalah yang akan kita kaji hari ini ialah bagaimana untuk "meminimumkan bilangan 0s yang perlu dipadamkan untuk memaksimumkan panjang subrentetan berterusan terpanjang 1s." Masalah ini ialah cara terbaik untuk mengasah kemahiran anda dalam manipulasi rentetan dan pengaturcaraan dinamik.

Pernyataan Masalah

Memandangkan rentetan binari, tugasnya adalah untuk meminimumkan bilangan 0 yang perlu dikeluarkan untuk memaksimumkan panjang 1 subrentetan terpanjang.

Penyelesaian C++

Untuk menyelesaikan masalah ini, kita boleh menggunakan kaedah sliding window. Kami akan mengekalkan dua penunjuk, penunjuk kiri dan penunjuk kanan. Pada mulanya, kedua-dua penunjuk menunjuk kepada elemen pertama. Kemudian kita akan terus mengalihkan penunjuk kanan ke kanan. Jika '0' ditemui, kami menambah pembilang. Jika pembilang menjadi lebih besar daripada bilangan penyingkiran sifar yang dibenarkan, kami mengalihkan penunjuk kiri ke kanan sehingga kami menemui '0' dan mengurangkan pembilang.

Kami juga akan mengekalkan maxLen pembolehubah untuk menyimpan panjang maksimum 1 subrentetan yang telah kami lihat setakat ini.

Contoh

Ini adalah kod C++ yang menyelesaikan masalah -

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

int maxSubstring(string str, int k) {
   int zeroCount = 0;
   int left = 0;
   int maxLen = 0;
   
   for (int right = 0; right < str.size(); right++) {
      if (str[right] == '0') {
         zeroCount++;
      }
      while (zeroCount > k) {
         if (str[left] == '0') {
               zeroCount--;
         }
         left++;
      }
      maxLen = max(maxLen, right - left + 1);
   }
   return maxLen;
}

int main() {
   string str = "110100110";
   int k = 2; // number of zeros that can be removed
   int result = maxSubstring(str, k);
   cout << "The maximum length of the substring of 1s is: " << result << endl;
   return 0;
}

Output

The maximum length of the substring of 1s is: 5

Perihalan kes ujian

Mari kita ambil rentetan binari "110100110", kita boleh mengeluarkan 2 sifar.

Apabila kita menghantar rentetan ini dan nilai k ke fungsi maxSubstring, ia mula mengimbas dari kiri. Setiap kali ia menemui '0', ia akan menambah zeroCount. Apabila zeroCount melebihi k, ia mula menggerakkan penunjuk kiri ke kanan sehingga ia menemui '0' dan mengurangkan zeroCount.

Dalam proses ini, ia sentiasa mengemas kini maxLen, iaitu panjang subrentetan maksimum 1s. Untuk rentetan yang diberikan, panjang subrentetan maksimum 1s tanpa mengalih keluar paling banyak 2 sifar ialah 5, iaitu subrentetan "11111" selepas mengalih keluar '0' kedua dan ketiga.

Jadi, fungsi itu akan kembali 5.

Kesimpulan

Soalan ini menunjukkan cara menggunakan teknologi tetingkap gelongsor dengan berkesan untuk menyelesaikan masalah manipulasi rentetan yang kompleks dalam C++. Ini adalah soalan yang sangat baik untuk memahami dan mempraktikkan pengaturcaraan dinamik dan teknik pemprosesan rentetan. Teruskan berlatih soalan seperti ini untuk meningkatkan kemahiran pengekodan C++ anda.

Atas ialah kandungan terperinci Minimumkan bilangan 0s yang perlu dialih keluar untuk memaksimumkan panjang subrentetan 1 terpanjang berturut-turut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!