Rechercher la valeur après avoir supprimé N caractères de la chaîne « S » dans N opérations sous les contraintes données

Quelles sont les spécifications d'utilisation des chaînes ?

Résolvez un défi spécifique impliquant la chaîne S donnée. La chaîne S ne contient que des lettres anglaises minuscules et certaines contraintes doivent être respectées lors de la suppression de caractères.

La contrainte donnée est -

• Il y a des lettres anglaises minuscules dans la chaîne S

• Seuls les caractères apparaissant plusieurs fois dans la chaîne peuvent être supprimés.

• Seuls les caractères consécutifs peuvent être supprimés. Les étapes suivantes peuvent être utilisées pour supprimer des caractères d'une chaîne S -

• Trouvez tous les caractères qui apparaissent plusieurs fois lors d'une itération sur la chaîne S. Recherchez toutes les occurrences consécutives du caractère en itérant à nouveau la chaîne S pour chaque caractère.

• Si le nombre d'occurrences consécutives de caractères est supérieur ou égal au nombre d'itérations, supprimez les N premières occurrences de caractères.

• Continuez les étapes 2 et 3 jusqu'à ce que toutes les itérations soient terminées.

Enfin, en renvoyant la chaîne finale S, vous pouvez trouver la valeur de la chaîne après avoir supprimé N caractères après N opérations.

Grammaire

Ce sujet est une question de codage qui consiste à manipuler une chaîne donnée en effectuant un certain nombre d'opérations dessus. À chaque opération, les caractères les plus courants de la chaîne sont supprimés et la fréquence de chaque caractère restant est mise à jour. Après avoir effectué cette opération N fois, la valeur finale de la chaîne est calculée en mettant au carré la fréquence de chaque caractère restant et en les additionnant. Le but de ce problème est d'écrire un programme qui prend une chaîne et un nombre N en entrée et génère la valeur finale de la chaîne après avoir effectué N opérations selon les contraintes données.

Voici la syntaxe d'une fonction qui trouve la valeur après N opérations pour supprimer N caractères de la chaîne S sous les contraintes données -

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

Cette fonction accepte deux paramètres -

• n - un entier représentant le nombre d'opérations à effectuer.

• s - une chaîne représentant la chaîne d'entrée.

La fonction calcule d'abord la fréquence de chaque caractère de la chaîne d'entrée à l'aide d'un tableau. Ce tableau de fréquences est ensuite trié par ordre décroissant et effectué N fois, où à chaque opération la fréquence des caractères les plus courants est réduite et le tableau de fréquences est à nouveau trié.

Enfin, la fonction calcule la valeur de la chaîne en additionnant la fréquence au carré de chaque caractère dans le tableau de fréquences trié et la renvoie sous forme d'entier.

Algorithme

Après N processus de suppression de caractères, l'algorithme calcule la valeur de la chaîne sous les contraintes suivantes. L'entrée se compose d'un nombre N et d'une chaîne S.

• Étape 1 - Utilisez un tableau pour déterminer la fréquence de chaque caractère dans la chaîne d'entrée.

• Étape 2 - Triez ce tableau de fréquences par ordre décroissant.

• Étape 3 - Effectuez N opérations, chaque opération diminuant la fréquence du caractère le plus fréquent dans le tableau de fréquences.

• Étape 4 - Réorganisez le tableau des fréquences.

• Étape 5 - Ajoutez la fréquence au carré de chaque caractère dans le tableau de fréquences trié pour déterminer la valeur de la chaîne.

• Étape 6 - Après N opérations, la valeur de la chaîne est la somme de ses carrés.

Cette technique fonctionne car le problème nécessite de supprimer N caractères d'une chaîne d'entrée S, ce qui revient à effectuer N opérations où chaque opération supprime une fois le caractère le plus courant de la chaîne. En raison des contraintes de la tâche, nous ne pouvons pas réellement supprimer des caractères de la chaîne, nous devons donc simuler cette opération en réduisant la fréquence des caractères les plus courants dans le tableau de fréquences à chaque opération.

Méthode à suivre

Méthode 1

Utilisez le code pour initialiser l'exemple de chaîne S et diverses opérations N. Après chaque opération dans la boucle, le caractère initial supérieur au caractère suivant est supprimé. S'il n'est pas supprimé, le dernier caractère sera supprimé. Une fois toutes les opérations terminées, il imprime la valeur finale de la chaîne.

Ici, le code suppose que N est inférieur ou égal à la longueur de la chaîne S. Si N est plus long que S, le code ne s'exécutera pas comme prévu.

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

Sortie

a b c d

Méthode 2

Dans ce code, un tableau est d'abord utilisé pour déterminer la fréquence de chaque caractère dans la chaîne d'entrée. Ensuite, nous effectuons N opérations, en diminuant la fréquence des caractères les plus courants dans chaque opération, et trions à nouveau le tableau de fréquences. Ensuite, nous trions ce tableau de fréquences par ordre décroissant.

La valeur de la chaîne est finalement déterminée en ajoutant la fréquence au carré de chaque caractère dans le tableau de fréquences trié.

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

Sortie

Value of string after 3 operations: 3

Conclusion

Pour résumer, nous pouvons éliminer N caractères de la chaîne "S" sous les contraintes ci-dessus en utilisant des techniques directes pour obtenir la valeur après N opérations. Tout d’abord, initialisons le tableau de fréquences pour suivre le nombre de caractères contenus dans la chaîne. Une fois que nous avons éliminé N caractères, nous pouvons répéter le processus de suppression du caractère avec le plus grand nombre de la matrice de fréquences. Ce processus peut être répété N fois au total.

Avec cette méthode, nous pouvons déterminer rapidement la valeur de la chaîne "S" après N opérations (y compris l'élimination de N caractères). En raison de la présence de l’étape de tri dans cette méthode, la complexité temporelle de cette solution est O(N logN), ce qui est acceptable pour la plupart des applications pratiques.

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!