資料結構
網路
關係資料庫管理系統(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 次瀏覽
