Gantikan setiap aksara dalam rentetan dengan aksara Kth selepas kekerapannya tepat X kali

Dalam masalah ini, kita diberi rentetan "str", integer K dan integer X. Rentetan "str" ​​​​hanya mengandungi integer antara 1 dan 9. Kita perlu melakukan operasi X pada rentetan ini. Operasinya ialah setiap kali kita perlu menggantikan bilangan kemunculan aksara dalam rentetan dengan aksara dalam rentetan. Kekerapan di sini merujuk kepada bilangan atau nilai aksara dalam rentetan. Tugas kami adalah untuk mengembalikan aksara ke-k selepas melakukan operasi yang diberikan X kali.

Contoh

Input 1: str = “1231”, K = 5, X = 3

Output 1: 2

Arahan

Kami telah melakukan operasi yang diberikan sebanyak 3 kali.

1st time, str = 1223331 as 

• Untuk aksara str[0], kekerapan ialah 1 dan nilainya ialah 1, jadi 1 muncul 1 kali.

• Untuk aksara str[1], kekerapan ialah 2 dan nilainya ialah 2, jadi 2 muncul 2 kali.

• Watak lain serupa.

2nd time, str = 122223333333331
3rd time, str = 1222222223333333333333333333333333331

Jadi tepat X kali kemudian aksara Kth rentetan ialah 2. Jadi jawapannya ialah 2.

Input 2: str = “1121”,  K = 2, X = 5 

Output 2: 2

Kita telah melihat contoh rentetan yang diberikan di atas, mari kita beralih kepada kaedah -

Kaedah naif

Dalam kaedah ini kita mengira rentetan baru dengan melakukan operasi yang diberikan sehingga X kali. Selepas mendapat rentetan tepat X kali, kami mengembalikan aksara Kth rentetan itu.

Contoh

Mari kita lihat kod untuk lebih memahami kaedah di atas -

#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;
}

Output

2

Kerumitan masa dan ruang

Kerumitan masa bergantung pada nombor rentetan yang diberikan dan sama dengan kuasa x nombor dan jumlah setiap nombor.

Kerumitan ruang adalah sama seperti kerumitan masa.

Kaedah yang cekap

Ia adalah versi yang dioptimumkan bagi kaedah di atas. di mana kita mengira julat untuk setiap piagam X kali dan bukannya mencipta rentetan setiap kali.

Di sini kita perhatikan bahawa setiap kali watak itu meningkat berbanding dengan nilai watak yang dinaikkan kepada kuasa masa.

Mari kita bincangkan langkah-langkah utama kaedah di atas di bawah -

• Buat pembolehubah kthChar untuk menyimpan KthChar rentetan x kali

• Buat pembolehubah tot untuk menyimpan kiraan kejadian setiap aksara selepas X kali

• Gunakan gelung for untuk melelaran melalui rentetan dan lakukan langkah berikut

->Dapatkan nilai watak semasa

->Menggunakan nilai dan X ini, kita boleh mendapatkan julat aksara semasa selepas X kali. Seperti yang dapat kita perhatikan, setiap kali nilai kekuatan watak meningkat sebanyak X

sebagai pow(nilai, X).

−> Simpan julat dalam pembolehubah "tot" untuk mengekalkan panjang rentetan selepas X kali

−> Semak sama ada aksara Kth selepas X kali berada dalam panjang rentetan semasa

Sebagai (K <= tot) jika ya maka putuskan gelung for dan simpan aksara semasa ke pembolehubah "kthChar"<= tot) if yes 则中断 for 循环并将当前字符存储到变量“kthChar”

• Kembali ke kthChar

Contoh

#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;
}

Output

2

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N), dengan N ialah saiz panjang yang diberikan.

Kerumitan ruang kod di atas ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Kesimpulan

Dalam tutorial ini, kami melaksanakan program untuk mencari aksara Kth dalam String selepas menggantikan setiap aksara dengan kekerapannya tepat X kali. Kami melaksanakan dua kaedah, satu kaedah naif dan satu lagi kaedah berkesan.

Atas ialah kandungan terperinci Gantikan setiap aksara dalam rentetan dengan aksara Kth selepas kekerapannya tepat X kali. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!