Heim > Artikel > Backend-Entwicklung > 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.
Input 1: str = “1231”, K = 5, X = 3
Output 1: 2
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 -
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.
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; }
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.
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
Zurück zu kthChar
#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; }
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.
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!