C++ 通过将每个字符向右按其频率循环移位来修改字符串

在这个问题中，我们需要将给定字符串中的每个字符向右移动其频率次数。为了解决这个问题，我们可以计算每个字符的频率并将其存储在类似数组或映射的数据结构中。然后，我们可以使用字符的ASCII值将每个字符按其频率向右移位。

问题陈述 - 我们有一个包含小写字符和长度为N的字符串str。我们需要将字符串的每个字符向右移动它在给定字符串中的频率次数。

示例

输入 - str = ‘tutorialspoint’

输出 - wvwqskbmtqqkow

解释

• ‘t’的频率是3。所以，’t’ + 3 = w。

• ‘u’的频率是1。所以，’u’ + 1 = v。

• ‘o’的频率是2。所以，’o’ + 2 = q。

• ‘r’的频率是1。所以，’r’ + 1 = s。

• ‘i’的频率是2。所以，’i’ + 2 = k。

• ‘a’的频率是1。所以，’a’ + 1 = b。

• ‘l’的频率是1。所以，’l’ + 1 = m。

• ‘s’的频率是1。所以，’s’ + 1 = t。

• ‘p’的频率是1。所以，’p’ + 1 = q。

• ‘n’的频率是1。所以，’n’ + 1 = o。

输入 - str = ‘xxxxyyyzz’

输出 - ‘bbbbbbbbb’

解释

• ‘x’的频率是4。所以，’x’ + 4 = b，因为我们需要进行循环移位。

• ‘y’的频率是3。所以，’y’ + 3 = b。

• ‘z’的频率是4。所以，’z’ + 2 = b。

方法1

在这种方法中，我们将使用映射数据结构来计算和存储给定字符串中每个字符的频率。然后，我们可以遍历字符串并按照每个字符的频率进行循环移位。

步骤

• 定义’mp’映射以存储字符->频率

• 定义’len’变量并使用length()方法存储字符串的长度。

• 使用for循环遍历字符串。在循环中，通过将1添加到当前值来更新字符的频率。

• 现在，再次遍历字符串的每个字符。

• 在循环中，访问当前字符的频率并使用26进行模运算。将结果存储在’freq’变量中。在这里，我们需要对字符进行右移运算，右移字符26位后，我们会得到相同的结果。

• 如果str[i]的ASCII值+freq小于’z’的ASCII值，则通过添加’freq’值更新str[i]字符。

• 否则，将str[i]的ASCII值加上’freq’值，并减去’z’的ASCII值。然后，将结果值添加到str[i]。

• 返回最终字符串。

示例

#include <iostream>
#include <map> 
//#include <set>
using namespace std;
// Function to shift each character of the string by its frequency.
string shiftCharByFrequancy(string str){
   // map to store the frequency of each character
   map<char, int> mp;
   int len = str.length();
   // Iterate over the string
   for (int i = 0; i < len; i++){
      // update the frequency of the current character
       mp[str[i]] += 1;
   }
   // Traverse the string str
   for (int i = 0; i < len; i++){
      // get the frequency of the current character
      int freq = mp[str[i]] % 26;
      // If the ASCII value of str[i] + freq is less than or equal to the ASCII value of 'z', then update the character by adding freq.
      if (str[i] + freq <= 'z'){
         str[i] = char(int(str[i]) + freq);
      } else {
         // else subtract ASCII value of 'z' from str[i] + freq and add it to ASCII value of 'a' - 1 to get the updated character.
         freq = freq - 'z' + str[i];
         str[i] = char(int('a') + freq - 1);
      }
   }
   return str;
}
int main(){
   string str = "tutorialspoint";
   cout << "The resultant string after circularly right shifting each character of string by its frequency is " << shiftCharByFrequancy(str);
   return 0;
}

输出

The resultant string after circularly right shifting each character of string by its frequency is wvwqskbmtqqkow

时间复杂度 – O(N)，因为我们遍历长度为N的字符串。

空间复杂度 – (26) ～ O(1)，因为我们使用map来存储字符的频率。

在本教程中，我们学会了通过它们的频率将每个字符右移。我们使用map来存储频率，用户也可以使用数组或向量来存储频率。此外，可以使用count()方法来计算特定字符的频率。