Anzahl aller Kleinbuchstaben in jedem Präfix der Länge 1 bis N nach Durchführung der beschriebenen Operation

In diesem Problem müssen wir die angegebene Operation für jedes String-Präfix ausführen. Schließlich müssen wir die Häufigkeit jedes Zeichens zählen.

Wir können einen Greedy-Algorithmus verwenden, um dieses Problem zu lösen. Wir müssen jedes Präfix der Länge K nehmen und seine Zeichen entsprechend den gegebenen Bedingungen aktualisieren. Wir können Map verwenden, um die Häufigkeit der Zeichen in der endgültigen Zeichenfolge zu berechnen.

Problemstellung – Wir erhalten eine Zeichenfolge tr mit N Kleinbuchstaben. Zusätzlich erhalten wir eine Mapping-Liste, die insgesamt 26 Elemente enthält. Jedes Element wird basierend auf seinem Wert Kleinbuchstaben zugeordnet. Beispielsweise wird Mapping[0] auf „a“, Mapping[1] auf „b“ und Mapping[25] auf „z“ abgebildet. Darüber hinaus enthält das zugeordnete Array 1 oder -1.

Wir müssen Folgendes tun.

• Ermitteln Sie die maximale Anzahl an Zeichen aus einem Präfix der Länge K und den Mapping-Wert aus dem Array „mapping“.

• Wenn der zugeordnete Wert 1 ist, erhöhen Sie alle Präfixelemente um 1.

• Wenn der zugeordnete Wert -1 ist, dekrementieren Sie alle Präfixelemente um 1.

Hier bedeutet das Hinzufügen von Elementen „a“ −> „b“, „b“ −> „z“ −>

Abnehmende Elemente bedeuten „a“->„z“, „b“->„a“,…. „z“->„y“.

Wir müssen das Obige für jedes Präfix der Länge 1

Beispiel Beispiel

Eintreten

mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = ‘progress’

Ausgabe

0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0

Anleitung

• In einem Präfix der Länge 1 ist das größte Zeichen „p“, was -1 entspricht. Daher lautet die aktualisierte Zeichenfolge „orogress“.

• In einem Präfix der Länge 2 ist das maximale Zeichen „r“ und die Zuordnung ist -1. Daher lautet die aktualisierte Zeichenfolge „nqogress“.

• In einem Präfix der Länge 3 ist das größte Zeichen „q“ und der Zuordnungswert ist 1. Daher lautet die aktualisierte Zeichenfolge „orpgress“.

• Wenn wir mit allem fertig sind, wird die letzte Zeichenfolge „pqmfpdqr“ sein, die 1 „f“, 2 „p“, 2 „q“, 1 „m“, 1 „d“ und 1 „d“ „r“ enthält '. In der Ausgabe geben wir die Häufigkeit jedes Zeichens in der resultierenden Zeichenfolge aus.

Eintreten

mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = "ab", 

Ausgabe

1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Erklärung− Nachdem alle Operationen ausgeführt wurden, ist die letzte Zeichenfolge „ac“ und wir geben die Häufigkeit jedes Zeichens aus.

Methode 1

Bei dieser Methode durchlaufen wir die Zeichenfolge und nehmen den Wert von K gleich dem Index P. Danach nehmen wir das Präfix mit der Länge P, suchen das größte Zeichen, nehmen den zugeordneten Wert und aktualisieren alle Präfixzeichen entsprechend.

Algorithmus

Schritt 1 − Definieren Sie die Variable „max_char“, um das maximale Zeichen für das angegebene Präfix zu speichern.

Schritt 2 − Initialisieren Sie ebenfalls eine Liste der Länge 26 mit Nullen, um die Häufigkeit jedes Zeichens in der endgültigen Zeichenfolge zu speichern.

Schritt 3 – Beginnen Sie mit der Schleife durch die Zeichenfolge und initialisieren Sie die Variable „max_char“ mit 96 innerhalb der Schleife.

Schritt 4 – Finden Sie mithilfe verschachtelter Schleifen das maximale Zeichen aus einem Präfix der Länge p.

Schritt 5 – Aktualisieren Sie jedes Zeichen des Präfixes, indem Sie den zugeordneten Wert von max_char hinzufügen.

Schritt 7 – Wenn das aktualisierte Zeichen kleiner als „a“ ist, aktualisieren Sie es auf „z“.

Schritt 8 – Wenn das aktualisierte Zeichen größer als „z“ ist, aktualisieren Sie es auf „a“.

Schritt 9− Speichern Sie abschließend die Häufigkeit jedes Zeichens in einer Liste, indem Sie die aktualisierte Zeichenfolge durchlaufen.

Schritt 10- Drucken Sie die Häufigkeit der Zeichen aus.

Beispiel

#include <bits/stdc++.h>
using namespace std;

void performOperations(string &str, vector<int> &mapping) {
    int len = str.length();
    char max_char;
    //  array to store the final frequency of each character
    int freq[26] = {0};
    for (int p = 0; p < len; p++) {
        max_char = 96;
        // Get the maximum character from the prefix string
        for (int q = 0; q <= p; q++) {
            max_char = max(max_char, str[q]);
        }
        // Update the prefix string by adding the max character's value.
        for (int q = 0; q <= p; q++) {
            // adding the mapping value to the current character
            str[q] += mapping[max_char - 'a'];
            // If the updated value is greater than z or less than a, update it
            if (str[q] < 'a') {
                str[q] = 'z';
            } else if (str[q] > 'z') {
                str[q] = 'a';
            }
        }
    }
    // Counting frequency of each character
    for (int p = 0; p < len; p++) {
        freq[str[p] - 'a']++;
    }
    // print count of each character in the updated string
    for (auto ch : freq) {
        cout << ch << ' ';
    }
}
int main() {
    string S = "progress";
    vector<int> mapping = {-1, 1, 1, -1, 1, 1, -1, -1,
                           -1, 1, 1, 1, -1, 1, -1, 1, -1,
                           1, -1, 1, 1, 1, -1, 1, 1, 1};
    performOperations(S, mapping);
    return 0;
}

Ausgabe

0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0

Zeitkomplexität− O(N*N), weil wir zwei verschachtelte Schleifen verwenden, um die Zeichenfolge zu durchlaufen.

Raumkomplexität− O(1), weil wir konstanten Raum verwenden, um die Häufigkeit von Zeichen zu speichern.

Fazit

Wir haben die angegebene Operation für die Eingabezeichenfolge ausgeführt und die Zeichenhäufigkeit der aktualisierten Zeichenfolge in der Ausgabe ausgegeben. Programmierer können in C++ auch Karten verwenden, um Zeichenhäufigkeiten zu speichern, anstatt Listen zu verwenden. Für mehr Übung könnte der Programmierer versuchen, die kumulative Häufigkeit jedes Zeichens in der aktualisierten Zeichenfolge auszugeben.

Das obige ist der detaillierte Inhalt vonAnzahl aller Kleinbuchstaben in jedem Präfix der Länge 1 bis N nach Durchführung der beschriebenen Operation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!