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