Maximieren Sie die Anzahl der Nullen, die in einem bestimmten binären Array umgedreht werden sollen, sodass zwischen zwei Einsen mindestens K Nullen liegen

Binäres Array ist ein spezieller Array-Typ, der nur die Zahlen 0 und 1 enthält. In diesem Problem erhalten wir ein binäres Array und eine ganze Zahl K. Unsere Aufgabe besteht darin, die maximale Anzahl von Nullen zu berechnen, die in einem gegebenen binären Array in Einsen umgewandelt werden können, sodass zwischen zwei Einsen mindestens K Nullen liegen.

Beispiel Beispiel

Input 1: arr[] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },  K = 2

Output 1: yes

Erklärung

Erklärung

Der 3. und 6. Index im obigen Array sind die einzigen gültigen Indizes und können umgedreht werden, um sicherzustellen, dass zwischen den beiden Einsen mindestens 2 Nullen liegen. Das resultierende Array ist also {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0}

Input 2: arr[] = {0, 1, 0, 0, 0, 1}, k = 1

Output 2: 1

Erklärung

Erklärung

Der 3. Index des obigen Arrays ist der einzige gültige umgedrehte Index.

Ansatz

Wir haben das oben gegebene Beispiel mit Array und Ganzzahl k gesehen, fahren wir mit der Methode −

Die Idee dieser Methode besteht darin, die Anzahl aufeinanderfolgender Nullen zwischen zwei Einsen zu zählen und zu prüfen, ob es geeignet ist, einige Nullen zwischen ihnen in Einsen umzudrehen. Angenommen, zwischen zwei Einsen liegen X Nullen. Laut Beobachtung beträgt die Anzahl der Nullen, die umgedreht werden können, (X-K) / (K+1). Gehen Sie also das Array durch und notieren Sie, wie viele aufeinanderfolgende Nullen zwischen jedem Paar von Einsen liegen. Addieren Sie dann die Anzahl der Nullen, die umgedreht werden können, zur Variablenanzahl, was die gewünschte Antwort darstellt.

Lassen Sie uns die folgende Methode Schritt für Schritt besprechen –

• Zunächst erstellen wir eine Funktion namens „onesCount“, die das angegebene Array „arr“ und die Ganzzahl „K“ als Parameter verwendet und die erforderliche Ganzzahl „count“ als Rückgabewert zurückgibt.

• Erstellen Sie die Variablen count und lastIdx.

• Initialisieren Sie die Variablenanzahl mit 0, um die Anzahl der Füllnullen zu speichern.

• Initialisieren Sie die Variable lastIdx mit (-(K+1)), um den letzten Index im Array mit dem Wert 1 zu speichern.

• Verwenden Sie eine for-Schleife, um das Array zu durchlaufen, prüfen Sie, ob das aktuelle Element 1 ist, und überprüfen Sie dann, ob zwischen zwei aufeinanderfolgenden Einsen genügend Nullen vorhanden sind, um eine weitere 1 hinzuzufügen. Aktualisieren Sie abschließend den Indexwert der letzten 1.

• Schreiben Sie eine Bedingung, die das letzte Segment von 0 im Array zählt, und fügen Sie es zur Variablenanzahl hinzu.

• Schließlich wird unsere endgültige Antwortanzahl zurückgegeben.

Beispiel

Beispiel

Unten finden Sie ein C++-Programm zur Berechnung der maximalen Konvertierung von Nullen in Einsen, um sicherzustellen, dass zwischen zwei Einsen mindestens k Nullen liegen.

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

Ausgabe

The Count of Maximum filliped of 0's is 2

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), da wir nur das Array durchlaufen. wobei N die Größe des angegebenen Arrays ist.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz verwenden.

Fazit

In diesem Tutorial haben wir ein Programm implementiert, um die maximale Anzahl von Nullen zu ermitteln, die in einem bestimmten Binärarray umgedreht werden sollen, sodass zwischen zwei Einsen mindestens K Nullen liegen. Dieses Problem wird gelöst, indem die Anzahl aufeinanderfolgender Nullen zwischen zwei Einsen gezählt und geprüft wird, ob es sinnvoll ist, einige Nullen dazwischen umzudrehen. Die Zeitkomplexität ist O(N) und die Raumkomplexität ist O(1). wobei N die Größe der Zeichenfolge ist.

Das obige ist der detaillierte Inhalt vonMaximieren Sie die Anzahl der Nullen, die in einem bestimmten binären Array umgedreht werden sollen, sodass zwischen zwei Einsen mindestens K Nullen liegen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!