Maison > développement back-end > C++ > le corps du texte

Maximiser le nombre de 0 à retourner dans un tableau binaire donné de telle sorte qu'il y ait au moins K 0 entre deux 1

王林
Libérer: 2023-08-26 19:49:06
avant
1358 Les gens l'ont consulté

Maximiser le nombre de 0 à retourner dans un tableau binaire donné de telle sorte quil y ait au moins K 0 entre deux 1

Un tableau binaire est un type spécial de tableau qui contient uniquement les nombres 0 et 1. Dans ce problème, on nous donne un tableau binaire et un entier K. Notre tâche est de calculer le nombre maximum de 0 pouvant être transformés en 1 dans un tableau binaire donné de telle sorte qu'il y ait au moins K 0 entre deux 1.

Exemple Exemple

Input 1: arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },  K = 2
Copier après la connexion
Output 1: yes
Copier après la connexion
La traduction chinoise de

Explication

est :

Explication

Les 3ème et 6ème indices du tableau ci-dessus sont les seuls indices valides et peuvent être inversés pour garantir qu'il y a au moins 2 0 entre les deux 1. Le tableau résultant est donc {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}

Input 2: arr[] = {0, 1, 0, 0, 0, 1}, k = 1
Copier après la connexion
Output 2: 1
Copier après la connexion
La traduction chinoise de

Explication

est :

Explication

Le 3ème index du tableau ci-dessus est le seul index inversé valide.

Approche

Nous avons vu l’exemple donné ci-dessus avec tableau et entier k, passons à la méthode −

L'idée de cette méthode est de compter le nombre de 0 consécutifs entre deux 1 et de vérifier s'il convient de retourner des 0 en 1 entre eux. Supposons qu’il y ait X zéros entre deux uns. Selon l'observation, le nombre de 0 pouvant être inversés est (X-K) / (K+1). Alors, parcourez le tableau et enregistrez combien de 0 consécutifs il y a entre chaque paire de 1. Ensuite, ajoutez le nombre de 0 pouvant être inversés au nombre de variables, qui correspond à la réponse souhaitée.

Discutons de la méthode ci-dessous étape par étape-

  • Tout d'abord, nous allons créer une fonction appelée « onesCount » qui prendra le tableau donné « arr » et l'entier « K » comme paramètres et renverra l'entier requis « count » comme valeur de retour.

  • Créez le nombre de variables et lastIdx.

  • Initialisez la variable count avec 0 pour stocker le nombre de fillip 0.

  • Initialisez la variable lastIdx en utilisant (-(K+1)) pour stocker le dernier index du tableau avec une valeur de 1.

  • Utilisez une boucle for pour parcourir le tableau, vérifiez si l'élément actuel est 1, puis vérifiez s'il y a suffisamment de 0 entre deux 1 consécutifs pour ajouter un autre 1. Enfin, mettez à jour la valeur d'index du dernier 1.

  • Écrivez une condition qui compte le dernier segment de 0 dans le tableau et ajoutez-le au nombre de variables.

  • Enfin, notre décompte final de réponses est renvoyé.

La traduction chinoise de

Exemple

est :

Exemple

Vous trouverez ci-dessous un programme C++ permettant de calculer la conversion maximale de 0 en 1 pour garantir qu'il y a au moins k 0 entre deux 1.

#include <bits/stdc++.h>
using namespace std; 
// Function to find the count of the maximum number of 0s to be filliped 
int onesCount(int arr[], int n, int k){
   int count = 0; // Stores the count of 1's 
   int lastIdx = -(k + 1); // Stores the last index of value 1 
   
   // Traverse the array using for loop
   for (int i = 0; i < n; i++) { 
      // If the current element is 1
      if (arr[i] == 1) { 
      
         // Verify whether there are enough 0s between two consecutive 1s to add another 1 in between them.
         if (i - lastIdx - 1 >= 2 * (k - 1)) {
            count += (i - lastIdx - 1 - k) / (k + 1);
         } 
         lastIdx = i; // Update the last index of the value 1 of the array
      }
   } 
   
   // condition to include the last section of 0s in the array
   count += (n - lastIdx - 1) / (k + 1);
 
   // Return the answer
   return count;
} 
int main(){
   int arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }; // given array
   int N = sizeof(arr) / sizeof(arr[0]); //getting size of an array
   int K = 2; //given integer 
   
   // Call the function
   int result = onesCount(arr, N, K);    
   cout<< "The count of Maximum filliped of 0's is "<< result ;
   return 0;
}
Copier après la connexion

Sortie

The Count of Maximum filliped of 0's is 2
Copier après la connexion

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N) car nous parcourons uniquement le tableau. où N est la taille du tableau donné.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme pour trouver le nombre maximum de 0 à retourner dans un tableau binaire donné afin qu'il y ait au moins K 0 entre deux 1. Ce problème est résolu en comptant le nombre de zéros consécutifs entre deux 1 et en vérifiant s'il est approprié d'inverser quelques zéros entre eux. La complexité temporelle est O(N) et la complexité spatiale est O(1). où N est la taille de la chaîne.

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!

source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!