Rumah > Artikel > pembangunan bahagian belakang > 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.
Input 1: str = “1231”, K = 5, X = 3
Output 1: 2
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 -
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.
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; }
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.
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
Kembali ke 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
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.
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!