Finden Sie die Länge der längsten Teilmenge bestehend aus A 0s und B 1s aus einem String-Array

In diesem Problem müssen wir die längste Teilmenge finden, die höchstens A 0s und B1s enthält. Alles was wir tun müssen, ist alle möglichen Teilmengen mithilfe von Array-Elementen zu finden und die längste Teilmenge zu finden, die höchstens A 0 und B1 enthält.

In diesem Tutorial lernen wir zunächst die rekursive Methode zur Lösung des Problems. Danach werden wir dynamische Programmiermethoden verwenden, um den Code zu optimieren.

Problemstellung – Wir erhalten ein Array mit N Binärzeichenfolgen. Zusätzlich erhalten wir die ganzen Zahlen A und B. Wir müssen die längste Teilmenge mit der gegebenen Binärzeichenfolge erstellen, sodass sie nicht mehr als A 0 und B1 enthält.

Beispiel

Input –  arr = {"101", "0", "101", "0", "1"}, A = 2, B = 1

Output – 3

Anleitung

Die längste Teilmenge ist { „0“, „0“, „1“}, die 2 Nullen und 1 1 enthält.

Input –  arr = {"0", "101", "0", "1"}, A = 3, B = 3

Output – 3

Anleitung

Die längste Teilmenge ist {"0", "101", "0", "1"}, 3 0er und 3 1er.

Methode 1

In diesem Abschnitt lernen wir eine einfache Methode mit Rekursion kennen. Wir werden alle möglichen Teilmengen mithilfe der Array-Elemente konstruieren und die längste Teilmenge finden, die A 0 und B 1 enthält.

Algorithmus

• Schritt 1 – Definieren Sie die Funktion countZeros(), um die Gesamtzahl der Nullen in einer bestimmten Binärzeichenfolge zu zählen.

• Schritt 1.1 – Initialisieren Sie die Variable „count“ auf Null.

• Schritt 1.2 – Verwenden Sie eine for-Schleife, um über die Zeichenfolge zu iterieren.

• Schritt 1.3 – Wenn das Zeichen am i-ten Index „0“ ist, dann erhöhen Sie den Wert von „cnt“ um 1.

• Schritt 1.2 – Geben Sie den Wert der Variablen „cnt“ zurück.

• Schritt 2 – getMaxSubsetLen() gibt einen ganzzahligen Wert zurück und verwendet den Vektor arr, int A, int B und index als Argumente.

• Schritt 3 – Definieren Sie den Basisfall innerhalb der Funktion. Gibt 0 zurück, wenn der Index gleich der Größe des Vektors ist oder wenn die Werte von A und B beide Null sind.

• Schritt 4 – Zählen Sie nun die Gesamtzahl der Nullen in der Zeichenfolge am Index.

• Schritt 5 – Subtrahieren Sie die Gesamtzahl der Einsen von der Zeichenfolgenlänge, um die Gesamtzahl der Einsen zu erhalten.

• Schritt 6 – Initialisieren Sie die „erste“ Variable auf 0.

• Schritt 7 – Enthält die aktuelle Binärzeichenfolge, wenn die Gesamtzahl von 0 und 1 kleiner als A bzw. B ist. Speichert 1 + den Rückgabewert eines rekursiven Funktionsaufrufs. Bei einem rekursiven Aufruf werden 0 und 1 von A und B subtrahiert.

• Schritt 8 – Schließen Sie die aktuelle Zeichenfolge aus und speichern Sie den resultierenden Wert in der „zweiten“ Variablen.

• Schritt 9 – Geben Sie den Maximalwert des ersten und zweiten zurück.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> arr, int A, int B, int index){

   // base case
   // if all the strings are traversed, or A + B becomes 0
   if (index == arr.size() || A + B == 0){
      return 0;
   }
   
   // total number of 0's in arr[index] string
   int zero = countZeros(arr[index]);
   
   // total number of 1's in arr[index] string
   int one = arr[index].size() - zero;
   
   // Stores the length of the subset, if arr[i] is included.
   int first = 0;
   
   // if the number of 0's and 1's in arr[index] is less than or equal to A and B, respectively, then include the string
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(arr, A - zero, B - one, index + 1);
   }
   
   // Stores the length of the subset, if arr[i] is not included.
   int second = getMaxSubsetLen(arr, A, B, index + 1);
   
   // return the maximum of the first and second
   return max(first, second);
}

// Driver Code
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " <<getMaxSubsetLen(arr, A, B, 0);
   return 0;
}

Ausgabe

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Zeitkomplexität – O(2N), da wir alle möglichen Teilmengen mithilfe von N Array-Elementen finden.

Raumkomplexität – O(1)

Methode 2

Wir haben die obige Methode in diesem Abschnitt optimiert. Zur Lösung dieses Problems nutzen wir dynamische Programmiermethoden. Es speichert das Ergebnis des vorherigen Zustands, um die zeitliche Komplexität des Problems zu reduzieren.

Algorithmus

• Schritt 1 – Definieren Sie die Funktion countZeros(), um die Gesamtzahl der Nullen in einer bestimmten Binärzeichenfolge zu zählen, genau wie wir es in der obigen Methode getan haben.

• Schritt 2 – Erstellen Sie einen 3D-Vektor der Größe A x B x N, um das Ergebnis des vorherigen Zustands zu speichern. In der Liste speichern wir die Länge der Teilmenge am Index „I“, wenn die Summe 0 gleich A und 1 gleich B ist. Übergeben Sie es außerdem als Argument an die Funktion getMaxSubsetLen().

• Schritt 3 – Definieren Sie den Basisfall wie in der obigen Methode.

• Schritt 4 – Wenn der Wert von dpTable[A][B][index] größer als 0 ist, bedeutet dies, dass der Status berechnet wurde und sein Wert zurückgegeben wird.

• Schritt 5 – Zählen Sie die Gesamtzahl der Nullen und Einsen in der aktuellen Zeichenfolge.

• Schritt 6 – Erhalten Sie den resultierenden Wert einschließlich und ohne die aktuelle Zeichenfolge.

• Schritt 7 – Verwenden Sie die Funktion max(), um den Maximalwert des ersten und zweiten Wertes zu erhalten, speichern Sie ihn in dpTable[A][B][index] und geben Sie ihn zurück

Beispiel

#include <bits/stdc++.h>
using namespace std;
// function to count the number of 0's in a string
int countZeros(string s){

   // initialize count variable to 0
   int count = 0;
   
   // traverse the string
   for (int i = 0; i < s.size(); i++){
   
      // if the current character is 0, the increment count
      if (s[i] == '0'){
         count++;
      }
   }
   
   // return count
   return count;
}

// recursive function to find the maximum length of a subset of strings according to the given condition.
int getMaxSubsetLen(vector<string> array, int A, int B, int index, vector<vector<vector<int>>> &dpTable){

   // base case
   if (index == array.size() || A + B == 0){
      return 0;
   }
   
   // return if already calculated
   if (dpTable[A][B][index] > 0){
      return dpTable[A][B][index];
   }
   
   // total number of 0's in the current string
   int zero = countZeros(array[index]);
   
   // total number of 1's in the current string
   int one = array[index].size() - zero;
   
   // to store the length of the subset can be formed by including the current string
   int first = 0;
   
   // if the total number of 0's and 1's in the current string is less than or equal to A and B, respectively
   if (zero <= A && one <= B){
      first = 1 + getMaxSubsetLen(array, A - zero, B - one, index + 1, dpTable);
   }
   
   // to store the length of the subset can be formed by excluding the current string
   int second = getMaxSubsetLen(array, A, B, index + 1, dpTable);
   
   // store the maximum of the first and second, and return
   return dpTable[A][B][index] = max(first, second);
}
int main(){
   vector<string> arr = {"101", "0", "101", "0", "1"};
   int A = 2, B = 1;
   vector<vector<vector<int>>> dpTable(A + 1, vector<vector<int>>(B + 1, vector<int>(arr.size() + 1, 0)));
   cout << "The maximum length of the subset consisting at most A 0s and B 1s is - " << getMaxSubsetLen(arr, A, B, 0, dpTable);
   return 0;
}

Ausgabe

The maximum length of the subset consisting at most A 0s and B 1s is - 3

Zeitkomplexität – O(A*B*N), da wir die 3D-Liste füllen müssen, um das Ergebnis zu erhalten.

Raumkomplexität – O(A*B*N), da wir 3D-Listen für die dynamische Programmiermethode verwenden.

Das obige ist der detaillierte Inhalt vonFinden Sie die Länge der längsten Teilmenge bestehend aus A 0s und B 1s aus einem String-Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!