Apakah bilangan minimum pertukaran yang diperlukan supaya subrentetan yang diberikan mengandungi tepat K 1?

Mencari bilangan swap minimum yang diperlukan untuk subrentetan mengandungi K yang tepat adalah masalah biasa dalam sains komputer dan pengaturcaraan. Dalam artikel ini, kami akan menyelidiki masalah ini dan menyediakan penyelesaian C++ untuknya. Soalan ini mempunyai aplikasi dalam pelbagai bidang, termasuk manipulasi rentetan, pengoptimuman struktur data dan cabaran pengekodan dalam temu bual.

Pernyataan Masalah

Memandangkan rentetan binari dan nombor K, tugasnya adalah untuk mencari bilangan swap minimum yang diperlukan untuk memastikan setiap subrentetan rentetan mempunyai K yang tepat.

Kaedah

Untuk menyelesaikan masalah ini, kita boleh menggunakan kaedah dua mata dan teknologi tingkap gelongsor. Idea asas adalah untuk mengekalkan tetingkap saiz K dan mengira bilangan swap yang diperlukan untuk semua 1 dalam tetingkap.

Contoh

Ini adalah fungsi C++ yang melaksanakan kaedah di atas -

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

int minSwaps(string s, int K) {
   int n = s.length();
   vector<int> onesPrefix(n, 0);
   if(s[0] == '1') onesPrefix[0] = 1;
   
   for(int i = 1; i < n; i++) {
      onesPrefix[i] = onesPrefix[i-1];
      if(s[i] == '1') onesPrefix[i]++;
   }
   
   int ans = INT_MAX;
   for(int i = 0; i <= n - K; i++) {
      int j = i + K - 1;
      int ones = onesPrefix[j] - ((i == 0) ? 0 : onesPrefix[i - 1]);
      ans = min(ans, K - ones);
   }
   
   return ans;
}

int main() {
   string s = "10010110";
   int K = 3;
   cout << "Minimum number of swaps = " << minSwaps(s, K) << endl;
   return 0;
}

Output

Minimum number of swaps = 1

Perihalan kes ujian

Katakan rentetan itu ialah "10010110", K = 3.

Dalam rentetan binari awal "10010110", kita mahu mempunyai tepat 3 1 dalam setiap subrentetan saiz 3. Sebagai contoh, subrentetan "100" memerlukan 2 pertukaran untuk menjadi "111". Begitu juga, subrentetan "001" juga memerlukan 2 pertukaran. Dengan mengulangi rentetan, kami mendapati bahawa bilangan swap minimum yang diperlukan untuk subrentetan "101" ialah 1.

Kesimpulan

Soalan ini ialah contoh yang bagus tentang cara menggabungkan pemahaman tentang algoritma, struktur data dan bahasa C++ untuk menyelesaikan masalah yang kompleks. Memahami dan melaksanakan soalan sedemikian boleh menjadi sangat bermanfaat untuk jurutera perisian, terutamanya dalam wawancara pengekodan dan pengaturcaraan kompetitif.

Atas ialah kandungan terperinci Apakah bilangan minimum pertukaran yang diperlukan supaya subrentetan yang diberikan mengandungi tepat K 1?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!