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
Nach dem Login kopieren
Output 1: yes
Nach dem Login kopieren
Die chinesische Übersetzung von
Erklärung
lautet:
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
Nach dem Login kopieren
Output 2: 1
Nach dem Login kopieren
Die chinesische Übersetzung von
Erklärung
lautet:
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 −
fort
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.
Die chinesische Übersetzung von
Beispiel
lautet:
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;
}
Nach dem Login kopieren
Ausgabe
The Count of Maximum filliped of 0's is 2
Nach dem Login kopieren
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!
