Quel est le nombre minimum d'échanges requis pour qu'une sous-chaîne donnée contienne exactement des K 1 ?

Trouver le nombre minimum d'échanges requis pour qu'une sous-chaîne contienne exactement K uns est un problème courant en informatique et en programmation. Dans cet article, nous allons approfondir ce problème et lui proposer une solution C++. Cette question a des applications dans divers domaines, notamment la manipulation de chaînes, l'optimisation de la structure des données et les défis de codage lors des entretiens.

Énoncé du problème

Étant donné une chaîne binaire et un nombre K, la tâche consiste à trouver le nombre minimum d'échanges requis pour garantir que chaque sous-chaîne de la chaîne en a exactement K.

Méthode

Pour résoudre ce problème, nous pouvons utiliser la méthode à deux pointeurs et la technologie des fenêtres coulissantes. L'idée de base est de maintenir une fenêtre de taille K et de calculer le nombre d'échanges requis pour tous les 1 de la fenêtre.

Exemple

Il s'agit d'une fonction C++ qui implémente la méthode ci-dessus -

#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;
}

Sortie

Minimum number of swaps = 1

Description du cas de test

Supposons que la chaîne soit "10010110", K = 3.

Dans la chaîne binaire initiale "10010110", nous voulons avoir exactement 3 1 dans chaque sous-chaîne de taille 3. Par exemple, la sous-chaîne « 100 » nécessite 2 échanges pour devenir « 111 ». De même, la sous-chaîne « 001 » nécessite également 2 échanges. En parcourant la chaîne, nous constatons que le nombre minimum de swaps requis pour la sous-chaîne "101" est de 1.

Conclusion

Cette question est un excellent exemple de la façon de combiner une compréhension des algorithmes, des structures de données et du langage C++ pour résoudre un problème complexe. Comprendre et mettre en œuvre de telles questions peut être très bénéfique pour les ingénieurs logiciels, en particulier lors des entretiens de codage et de la programmation compétitive.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!