C++ 将字符串中的每个字符替换为其出现次数的X倍后的第K个字符

问题描述如下：给定一个字符串’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;
}

输出

时间和空间复杂度

时间复杂度取决于给定的字符串digits，等于x的digits次方和它们的总和。

空间复杂度与时间复杂度完全相同。

高效的方法

这是上述方法的优化版本。我们计算每个字符的范围X次，而不是为每次创建一个字符串。

在这里我们观察到，每次字符增加的幂次与字符值有关。

让我们讨论上述方法的主要步骤如下——

创建kthChar变量来存储x次字符串的第K个字符
创建变量tot来存储X次后每个字符出现的次数
使用for循环遍历字符串，并执行以下步骤

−>获取当前字符的值

−>使用该值和X得到X次后当前字符的范围。我们观察到，每次字符值都以X为幂增加。

如pow(value, X)。

−>将该范围存储在变量‘tot’中，以保持X次后字符串的长度

−>检查kth字符是否落在X次后字符串的当前长度内

如(K <= tot)如果是，则中断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;
}