Ersetzen Sie jedes Zeichen in einer Zeichenfolge genau X-mal durch das K-te Zeichen nach seiner Häufigkeit

In diesem Problem erhalten wir eine Zeichenfolge „str“, eine Ganzzahl K und eine Ganzzahl X. Die Zeichenfolge „str“ enthält nur ganze Zahlen zwischen 1 und 9. Wir müssen X-Operationen für diese Zeichenfolge ausführen. Die Operation besteht darin, dass wir jedes Mal die Anzahl der Vorkommen eines Zeichens in der Zeichenfolge durch ein Zeichen in der Zeichenfolge ersetzen müssen. Die Häufigkeit bezieht sich hier auf die Anzahl oder den Wert der Zeichen in der Zeichenfolge. Unsere Aufgabe besteht darin, das k-te Zeichen zurückzugeben, nachdem eine bestimmte Operation X-mal ausgeführt wurde.

Beispiel

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

Output 1: 2

Anleitung

Wir haben den angegebenen Vorgang dreimal durchgeführt.

1st time, str = 1223331 as 

• Für das Zeichen str[0] beträgt die Häufigkeit 1 und der Wert 1, sodass 1 1 Mal erscheint.

• Für das Zeichen str[1] beträgt die Häufigkeit 2 und der Wert 2, sodass 2 zweimal vorkommt.

• Andere Charaktere sind ähnlich.

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

Genau X-mal später ist das K-te Zeichen der Zeichenfolge also 2. Die Antwort ist also 2.

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

Output 2: 2

Wir haben die oben angegebene Beispielzeichenfolge gesehen, gehen wir nun zu den Methoden über -

Naive Methode

Bei dieser Methode berechnen wir die neue Zeichenfolge, indem wir die angegebene Operation X-mal ausführen. Nachdem wir die Zeichenfolge genau X-mal erhalten haben, geben wir das K-te Zeichen der Zeichenfolge zurück.

Beispiel

Werfen wir einen Blick auf den Code, um die obige Methode besser zu verstehen -

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

Ausgabe

2

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität hängt von den angegebenen String-Zahlen ab und ist gleich der x-Potenz der Zahl und der Summe jeder Zahl.

Raumkomplexität ist genau dasselbe wie Zeitkomplexität.

Effiziente Methode

Es handelt sich um eine optimierte Version der oben genannten Methode. Dabei berechnen wir die Reichweite für jede Charter X-mal, anstatt jedes Mal eine Zeichenfolge zu erstellen.

Hier beobachten wir, dass sich der Charakter jedes Mal im Verhältnis zum Charakterwert erhöht, der mit der Zeit hochgerechnet wird.

Lassen Sie uns unten die Hauptschritte der oben genannten Methode besprechen -

• Erstellen Sie die kthChar-Variable, um den KthChar von x mal String zu speichern

• Erstellen Sie die Variable tot, um die Anzahl der Vorkommen jedes Zeichens nach X-Zeiten zu speichern

• Verwenden Sie eine for-Schleife, um die Zeichenfolge zu durchlaufen und führen Sie die folgenden Schritte aus

->Den Wert des aktuellen Zeichens abrufen

->Mit diesem Wert und X können wir den Bereich des aktuellen Zeichens nach X-Zeiten ermitteln. Wie wir beobachten können, erhöht sich der Stärkewert des Charakters jedes Mal um X

als pow(Wert, X).

−> Speichern Sie den Bereich in der Variablen „tot“, um die Länge der Zeichenfolge nach X-Zeiten beizubehalten

−> Prüfen Sie, ob das K-te Zeichen nach X-mal innerhalb der aktuellen Länge der Zeichenfolge liegt

As (K <= tot) Wenn ja, unterbrechen Sie die for-Schleife und speichern Sie das aktuelle Zeichen in der Variablen „kthChar“<= tot) if yes 则中断 for 循环并将当前字符存储到变量“kthChar”

• Zurück zu kthChar

Beispiel

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

Ausgabe

2

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Größe der gegebenen Länge ist.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz verwenden.

Fazit

In diesem Tutorial haben wir ein Programm implementiert, um das K-te Zeichen in einem String zu finden, nachdem jedes Zeichen genau X-mal durch seine Häufigkeit ersetzt wurde. Wir haben zwei Methoden implementiert, eine ist die naive Methode und die andere ist die effektive Methode.

Das obige ist der detaillierte Inhalt vonErsetzen Sie jedes Zeichen in einer Zeichenfolge genau X-mal durch das K-te Zeichen nach seiner Häufigkeit. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!