在這個問題中，我們給了一個字串「str」、整數 K 和整數 X。該字串「str」僅包含 1 到 9 之間的整數。我們必須對該字串執行 X 次操作。操作就是每次我們都要用字串中的一個字元替換它出現的次數。這裡的頻率是指字串中字元的個數或值。我們的任務是在執行給定操作 X 次後返回第 k 個字元。
Input 1: str = “1231”, K = 5, X = 3
Output 1: 2
我們已經執行了 3 次給定的操作。
1st time, str = 1223331 as
對於字元str[0]，頻率為1，值為1，因此1出現1次。
對於字元str[1]，頻率是2，值是2，所以2出現了2次。
其他角色也類似。
2nd time, str = 122223333333331 3rd time, str = 1222222223333333333333333333333333331
所以剛好 X 次之後字串的第 K 個字元是 2。所以答案是 2。
Input 2: str = “1121”, K = 2, X = 5
Output 2: 2
我們已經看到了上面給定字串的範例，讓我們轉向方法 -
在這種方法中，我們透過執行給定的操作來計算新字串直到 X 次。在獲得恰好 X 次的字串後，我們傳回該字串的第 K 個字元。
讓我們看一下程式碼，以便更好地理解上述方法 -
#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
時間與空間複雜度
#時間複雜度取決於給定的字串數字，並且等於數字的 x 次方以及每個數字的總和。
空間複雜度與時間複雜度完全相同。
它是上述方法的最佳化版本。其中我們計算 X 次每個包機的範圍，而不是每次都建立一個字串。
在這裡我們觀察到，每次角色相對於角色值都會增加時間的冪次方。
讓我們在下面討論上述方法的主要步驟 -
建立 kthChar 變數來儲存 x 次字串的 KthChar
建立變數tot來儲存X次後每個字元出現的計數
使用for迴圈遍歷字串並執行下列步驟
#->取得目前字元的值
->使用該值和 X，我們可以得到 X 次後目前字元的範圍。正如我們所觀察到的，每次角色的力量值都會增加 X
作為 pow(value, X)。
−> 將此範圍儲存在變數「tot」中，以維持 X 次後字串的長度
−> 檢查 X 次後第 K 個字元是否位於字串的目前長度內
As (K <= tot) if yes 則中斷 for 迴圈並將目前字元儲存到變數「kthChar」<= tot) if yes 则中断 for 循环并将当前字符存储到变量“kthChar”
返回第 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
時間與空間複雜度
#上述程式碼的時間複雜度為O(N)，其中N是給定長度的大小。
上述程式碼的空間複雜度為 O(1)，因為我們沒有使用任何額外的空間。
在本教程中，我們實作了一個程序，用於在將 String 中的每個字元替換為其頻率恰好 X 次後找到第 K 個字元。我們實現了兩種方法，一種是樸素方法，另一種是有效方法。
以上是將字串中的每個字元替換為其頻率恰好X次後的第K個字符的詳細內容。更多資訊請關注PHP中文網其他相關文章！
