C++ 通过删除频率不等于2的幂次方的字符来排序字符串

按照删除频率不是2的幂次方的字符并按词典顺序递增排序，修改字符串是计算机编程领域中一个常见的问题，特别是在竞技编程的背景下。该问题涉及将一个字符串作为输入，通过删除频率不是2的幂次方的字符来修改它，然后按照词典顺序递增对剩余字符进行排序。

在本教程中，我们将使用C++编程语言为这个问题提供一个详细的解决方案。我们将首先更详细地讨论问题陈述，探索解决问题所涉及的各种复杂性，然后提供一步一步的指南，介绍如何使用C++实现一个解决方案。我们还将包括代码片段和示例来帮助说明涵盖的概念。那么，让我们开始吧！

问题陈述

给定一个由N个字符串组成的数组’arr[]’，任务是在修改每个字符串之后，按升序对数组进行排序，其中修改是通过删除非2的幂次方字符并按递减次序对修改后的字符串进行排序。

示例

示例1

例如，输入数组’arr[] = {“aaacbb”, “bleek”, “aaa”}’的修改如下：

• 字符串”aaacbb”中的’a’的频率不是2的幂次方。因此，从字符串中删除’a’，结果为”cbb”。修改后的字符串”cbb”按频率递增的顺序进行排序，与原始字符串相同。因此，”cbb”保持不变。

• 字符串”bleek”的所有字符的频率都是2的幂次方。因此，不删除任何字符，并按频率递增的顺序对字符串进行排序，结果为”lkeeb”。

• 字符串”aaa”中的’a’的频率不是2的幂次方。因此，从字符串中删除’a’，结果为空字符串””。

最后，将修改和排序后的字符串连接起来，结果为 “cbb lkeeb” 。

请注意，程序假设输入字符串仅包含小写英文字母。

示例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是数组中最长字符串的长度。