Remplacez chaque caractère d'une chaîne par le Kème caractère après sa fréquence exactement X fois

Dans ce problème, on nous donne une chaîne "str", un entier K et un entier X. La chaîne « str » contient uniquement des entiers compris entre 1 et 9. Nous devons effectuer X opérations sur cette chaîne. Le fonctionnement est qu'à chaque fois nous devons remplacer le nombre d'occurrences d'un caractère dans la chaîne par un caractère dans la chaîne. La fréquence fait ici référence au nombre ou à la valeur de caractères dans la chaîne. Notre tâche est de renvoyer le k-ème caractère après avoir effectué une opération donnée X fois.

Exemple

Input 1: str = “1231”, K = 5, X = 3

Output 1: 2

Instructions

Nous avons effectué l'opération donnée 3 fois.

1st time, str = 1223331 as 

• Pour le caractère str[0], la fréquence est 1 et la valeur est 1, donc 1 apparaît 1 fois.

• Pour le caractère str[1], la fréquence est 2 et la valeur est 2, donc 2 apparaît 2 fois.

• Les autres personnages sont similaires.

2nd time, str = 122223333333331
3rd time, str = 1222222223333333333333333333333333331

Donc exactement X fois plus tard, le Kème caractère de la chaîne est 2. La réponse est donc 2.

Input 2: str = “1121”,  K = 2, X = 5 

Output 2: 2

Nous avons vu l'exemple ci-dessus avec la chaîne donnée, passons aux méthodes -

Méthode naïve

Dans cette méthode, nous calculons la nouvelle chaîne en effectuant l'opération donnée jusqu'à X fois. Après avoir obtenu la chaîne exactement X fois, nous renvoyons le Kième caractère de la chaîne.

Exemple

Jetons un coup d'œil au code pour mieux comprendre la méthode ci-dessus -

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Kth character of the string after X times
char findKthChar(string str, long long K, int X){
   string s = str; // create another string to store the give string as we need to update the string     
   for (int i = 0; i < X; i++) {
      string temp = ""; // To store the temporary result of each time
      for (int j = 0; j < s.size(); j++) {
         int freq = s[j] - '0'; // getting freq of char s[j]
         
         // adding char value its frequency times to 'temp' result.
         while (freq--) {  
            temp += s[j];
         }
      }
      s = temp; // update the string after.
   } 
   return s[K - 1]; // return Kth character of X times string
} 
int main(){

   // Given Input
   string str = "1231";
   long long K =  5;
   int X = 3;
   
   // Function Call
   char result = findKthChar(str, K, X);
   cout << result << "\n";
   return 0;
}

Sortie

2

Complexité temporelle et spatiale

La complexité temporelle dépend des nombres de chaînes donnés et est égale à la puissance x du nombre et à la somme de chaque nombre.

La complexité spatiale est exactement la même que la complexité temporelle.

Méthode efficace

Il s'agit d'une version optimisée de la méthode ci-dessus. où nous calculons la plage pour chaque charte X fois au lieu de créer une chaîne à chaque fois.

Ici, nous observons qu'à chaque fois le caractère augmente par rapport à la valeur du caractère élevée à la puissance du temps.

Discutons ci-dessous des principales étapes de la méthode ci-dessus -

• Créez la variable kthChar pour stocker le KthChar de x fois la chaîne

• Créez une variable tot pour stocker le nombre d'occurrences de chaque caractère après X fois

• Utilisez une boucle for pour parcourir la chaîne et effectuez les étapes suivantes

->Obtenir la valeur du personnage actuel

->En utilisant cette valeur et X, nous pouvons obtenir la plage du caractère actuel après X fois. Comme on peut l'observer, à chaque fois la valeur de force du personnage augmente de X

comme pow(valeur, X).

−> Stockez la plage dans la variable "tot" pour conserver la longueur de la chaîne après X fois

−> Vérifiez si le Kème caractère après X fois se trouve dans la longueur actuelle de la chaîne

As (K <= tot) si oui, cassez la boucle for et stockez le caractère actuel dans la variable "kthChar"<= tot) if yes 则中断 for 循环并将当前字符存储到变量“kthChar”

• Retour à kthChar

Exemple

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Kth character of the string after X times
char findKthChar(string str, long long K, int X){
   char kthChar; // Variable to store the KthChar of x times string
   int tot = 0; // to store the count of the each character occur after the X times 
   
   // Traverse the string 'str'
   for (int i = 0; i < str.size(); i++) { 
      int value = str[i] - '0'; // Convert char into int to get the value 
      
      // Calculate each characters occuring range
      int charRange = pow(value, X);
      tot += charRange; 
      
      // If K is less than tot than kthChar is str[i]
      if (K <= tot) {
         kthChar = str[i];
         break; // break the for loop
      }
   }
   
   // Return answer, kthChar of the string after X times
   return kthChar;
}
int main(){
   string str = "1231"; // given string
   long long K =  5; // given integer
   int X = 3; // given integer
   
   // Function Call to get the kth character after X times
   char result = findKthChar(str, K, X); 
   
   // Print the result
   cout << result << "\n";
   return 0;
}

Sortie

2

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est la taille de la longueur donnée.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme pour trouver le Kième caractère dans une chaîne après avoir remplacé chaque caractère par sa fréquence exactement X fois. Nous avons mis en œuvre deux méthodes, l’une est la méthode naïve et l’autre la méthode efficace.

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!