在这个问题中，我们给出了一个字符串“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中文网其他相关文章！
