Nombre de chaque caractère minuscule dans chaque préfixe de longueur 1 à N après avoir effectué l'opération décrite

Dans ce problème, nous devons effectuer l'opération donnée pour chaque préfixe de chaîne. Enfin, nous devons compter la fréquence de chaque caractère.

Nous pouvons utiliser un algorithme glouton pour résoudre ce problème. Nous devons prendre chaque préfixe de longueur K et mettre à jour ses caractères selon les conditions données. Nous pouvons utiliser map pour calculer la fréquence des caractères dans la chaîne finale.

Énoncé du problème - On nous donne une chaîne tr contenant N caractères alphabétiques minuscules. De plus, nous recevons une liste de mappage contenant un total de 26 éléments. Chaque élément est mappé en caractères minuscules en fonction de sa valeur. Par exemple, mapping[0] correspond à "a", mapping[1] correspond à "b" et mapping[25] correspond à "z". De plus, le tableau mappé contient 1 ou -1.

Nous devons faire ce qui suit.

• Obtenez le maximum de caractères d'un préfixe de longueur K et obtenez la valeur de mappage du tableau 'mapping'.

• Si la valeur mappée est 1, augmentez tous les éléments de préfixe de 1.

• Si la valeur mappée est -1, décrémentez tous les éléments de préfixe de 1.

Ici, ajouter des éléments signifie 'a' -> 'b', 'b' -> 'c',… 'z' −>

Les éléments décroissants signifient « a »-> « z », « b »-> « a »,…. 'z'->'y'.

Nous devons faire ce qui précède pour chaque préfixe de longueur 1

Exemple Exemple

Entrez

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’

Sortie

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

Instructions

• Dans un préfixe de longueur 1, le plus grand caractère est « p », qui correspond à -1. Par conséquent, la chaîne mise à jour sera « orogress ».

• Dans un préfixe de longueur 2, le caractère maximum est « r » et le mappage est -1. Par conséquent, la chaîne mise à jour sera « nqogress ».

• Dans un préfixe de longueur 3, le plus grand caractère est « q » et la valeur de mappage est 1. Par conséquent, la chaîne mise à jour est « orpgress ».

• Quand nous aurons fini avec tout, la chaîne finale sera 'pqmfpdqr' qui contient 1 'f', 2 'p', 2 'q', 1 'm', 1 'd' et 1 'd' 'r '. Dans la sortie, nous imprimons la fréquence de chaque caractère dans la chaîne résultante.

Entrez

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", 

Sortie

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

Explication− Après avoir effectué toutes les opérations, la chaîne finale est 'ac' et nous avons imprimé la fréquence de chaque caractère.

Méthode 1

Dans cette méthode, nous allons parcourir la chaîne et prendre la valeur de K égale à l'indice P. Après cela, nous prendrons le préfixe de longueur égale à P, trouverons le caractère le plus grand, prendrons la valeur mappée et mettrons à jour tous les caractères du préfixe en conséquence.

Algorithme

Étape 1 − Définissez la variable 'max_char' pour stocker le caractère maximum pour le préfixe donné.

Étape 2 − De même, initialisez une liste de longueur 26 avec des zéros afin de stocker la fréquence de chaque caractère dans la chaîne finale.

Étape 3- Commencez à parcourir la chaîne et initialisez la variable "max_char" avec 96 à l'intérieur de la boucle.

Étape 4- Trouvez le caractère maximum d'un préfixe de longueur p à l'aide de boucles imbriquées.

Étape 5 - Mettez à jour chaque caractère du préfixe en ajoutant la valeur mappée de max_char.

Étape 7- Si le caractère mis à jour est inférieur à "a", mettez-le à jour en "z".

Étape 8- Si le caractère mis à jour est plus grand que "z", mettez-le à jour en "a".

Étape 9− Enfin, stockez la fréquence de chaque caractère dans une liste en parcourant la chaîne mise à jour.

Étape 10- Imprimez la fréquence des caractères.

Exemple

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

Sortie

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

Complexité temporelle− O(N*N) car nous utilisons deux boucles imbriquées pour parcourir la chaîne.

Complexité spatiale− O(1) car nous utilisons un espace constant pour stocker la fréquence des caractères.

Conclusion

Nous avons effectué l'opération donnée sur la chaîne d'entrée et imprimé la fréquence des caractères de la chaîne mise à jour dans la sortie. Les programmeurs peuvent également utiliser des cartes en C++ pour stocker les fréquences de caractères au lieu d'utiliser des listes. Pour plus de pratique, le programmeur peut essayer d'imprimer la fréquence cumulée de chaque caractère dans la chaîne mise à jour.

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!