Parité dans le nombre de lettres avec la même position de lettre et parité de fréquence

Dans cette question, nous compterons le nombre de caractères avec la même parité en fréquence et en position et imprimerons le nombre de ce nombre comme impair ou pair.

Pour résoudre ce problème, nous pouvons trouver la fréquence de chaque caractère dans la chaîne et compter le nombre total de caractères ayant la même parité en fréquence et en position. Après cela, nous pouvons imprimer des réponses paires ou impaires en fonction du décompte.

Énoncé du problème - Nous recevons une chaîne alpha contenant uniquement des caractères alphabétiques anglais minuscules. Nous devons vérifier si le nombre de caractères avec la même position de lettre et la même fréquence est impair ou pair.

Si un caractère remplit l’une des conditions suivantes, alors il a la même parité de fréquence et de position de lettre.

• Si la fréquence des caractères dans la chaîne est impaire et que la position de la lettre est également impaire.

• Si la fréquence des caractères dans la chaîne est paire et que la position de la lettre est également paire.

Exemple

Entrez

alpha = "dbbabcdc"

Sortie

Even

Instructions

• a a une fréquence de 1 et une position de 1, donc la parité est la même et le décompte devient 1.

• d a une fréquence de 2 et une position de 4. Par conséquent, puisque les bits de parité sont les mêmes, le compte devient 2.

La valeur de comptage est 2, ce qui est un nombre pair.

Entrez

alpha = "ppqqr"

Sortie

Odd

Explication – Seule la parité de « p » est la même. Le compte est donc 1 et la réponse est un nombre impair.

Entrez

alpha = "pqqqqrrr";

Sortie

Even

Notes - La parité n'est pas la même pour tous les personnages. Ainsi, puisque la valeur de comptage est nulle, il imprime « Pair ».

Méthode 1

Dans cette méthode, nous utiliserons la structure de données cartographiques pour stocker la fréquence de chaque caractère de chaîne. Après cela, nous comptons le nombre de caractères avec la même parité en position et fréquence des lettres.

Algorithme

Étape 1 - Définissez un tableau count[] de longueur 27 et initialisez-le à 0. De plus, initialisez "parité" avec 0.

Étape 2 - Stockez les fréquences de caractères dans le tableau count[].

Étape 3 - Faites 26 itérations pour parcourir chaque caractère alphabétique minuscule.

Étape 4 - Si count[p] est supérieur à 0, vérifiez si la fréquence et la position des caractères ont la même parité. Si tel est le cas, augmentez la valeur de parité de 1.

Étape 5 - Enfin, si la parité est divisible par 2, retournez "Pair". Sinon, retournez "impair".

Exemple

#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;
}

Sortie

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

Complexité temporelle - O(N) pour calculer la fréquence des caractères.

Complexité spatiale - O(26) ~ O(1) pour stocker la fréquence des caractères alphabétiques.

Méthode 2

Dans cette méthode, nous trierons la chaîne donnée. Après cela, chaque fois que nous obtenons différents caractères adjacents, nous vérifions la fréquence et la parité de position du caractère précédent.

Algorithme

Étape 1 - Initialisez "Parité" à 0.

Étape 2 - La méthode sort() est utilisée pour trier la chaîne donnée.

Étape 3 - Commencez à parcourir la chaîne et initialisez « charCnt » à 0 pour stocker la fréquence du caractère actuel.

Étape 4 - Si le caractère actuel est différent du caractère suivant, vérifiez si la parité et la position du caractère de "charCnt" correspondent. Si tel est le cas, augmentez la parité de 1.

Étape 5 - Si le caractère actuel est le même que le caractère précédent, augmentez "charCnt" de 1.

Étape 6 - Enfin, si la valeur "Parité" est paire, renvoyez "Pair". Sinon, retournez "impair".

Exemple

#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;
}

Sortie

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

Complexité temporelle - O(NlogN) pour trier les chaînes.

Complexité spatiale - O(N) pour trier les chaînes.

La première méthode prend un espace constant tandis que la seconde méthode prend un espace dynamique pour trier la chaîne donnée. De plus, la deuxième méthode a un coût en temps plus élevé, il est donc recommandé d'utiliser la première méthode pour de meilleures performances.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!