在C ++中重组字符串
假设我们有一个字符串S，请检查是否可以重新排列字母，以使彼此相邻的两个字符不同。如果可能，输出任何可能的结果。如果不可能，则返回空字符串。因此，如果输入像“AAB”，那么输出将是“ABA”。
为了解决这个问题，我们将遵循以下步骤-
创建一个称为pq的整数字符对的优先级队列，定义一个映射m
n：=字符串的大小
将字符频率存储在映射m中
对于m中的每个键值对p
插入（p的整数部分，p的字符部分）
ans：=空字符串
当pq不为空时
如果整数部分>1，则返回空字符串
ans：=ans+一个字符的一部分
返回ans
设置一个：=pq中的顶级对，并删除pq中的顶级对
如果pq为空，则
两个：=来自pq的顶部对，并删除来自pq的顶部对
ans：=ans+一个字符的一部分
ans：=ans+两个字符的一部分
将一和二的整数部分加1
如果1的整数部分不为0，则将1插入pq
如果2的整数部分不为0，则将1插入pq
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string reorganizeString(string S) {
priority_queue <pair <int, char>> pq;
map <char, int> m;
int n = S.size();
for(int i = 0; i < n; i++){
m[S[i]]++;
}
map <char, int> :: iterator i = m.begin();
while(i != m.end()){
pq.push({i->second, i->first});
i++;
}
string ans = "";
while(!pq.empty()){
pair <int, char> one = pq.top();
pq.pop();
if(pq.empty()){
if(one.first > 1)
return "";
ans += one.second;
return ans;
}
pair <int, char> two = pq.top();
pq.pop();
ans += one.second;
ans += two.second;
//cout << ans << endl;
one.first--;
two.first--;
if(one.first)pq.push(one);
if(two.first)pq.push(two);
}
return ans;
}
};
int main() {
Solution ob1;
cout << ob1.reorganizeString("AAB") << endl;
return 0;
}输入项
S = "AAB"
ob1.reorganizeString("AAB")输出结果
ABA