Zählen Sie anhand der angegebenen Zeichen die Anzahl der Zeichenfolgen der Länge 3, die mindestens 2 verschiedene Zeichen enthalten

Geben Sie uns drei ganze Zahlen „a“, „b“ und „c“, die die Häufigkeit des Auftretens der drei verschiedenen Zeichen „A“, „B“ und „C“ darstellen. Wir müssen die Anzahl der verschiedenen Zeichenfolgen ermitteln, die mit diesen Zeichen gebildet werden können, und es müssen mindestens zwei verschiedene Zeichen in der gebildeten Zeichenfolge vorhanden sein. Wir werden zwei Möglichkeiten sehen, dieses Problem zu lösen: eine ist naiv und die andere ist mathematisch.

Beispiel

Input 1: a = 3, b = 2, c = 4 

Output:  3 

Anleitung

Wir können drei Zeichenfolgen „ABC“, „ABC“ und „ACC“ erstellen. Wir verwenden in diesen Zeichenfolgen „A“ dreimal, „B“ zweimal und „C“ viermal, was der gleichen oder einer geringeren Häufigkeit entspricht als angegeben, und alle Zeichenfolgen enthalten mindestens zwei verschiedene Zeichen. p>

Input 2: a = 1, b = 3, c = 10

Output: 4

Anleitung

Wir können die Zeichenfolgen „ACC“, „BCC“, „BCC“ und „BCC“ erstellen. Wir haben alle angegebenen Zeichen außer den beiden „C“ verwendet, da es keine anderen Zeichen gibt, mit denen eine neue Zeichenfolge erstellt werden könnte. Wenn wir andere Kombinationen ausprobiert hätten, wäre die endgültige Anzahl der Saiten geringer ausgefallen.

Naive Methode

Der einfachste Weg besteht darin, alle möglichen Kombinationen einer bestimmten Frequenz zu finden, aber das Problem ist, dass dies viel Zeit, Komplexität und äußerst ineffizient ist.

Wir müssen alle möglichen Teilzeichenfolgen generieren, und wenn unsere Zahlen groß sind, wird das viel Zeit und Platz in Anspruch nehmen, die ein Computer nicht bewältigen kann.

Mathematische Methoden

Ideen

Die Idee hinter diesem Ansatz ist, dass wir mindestens zwei unterschiedliche Zeichen in der Zeichenfolge benötigen, daher werden wir uns immer auf das am wenigsten häufige Zeichen konzentrieren.

Die maximale Anzahl von Zeichenfolgen, die wir erstellen können, ist (a+b+c)/3, und die mögliche Anzahl hängt nur von der Häufigkeit des Auftretens von mindestens zwei ab.

Angenommen, wenn mindestens zwei Frequenzen x und y sind und ihre Summe größer oder gleich (a+b+c)/3 ist, können wir diesen Wert als Antwort ausgeben, andernfalls ist die Summe von x und y die Antwort.

Umsetzung

Wir haben Beispiele und Ideen für die Lösungsfindung gesehen, jetzt beginnen wir mit der Implementierung des Codes -

• Zunächst erstellen wir eine Funktion, die drei Ganzzahlen akzeptiert und eine Ganzzahl zurückgibt.

• In der Funktion speichern wir zunächst alle Ganzzahlen in einem Vektor und sortieren dann den Vektor, um die Ganzzahl mit der minimalen Häufigkeit zu erhalten.

• Wir ermitteln die Summe aller angegebenen Elemente und teilen sie dann durch 3, um die maximale Anzahl an Zeichenfolgen zu erhalten, die wir erstellen können.

• Später vergleichen wir den Wert der größten Zeichenfolge mit dem Wert der kleinsten Summe zweier Frequenzen. Wenn die Summe kleiner ist, aktualisieren wir die maximale Zeichenfolge so, dass sie die Summe von mindestens zwei Frequenzelementen ist.

• Abschließend geben wir den Wert der größtmöglichen Zeichenfolge zurück und geben ihn in der Hauptfunktion aus.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int count(int a, int b, int c){
   // storing the values in the vector 
   vector<int>temp(3);
   temp[0] = a;
   temp[1] = b;
   temp[2] = c; 
   
   // sorting the vector to get the minimum two elements 
   sort(temp.begin(), temp.end());
   
   // counting the sum of all the elements 
   int maxStrings = (a+b+c)/3;    
   if(temp[0] + temp[1] < maxStrings){
      maxStrings = temp[0] + temp[1];
   }    
   return maxStrings; // returning the final answer
}
int main(){

   // given numbers 
   int a = 3;
   int b = 2;
   int c = 4;
   cout<<"The count of 3 length strings using given characters containing at least 2 different characters is "<<count(a,b,c)<<endl;   
   return 0;
}

Ausgabe

The count of 3 length strings using given characters containing at least 2 different characters is 3

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes ist O(1) oder konstant, da wir keine Schleifen oder rekursiven Aufrufe verwenden, um das Ergebnis zu erhalten.

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

Fazit

In diesem Tutorial haben wir ein Programm implementiert, um Zeichenfolgen mit einer Länge von 3 und einer Anzahl von 3 zu finden, indem bestimmte Zeichen verwendet werden, die mindestens 2 verschiedene Zeichen enthalten. Wir diskutierten einfache Methoden und implementierten mathematische Methoden mit konstanter zeitlicher und räumlicher Komplexität, d. h. O(1).

Das obige ist der detaillierte Inhalt vonZählen Sie anhand der angegebenen Zeichen die Anzahl der Zeichenfolgen der Länge 3, die mindestens 2 verschiedene Zeichen enthalten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!