对长度为 1 到 N 的每个前缀执行所述操作后,每个小写字符的计数


在这个问题中,我们需要对每个字符串前缀执行给定的操作。最后,我们需要计算每个字符的频率。

我们可以遵循贪婪算法来解决这个问题。我们需要获取长度为 K 的每个前缀,并根据给定的条件更新其字符。我们可以使用映射来计算最终字符串中字符的频率。

问题陈述 - 我们得到了包含 N 个小写字母字符的字符串 tr。我们还得到了映射列表,其中包含总共 26 个元素。每个元素根据其值映射到小写字符。例如,mapping[0] 映射到 'a',mapping[1] 映射到 'b',mapping[25] 映射到 'z'。此外,mapping 数组包含 1 或 -1。

我们需要执行以下操作。

  • 获取长度为 K 的前缀中的最大字符,并从 'mapping' 数组中获取映射值。

  • 如果映射值为 1,则将所有前缀元素增加 1。

  • 如果映射值为 -1,则将所有前缀元素减少 1。

这里,增加元素意味着 'a' -> 'b','b' -> 'c',… 'z' -> 'a'。

减少元素意味着 'a' -> 'z','b' -> 'a',… 'z' -> 'y'。

我们需要对长度为 1 <= K <= N 的每个前缀执行上述操作。我们需要在执行上述操作后打印每个字符的频率。

示例

输入

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 个 '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',我们打印了每个字符的频率。

方法 1

在这种方法中,我们将遍历字符串并将 K 的值设置为等于索引 P。之后,我们将获取长度等于 P 的前缀,找到最大字符,获取映射值,并相应地更新所有前缀字符。

算法

步骤 1 - 定义 'max_char' 变量来存储给定前缀的最大字符。

步骤 2 - 还初始化长度为 26 的列表,其值为零,用于存储最终字符串中每个字符的频率。

步骤 3 - 开始遍历字符串,并在循环内将 'max_char' 变量初始化为 96。

步骤 4 - 使用嵌套循环从长度为 p 的前缀中找到最大字符。

步骤 5 - 通过添加 max_char 的映射值来更新前缀的每个字符。

步骤 7 - 如果更新后的字符小于 'a',则将其更新为 'z'。

步骤 8 - 如果更新后的字符大于 'z',则将其更新为 'a'。

步骤 9 - 最后,通过遍历更新后的字符串,将每个字符的频率存储在列表中。

步骤 10 - 打印字符的频率。

示例

Open Compiler
#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++ 中的映射来存储字符频率,而不是使用列表。为了更多练习,程序员可以尝试打印更新字符串中每个字符的累积频率。

更新于:2023年8月14日

54 次查看

开启您的 职业生涯

完成课程获得认证

开始
广告