執行描述的操作後，每個長度為1到N的前綴中的每個小寫字元的計數

在這個問題中，我們需要對每個字串前綴執行給定的操作。最後，我們需要統計每個字元的頻率。

我們可以採用貪心演算法來解決這個問題。我們需要取長度為K的每個前綴，並根據給定的條件更新其字元。我們可以使用map來計算最終字串中字元的頻率。

問題陳述 - 我們給出了包含 N 個小寫字母字元的字串 tr。另外，我們也給出了映射列表，總共包含 26 個元素。每個元素根據其值映射到小寫字元。例如，mapping[0] 映射到“a”，mapping[1] 映射到“b”，mapping[25] 映射到“z”。此外，映射數組包含 1 或 -1。

我們需要執行以下操作。

• 從長度為K的前綴中取得最大字符，並從'mapping'數組中取得映射值。

• 如果映射值為1，則將所有前綴元素增加1。

• 如果映射的值為-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中文網其他相關文章！