数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究对字符串数组进行排序，先移除频率不是2的幂的字符，再对每个字符串排序
在这个问题中，我们需要移除字符串中频率不是2的幂的字符。之后，我们需要按照非递减顺序对数组中的每个字符串进行排序。
问题陈述 - 我们给定一个包含 N 个不同长度字符串的数组 arr[]。如果字符的频率不是2的幂，则需要移除字符串中的字符。之后，需要对每个字符串进行排序。
示例
输入 – arr[] = {"abde", "cpcc", "ddddd", "kk"}
输出 – edba, p, kk
解释
在字符串“abde”中，所有字符的频率都是1，等于 2^0。
在字符串“cpcc”中，“c”的频率是3，它不等于任何2的幂。所以，我们移除了它。
在字符串“ddddd”中，“d”的频率是5。所以，所有字符都被从字符串中移除。
在字符串“kk”中，“k”的频率是2，等于 2^1。
最后，我们按照递减顺序对所有字符串进行排序，并显示非空字符串。
输入 – arr[] = {"yz ", "nm", "", ""}
输出 – zy, mn
解释 – 它在输出中移除空字符串。
方法 1
在这个方法中，首先，我们将计算给定字符串中每个字符的频率。之后，我们将检查频率是否为2的幂。如果是，我们将保留字符串中的字符。否则，我们将从字符串中移除它。
用户可以按照以下算法解决问题。
算法
定义 isPowerOfTwo() 函数来检查数字是否为2的幂。
在函数中，如果“num”等于零，则返回 false。
取以2为底的对数。
如果 num 是 2 的幂，则取对数时得到整数值。因此，使用 ceil() 和 floor() 方法来检查对数值是否为整数，并根据此返回布尔值。
定义 sortedString() 函数来对修改后的字符串进行排序。
定义“freq”映射来存储特定字符串的字符频率。此外，定义“ans”向量来存储结果字符串。
使用循环遍历字符串数组。在循环中，定义“temp”字符串变量并将其初始化为空字符串。
现在，使用循环遍历从第 i 个索引开始的字符串，并将字符的频率存储在“freq”映射中。
使用 clear() 方法清除映射，因为我们需要存储另一个字符串的字符频率。
如果“temp”字符串的大小为零，则继续迭代。
使用 sort() 方法对字符串进行排序，并将其附加到“ans”向量。
遍历“ans”向量以获取所有结果字符串。
2的幂。如果是，则将字符频率次添加到 temp 字符串中。
示例
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
using namespace std;
// Check whether Num is power of 2
bool isPowerOfTwo(int num){
// Base Case
if (num == 0)
return false;
// If num is a power of 2, then log2(num) will be an integer value.
return (ceil(log2(num)) == floor(log2(num)));
}
// function to modify the array of strings according to the given condition.
void sortedStrings(string str[], int N){
// map to store the frequency of each alphabet of the string.
unordered_map<char, int> freq;
// storing answer in a vector of strings.
vector<string> ans;
// iterate over the array of strings
for (int i = 0; i < N; i++){
// Temporary string
string temp = "";
// Stores frequency of each
// alphabet of the string
for (int j = 0; j < str[i].size(); j++){
// Update frequency of str[i][j]
freq[str[i][j]]++;
}
// Iterate over the map
for (auto i : freq){
// If the frequency of any alphabet is a power of 2, then append it to temp.
if (isPowerOfTwo(i.second)){
// append i.first character i.second times to temp.
for (int j = 0; j < i.second; j++){
temp += i.first;
}
}
}
// Clear the map
freq.clear();
// empty string
if (temp.size() == 0)
continue;
// sort the string in non-increasing order
sort(temp.begin(), temp.end(), greater<char>());
// push temp string to ans
ans.push_back(temp);
}
// Print the array of strings
cout << "The array of strings after modification is: ";
for (int i = 0; i < ans.size(); i++){
cout << ans[i] << " ";
}
}
int main(){
string arr[] = {"abde", "cpcc", "ddddd", "kk"};
int N = sizeof(arr) / sizeof(arr[0]);
sortedStrings(arr, N);
return 0;
}
输出
The array of strings after modification is: edba p kk
时间复杂度 – O(N*M)，其中 N 是数组的长度，M 是字符串的最大长度。
空间复杂度 – O(N)，用于在映射中存储字符频率。
我们学习了如何从字符串中移除所有频率不等于2的幂的字符，并按照递减顺序对字符串进行排序。程序员可以尝试按照字符的频率顺序对字符串的字符进行排序。
93 次查看
