將字串中的每個字元替換為其頻率恰好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;
}

輸出

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中文網其他相關文章！