在這個問題中，我們需要對每個字串前綴執行給定的操作。最後，我們需要統計每個字元的頻率。
我們可以採用貪心演算法來解決這個問題。我們需要取長度為K的每個前綴，並根據給定的條件更新其字元。我們可以使用map來計算最終字串中字元的頻率。
問題陳述 - 我們給出了包含 N 個小寫字母字元的字串 tr。另外，我們也給出了映射列表，總共包含 26 個元素。每個元素根據其值映射到小寫字元。例如，mapping[0] 映射到“a”，mapping[1] 映射到“b”，mapping[25] 映射到“z”。此外，映射數組包含 1 或 -1。
我們需要執行以下操作。
在這裡，增加元素意味著 ‘a’ −> ‘b’，‘b’ −> ‘c’，… ‘z’ −> ‘a’。
遞減的元素意味著，‘a’->‘z’，‘b’->‘a’，…。 ‘z’->‘y’。
我們需要對每個長度為1的前綴執行上述操作
範例範例
輸入
mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = ‘progress’
登入後複製
輸出
0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0
登入後複製
說明
在長度為1的前綴中，最大的字元是 'p'，映射為 -1。因此，更新後的字串將是 'orogress'。
長度為2的前綴中，最大字元為‘r’，對應為-1。因此，更新後的字串將是“nqogress”。
在長度為3的前綴中，最大的字元是‘q’，映射值為1。因此，更新後的字串為‘orpgress’。
當我們完成所有操作後，最終的字串將是'pqmfpdqr'，其中包含1個'f'，2個'p'，2個'q'，1個'm'，1個'd'和1個'd' 'r'。在輸出中，我們列印了結果字串中每個字元的頻率。
輸入
mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = "ab",
登入後複製
輸出
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
登入後複製
解釋− 在執行所有操作之後，最終的字串是'ac'，我們列印了每個字元的頻率。
方法一
在這個方法中，我們將遍歷字串並取K的值等於索引P。之後，我們將取長度等於P的前綴，找到最大字符，取映射值，並相應地更新所有前綴字符。
演算法
步驟 1 − 定義‘max_char’變數來儲存給定前綴的最大字元。
步驟2 − 同樣地，用零初始化長度為26的列表，以便儲存最終字串中每個字元的頻率。
第 3 步- 開始遍歷字串，並在迴圈內以 96 初始化「max_char」變數。
第 4 步- 使用巢狀循環從長度為 p 的前綴中尋找最大字元。
步驟 5 - 透過新增 max_char 的映射值來更新前綴的每個字元。
第 7 步- 如果更新的字元小於“a”，則將其更新為“z”。
第 8 步- 如果更新的字元大於“z”，則將其更新為“a”。
第9步− 最後，透過遍歷更新後的字串，將每個字元的頻率儲存在清單中。
第 10 步- 列印字元的頻率。
範例
#include <bits/stdc++.h>
using namespace std;
void performOperations(string &str, vector<int> &mapping) {
int len = str.length();
char max_char;
// array to store the final frequency of each character
int freq[26] = {0};
for (int p = 0; p < len; p++) {
max_char = 96;
// Get the maximum character from the prefix string
for (int q = 0; q <= p; q++) {
max_char = max(max_char, str[q]);
}
// Update the prefix string by adding the max character's value.
for (int q = 0; q <= p; q++) {
// adding the mapping value to the current character
str[q] += mapping[max_char - 'a'];
// If the updated value is greater than z or less than a, update it
if (str[q] < 'a') {
str[q] = 'z';
} else if (str[q] > 'z') {
str[q] = 'a';
}
}
}
// Counting frequency of each character
for (int p = 0; p < len; p++) {
freq[str[p] - 'a']++;
}
// print count of each character in the updated string
for (auto ch : freq) {
cout << ch << ' ';
}
}
int main() {
string S = "progress";
vector<int> mapping = {-1, 1, 1, -1, 1, 1, -1, -1,
-1, 1, 1, 1, -1, 1, -1, 1, -1,
1, -1, 1, 1, 1, -1, 1, 1, 1};
performOperations(S, mapping);
return 0;
}
登入後複製
輸出
0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0
登入後複製
時間複雜度− O(N*N)因為我們使用兩個巢狀循環來遍歷字串。
空間複雜度− O(1)，因為我們使用恆定空間來儲存字元的頻率。
結論
我們對輸入字串執行了給定的操作，並在輸出中列印了更新後字串的字元頻率。程式設計師也可以使用C 中的map來儲存字元頻率，而不是使用清單。對於更多練習，程式設計師可以嘗試列印更新後字串中每個字元的累積頻率。
以上是執行描述的操作後，每個長度為1到N的前綴中的每個小寫字元的計數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
