在這個問題中,我們給了一個字串「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
返回第 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中文網其他相關文章!