Parität in der Anzahl der Buchstaben mit gleicher Buchstabenposition und Häufigkeitsparität

In dieser Frage zählen wir die Anzahl der Zeichen mit gleicher Parität in Häufigkeit und Position und geben die Anzahl dieser Zahl als ungerade oder gerade aus.

Um dieses Problem zu lösen, können wir die Häufigkeit jedes Zeichens in der Zeichenfolge ermitteln und die Gesamtzahl der Zeichen mit derselben Parität in Häufigkeit und Position zählen. Danach können wir basierend auf der Zählung ungerade oder gerade Antworten ausdrucken.

Problemstellung – Wir erhalten eine Zeichenfolge alpha, die nur englische Kleinbuchstaben enthält. Wir müssen prüfen, ob die Anzahl der Zeichen mit derselben Buchstabenposition und -häufigkeit ungerade oder gerade ist.

Wenn ein Zeichen eine der folgenden Bedingungen erfüllt, hat das Zeichen die gleiche Häufigkeit und Buchstabenpositionsparität.

• Wenn die Zeichenhäufigkeit in der Zeichenfolge ungerade ist und auch die Buchstabenposition ungerade ist.

• Wenn die Zeichenhäufigkeit in der Zeichenfolge gerade ist und die Buchstabenposition ebenfalls gerade ist.

Beispiel

Eintreten

alpha = "dbbabcdc"

Ausgabe

Even

Anleitung

• a hat eine Häufigkeit von 1 und eine Position von 1, daher ist die Parität gleich und die Anzahl wird 1.

• d hat eine Häufigkeit von 2 und eine Position von 4. Da die Paritätsbits gleich sind, beträgt der Zählerstand daher 2.

Der Zählwert ist 2, was eine gerade Zahl ist.

Eintreten

alpha = "ppqqr"

Ausgabe

Odd

Erklärung – Nur die Parität von „p“ ist gleich. Daher ist die Zählung 1 und die Antwort ist eine ungerade Zahl.

Eintreten

alpha = "pqqqqrrr";

Ausgabe

Even

Hinweise – Parität ist nicht für jedes Zeichen gleich. Da der Zählwert also Null ist, wird „Gerade“ ausgegeben.

Methode 1

Bei dieser Methode verwenden wir eine Kartendatenstruktur, um die Häufigkeit jedes Zeichenfolgenzeichens zu speichern. Danach zählen wir die Anzahl der Zeichen mit gleicher Parität in Buchstabenposition und Häufigkeit.

Algorithmus

Schritt 1 – Definieren Sie ein count[]-Array mit der Länge 27 und initialisieren Sie es mit 0. Initialisieren Sie außerdem „Parität“ mit 0.

Schritt 2 – Zeichenhäufigkeiten im Array count[] speichern.

Schritt 3 – Machen Sie 26 Iterationen, um jedes Kleinbuchstabenzeichen durchzugehen.

Schritt 4 – Wenn count[p] größer als 0 ist, prüfen Sie, ob Zeichenhäufigkeit und Position die gleiche Parität haben. Wenn ja, erhöhen Sie den Paritätswert um 1.

Schritt 5 – Wenn die Parität schließlich durch 2 teilbar ist, geben Sie „Gerade“ zurück. Andernfalls geben Sie „ungerade“ zurück.

Beispiel

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

string getParity(string alpha) {
    // To store the count of characters
    int count[27] = {0};
    int parity = 0;
    // Count frequency of each character
    for (int p = 0; p < alpha.size(); p++) {
        count[alpha[p] - 'a' + 1]++;
    }
    for (int p = 1; p <= 26; p++) {
        if (count[p] != 0) {
            // Increment parity for valid odd and even parity
            if (p % 2 == 0 && count[p] % 2 == 0 || p % 2 == 1 && count[p] % 2 == 1)
                parity++;
        }
    }
    // Return value based on final parity count
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "dbbabcdc";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

Ausgabe

The parity of given string's character's is EVEN

Zeitkomplexität – O(N) zur Berechnung der Häufigkeit von Zeichen.

Raumkomplexität – O(26) ~ O(1) zum Speichern der Häufigkeit alphabetischer Zeichen.

Methode 2

In dieser Methode sortieren wir die angegebene Zeichenfolge. Wenn wir danach unterschiedliche benachbarte Zeichen erhalten, überprüfen wir die Häufigkeit und Positionsparität des vorherigen Zeichens.

Algorithmus

Schritt 1 – „Parität“ auf 0 initialisieren.

Schritt 2 – Die Methode sort() wird zum Sortieren der angegebenen Zeichenfolge verwendet.

Schritt 3 – Beginnen Sie mit dem Durchlaufen der Zeichenfolge und initialisieren Sie „charCnt“ auf 0, um die Häufigkeit des aktuellen Zeichens zu speichern.

Schritt 4 – Wenn sich das aktuelle Zeichen vom nächsten Zeichen unterscheidet, prüfen Sie, ob die Parität und die Zeichenposition von „charCnt“ übereinstimmen. Wenn ja, erhöhen Sie die Parität um 1.

Schritt 5 – Wenn das aktuelle Zeichen mit dem vorherigen Zeichen übereinstimmt, erhöhen Sie „charCnt“ um 1.

Schritt 6 – Wenn der „Parität“-Wert schließlich gerade ist, geben Sie „Gerade“ zurück. Andernfalls geben Sie „ungerade“ zurück.

Beispiel

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

string getParity(string alpha) {
    int parity = 0;
    // Sort the string
    sort(alpha.begin(), alpha.end());
    // Traverse the string
    for (int p = 0; p < alpha.size(); p++) {
        int charCnt = 0;        
        // When we get different adjacent characters
        if (alpha[p] != alpha[p + 1]) {
            // Validating the odd and even parties
            if (charCnt % 2 == 1 && (alpha[p] - 'a' + 1) % 2 == 1 || charCnt % 2 == 0 && (alpha[p] - 'a' + 1) % 2 == 0)
                parity++;
        } else {
            charCnt++;
        }
    }
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "abbbccdd";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

Ausgabe

The parity of given string's character's is EVEN

Zeitkomplexität – O(NlogN) zum Sortieren von Zeichenfolgen.

Raumkomplexität – O(N) zum Sortieren von Zeichenfolgen.

Die erste Methode benötigt konstanten Speicherplatz, während die zweite Methode dynamischen Speicherplatz zum Sortieren der angegebenen Zeichenfolge benötigt. Darüber hinaus ist die zweite Methode mit einem höheren Zeitaufwand verbunden, daher wird für eine bessere Leistung empfohlen, die erste Methode zu verwenden.

Das obige ist der detaillierte Inhalt vonParität in der Anzahl der Buchstaben mit gleicher Buchstabenposition und Häufigkeitsparität. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!