Finden Sie den Wert, nachdem Sie N Zeichen aus der Zeichenfolge „S“ in N Operationen unter den angegebenen Einschränkungen entfernt haben

Was sind die Verwendungsspezifikationen von Saiten?

Lösen Sie eine bestimmte Herausforderung mit der angegebenen Zeichenfolge S. Die Zeichenfolge S enthält nur englische Kleinbuchstaben und beim Entfernen von Zeichen müssen bestimmte Einschränkungen beachtet werden.

Die gegebene Einschränkung ist -

• Die Zeichenfolge S

enthält englische Kleinbuchstaben

• Nur Zeichen, die mehrmals in der Zeichenfolge vorkommen, können gelöscht werden.

• Nur aufeinanderfolgende Zeichen können gelöscht werden. Mit den folgenden Schritten können Zeichen aus einer Zeichenfolge S -

entfernt werden

• Finden Sie alle Zeichen, die beim Durchlaufen der Zeichenfolge S mehrmals vorkommen. Finden Sie alle aufeinanderfolgenden Vorkommen des Zeichens, indem Sie die Zeichenfolge S für jedes Zeichen erneut iterieren.

• Wenn die Anzahl der aufeinanderfolgenden Vorkommen von Zeichen größer oder gleich der Anzahl der Iterationen ist, löschen Sie die ersten N Vorkommen von Zeichen.

• Fahren Sie mit den Schritten 2 und 3 fort, bis alle Iterationen abgeschlossen sind.

Durch die Rückgabe der letzten Zeichenfolge S können Sie schließlich den Wert der Zeichenfolge ermitteln, nachdem N Zeichen nach N Operationen entfernt wurden.

Grammatik

Bei diesem Thema handelt es sich um eine Codierungsfrage, bei der es darum geht, eine bestimmte Zeichenfolge zu manipulieren, indem eine bestimmte Anzahl von Operationen daran ausgeführt wird. Bei jedem Vorgang werden die häufigsten Zeichen in der Zeichenfolge entfernt und die Häufigkeit jedes verbleibenden Zeichens aktualisiert. Nachdem dieser Vorgang N-mal ausgeführt wurde, wird der Endwert der Zeichenfolge berechnet, indem die Häufigkeit jedes verbleibenden Zeichens quadriert und summiert wird. Das Ziel dieses Problems besteht darin, ein Programm zu schreiben, das eine Zeichenfolge und eine Zahl N als Eingabe verwendet und den Endwert der Zeichenfolge ausgibt, nachdem N Operationen gemäß den gegebenen Einschränkungen ausgeführt wurden.

Hier ist die Syntax einer Funktion, die den Wert nach N Operationen findet, um N Zeichen der Zeichenfolge S unter den gegebenen Einschränkungen zu entfernen -

int findvalueafterNoperations(int n, string s) {
   int len = s.length();
   int freq[26] = {0};
   for (int i = 0; i < len; i++) {
      freq[s[i] - 'a']++;
   }
   sort(freq, freq + 26, greater<int>());
   for (int i = 0; i < n; i++) {
      freq[0]--; 
      sort(freq, freq + 26, greater<int>()); 
   }
   int value = 0;
   for (int i = 0; i < 26; i++) {
      value += freq[i] * freq[i];
   }
   return value;
}

Diese Funktion akzeptiert zwei Parameter -

• n – eine Ganzzahl, die die Anzahl der auszuführenden Operationen darstellt.

• s – eine Zeichenfolge, die die Eingabezeichenfolge darstellt.

Die Funktion berechnet zunächst mithilfe eines Arrays die Häufigkeit jedes Zeichens in der Eingabezeichenfolge. Dieses Häufigkeitsarray wird dann in absteigender Reihenfolge sortiert und N-mal ausgeführt, wobei bei jedem Vorgang die Häufigkeit der häufigsten Zeichen verringert und das Häufigkeitsarray erneut sortiert wird.

Abschließend berechnet die Funktion den Wert der Zeichenfolge, indem sie die quadratische Häufigkeit jedes Zeichens im sortierten Häufigkeitsarray summiert und ihn als Ganzzahl zurückgibt.

Algorithmus

Nach dem Entfernen von N Zeichen berechnet der Algorithmus den Wert der Zeichenfolge unter den folgenden Einschränkungen. Die Eingabe besteht aus einer Zahl N und einer Zeichenfolge S.

• Schritt 1 – Verwenden Sie ein Array, um die Häufigkeit jedes Zeichens in der Eingabezeichenfolge zu bestimmen.

• Schritt 2 – Sortieren Sie dieses Frequenzarray in absteigender Reihenfolge.

• Schritt 3 – Führen Sie N Operationen aus, wobei jede Operation die Häufigkeit des häufigsten Zeichens im Häufigkeitsarray verringert.

• Schritt 4 – Ordnen Sie das Frequenzarray neu an.

• Schritt 5 – Addieren Sie die quadratische Häufigkeit jedes Zeichens im sortierten Häufigkeitsarray, um den Wert der Zeichenfolge zu bestimmen.

• Schritt 6 – Nach N Operationen ist der Wert der Zeichenfolge die Summe ihrer Quadrate.

Diese Technik funktioniert, weil das Problem das Entfernen von N Zeichen aus einer Eingabezeichenfolge S erfordert, was der Durchführung von N Operationen entspricht, bei denen jede Operation das häufigste Zeichen in der Zeichenfolge einmal entfernt. Aufgrund der Einschränkungen der Aufgabe können wir Zeichen nicht wirklich aus der Zeichenfolge entfernen, daher müssen wir diesen Vorgang simulieren, indem wir die Häufigkeit der häufigsten Zeichen im Häufigkeitsarray bei jedem Vorgang reduzieren.

Zu befolgende Methode

Methode 1

Verwenden Sie Code, um die Beispielzeichenfolge S und verschiedene Operationen N zu initialisieren. Nach jeder Operation in der Schleife wird das erste Zeichen entfernt, das größer als das nächste Zeichen ist. Wenn es nicht gelöscht wird, wird das letzte Zeichen gelöscht. Nachdem alle Vorgänge abgeschlossen sind, wird der Endwert der Zeichenfolge gedruckt.

Hier geht der Code davon aus, dass N kleiner oder gleich der Länge der Zeichenfolge S ist. Wenn N länger als S ist, wird der Code nicht wie erwartet ausgeführt.

Beispiel 1

#include <iostream>
#include <string>
using namespace std;
int main(){
   string S = "abcdefg";
   int N = 3;
   for (int l = 1; l <= N; l++) {
      int p=0;
      while(p<S.length()- 1) {
         if(S[p]>S[p+1]) {
            S.erase(p, 1);
            break;
         }
         p++;
      }
      if(p==S.length()- 1) {
         S.erase(p, 1);
      }
   }
   cout<< S << endl;
   return 0 ;
}

Ausgabe

a b c d

Methode 2

In diesem Code wird zunächst ein Array verwendet, um die Häufigkeit jedes Zeichens in der Eingabezeichenfolge zu bestimmen. Als nächstes führen wir N Operationen durch, verringern die Häufigkeit der häufigsten Zeichen in jeder Operation und sortieren das Häufigkeitsarray erneut. Als nächstes sortieren wir dieses Häufigkeitsarray in absteigender Reihenfolge.

Der Wert der Zeichenfolge wird letztendlich durch Addition der quadrierten Häufigkeit jedes Zeichens im sortierten Häufigkeitsarray bestimmt.

Beispiel 2

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
   // Given values
   int n = 3; 
   string s = "abcabc"; 
   int len = s.length();
   int freq[26] = {0};
   for (int i = 0; i < len; i++) {
      freq[s[i] - 'a']++;
   }
   sort(freq, freq + 26, greater<int>());
   for (int i = 0; i < n; i++) {
      freq[0]--; 
      sort(freq, freq + 26, greater<int>()); 
   }
   int value = 0;
   for (int i = 0; i < 26; i++) {
      value += freq[i] * freq[i];
   }
   cout << "Value of string after " << n << " operations: " << value << endl;
   return 0;
}

Ausgabe

Value of string after 3 operations: 3

Fazit

Zusammenfassend lässt sich sagen, dass wir unter den oben genannten Einschränkungen N Zeichen aus der Zeichenfolge „S“ entfernen können, indem wir direkte Techniken verwenden, um den Wert nach N Operationen zu erhalten. Initialisieren wir zunächst das Häufigkeitsarray, um zu verfolgen, wie viele Zeichen die Zeichenfolge enthält. Sobald wir N Zeichen eliminiert haben, können wir den Vorgang des Entfernens des Zeichens mit der größten Anzahl aus dem Häufigkeitsarray wiederholen. Dieser Vorgang kann insgesamt N-mal wiederholt werden.

Mit dieser Methode können wir nach N Operationen (einschließlich der Eliminierung von N Zeichen) schnell den Wert der Zeichenfolge „S“ ermitteln. Aufgrund der Sortierstufe in dieser Methode beträgt die zeitliche Komplexität dieser Lösung O(N logN), was für die meisten praktischen Anwendungen akzeptabel ist.

Das obige ist der detaillierte Inhalt vonFinden Sie den Wert, nachdem Sie N Zeichen aus der Zeichenfolge „S“ in N Operationen unter den angegebenen Einschränkungen entfernt haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!