数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 字符串重排
假设我们有一个字符串 S，检查其字母是否可以重新排列，使得任何两个相邻的字符都不相同。如果可以，输出任何一个可能的排列结果。如果不可以，则返回空字符串。例如，如果输入是“AAB”，则输出将是“ABA”。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个名为 pq 的整数字符对优先队列，定义一个 map m
- n := 字符串的长度
- 在 map m 中存储字符频率
- 对于 m 中的每个键值对 p
- 插入 (p 的整数部分，p 的字符部分)
- ans := 空字符串
- 当 pq 不为空时
- 设置 one := pq 中的顶部对，并从 pq 中删除顶部对
- 如果 pq 为空，则
- 如果 one 的整数部分 > 1，则返回空字符串
- ans := ans + one 的字符部分
- 返回 ans
- two := pq 中的顶部对，并从 pq 中删除顶部对
- ans := ans + one 的字符部分
- ans := ans + two 的字符部分
- 将 one 和 two 的整数部分加 1
- 如果 one 的整数部分不为 0，则将 one 插入 pq
- 如果 two 的整数部分不为 0，则将 two 插入 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
更新于: 2020年4月30日
511 次浏览
广告