数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究移除频率不是2的幂的字符后，通过排序字符修改字符串
移除频率不是2的幂的字符后，通过排序字符修改字符串是计算机编程领域，尤其是在竞赛编程中一个常见的问题。这个问题涉及到接收一个字符串作为输入，并通过移除频率不是2的幂的字符，然后按字典序递增顺序排序剩余字符来修改它。
在本教程中，我们将使用C++编程语言提供此问题的详细解决方案。我们将首先更详细地讨论问题陈述，探讨解决问题中涉及的各种复杂之处，然后提供一个关于如何使用C++实现解决方案的分步指南。我们还将包含代码片段和示例来帮助说明所涵盖的概念。让我们开始吧！
问题陈述
给定一个包含N个字符串的数组'arr[]'，任务是在修改每个字符串后按升序排序数组，方法是移除所有频率不是2的幂的字符，然后按降序排序修改后的字符串。
示例
示例1
例如，输入数组'arr[] = {“aaacbb”, “bleek”, “aaa”}'修改如下：
字符串"aaacbb"中'a'的频率不是2的幂。因此，'a'将从字符串中移除，结果为"cbb"。修改后的字符串"cbb"按频率递增顺序排序，这与原始字符串相同。因此，"cbb"保持不变。
字符串"bleek"中所有字符的频率都是2的幂。因此，没有字符被移除，并且字符串按频率递增顺序排序，结果为"beekl"。
字符串"aaa"中'a'的频率不是2的幂。因此，'a'从字符串中移除，结果为空字符串""。
最后，修改并排序后的字符串连接在一起，得到输出"cbb beekl "。
请注意，程序假设输入字符串仅包含小写英文字母。
示例2
例如，如果输入数组是'S[] = {“c”, “a”, “b”}'，程序将按字母顺序对其进行排序，得到输出数组'S[] = {“a”, “b”, “c”}'。
算法
可以使用哈希表来存储每个字符串中字符的频率，然后执行指定的运算来解决给定的问题。请按照以下步骤解决问题：
遍历输入字符串数组arr[]，并对每个字符串执行以下操作：
在一个Map中存储每个字符的频率。
创建一个空字符串T来存储修改后的字符串。
遍历Map，并将频率为2的幂的字符添加到字符串T中。
按频率升序排列字符串T，并将其添加到字符串数组res[]中。
按升序排列数组res[]。
完成上述步骤后，打印数组res[]中的字符串作为结果。
现在，让我们借助示例了解使用C++实现上述算法的过程。让我们开始吧！
示例
使用C++实现上述算法
程序首先在一个哈希表中存储输入数组每个字符串的每个字符的频率。然后，它通过只保留频率为2的幂的字符来修改每个字符串，并按降序排列修改后的字符串。最后，它按升序排列修改后的字符串并打印结果。
程序的时间复杂度为O(NMlog(M))，其中N是输入数组的大小，M是输入数组中最长字符串的长度。这是因为，对于每个字符串，我们遍历它一次来计算每个字符的频率，然后再次遍历它来修改字符串。排序操作的时间复杂度为O(Mlog(M))，我们对每个字符串都这样做。此外，我们还在最后对修改后的字符串进行排序，这需要O(NM*log(M))的时间复杂度。
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;
bool isPowerOfTwo(int n) {
if (n == 0) {
return false;
}
return (ceil(log2(n)) == floor(log2(n)));
}
void printArray(vector<string> res) {
sort(res.begin(), res.end());
cout << "Modified array= {";
for (int i = 0; i < res.size(); i++) {
cout << "\"" << res[i] << "\"";
if (i != res.size() - 1) {
cout << ", ";
}
}
cout << "}" << endl;
}
void sortedStrings(string S[], int N) {
unordered_map<char, int> freq;
vector<string> res;
for (int i = 0; i < N; i++) {
string st = "";
for (int j = 0; j < S[i].size(); j++) {
freq[S[i][j]]++;
}
for (auto i : freq) {
if (isPowerOfTwo(i.second)) {
for (int j = 0; j < i.second; j++) {
st += i.first;
}
}
}
freq.clear();
if (st.size() == 0) {
continue;
}
sort(st.begin(), st.end(), greater<char>());
res.push_back(st);
}
printArray(res);
}
int main() {
string arr[] = { "aaacbb", "bleek", "aaa" };
int N = sizeof(arr) / sizeof(arr[0]);
cout << "Input array= {";
for (int i = 0; i < N; i++) {
cout << "\"" << arr[i] << "\"";
if (i != N - 1) {
cout << ", ";
}
}
cout << "}" << endl;
sortedStrings(arr, N);
return 0;
}
输出
Input array= {"aaacbb", "bleek", "aaa"}
Modified array= {"cbb", "lkeeb"}
结论
总而言之，可以使用哈希技术有效地解决基于字符频率修改和排序字符串数组的问题。解决方案的时间复杂度为O(NM log M)，其中N是字符串的数量，M是数组中最长字符串的长度。
45 次浏览
