给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
示例 1:
输入: S = "aab"
输出: "aba"
示例 2:
输入: S = "aaab"
输出: ""
分析：首先统计S中各个字符出现的次数，比如说实例1中，a:2，b:1，然后放到最大堆里，每次从中拿出出现次数最多的两个字符，输出字符。接着把字符出现次数减1，如果字符出现的次数仍然大于0,那么放回最大堆里去。重新选择出现次数最多的两个字符。最后，最大堆里面要么剩下一个元素，要么不剩元素，如果剩下的那个字符出现的次数大于1,那么题目中的要求达不到，如果字符出现次数为1,就要输出。
#include <map> #include <string> #include <queue> #include <iostream> #include <vector> using namespace std; // 自定义优先级队列排序规则 class mycomparison { bool reverse; public: mycomparison(const bool& revparam=false) {reverse=revparam;} bool operator() (pair<char, int>& lhs, pair<char,int>&rhs) const { if (reverse) return (lhs.second > rhs.second); else return (lhs.second < rhs.second); } }; class Solution { public: string reorganizeString(string S) { map<char, int> my_map; pair<char, int> temp1, temp2; string s = ""; // 查找字符串次数 int length = S.size(); for(int i = 0; i < length; i++) { my_map[S[i]]++; } // 放入最大堆 priority_queue<pair<char, int>,vector<pair<char,int>> ,mycomparison> max_heap; map<char, int>::iterator begin = my_map.begin(); for(begin; begin != my_map.end(); begin++) { max_heap.push(*(begin)); } // 弹出两个元素 while(max_heap.size() > 1) { temp1 = max_heap.top(); max_heap.pop(); temp2 = max_heap.top(); max_heap.pop(); s = s + temp1.first + temp2.first; if(temp1.second >= 2) { //减1放回去 temp1.second -= 1; max_heap.push(temp1); } if(temp2.second >= 2) { //减1放回去,重新调整顺序，优先级队列，好爽^-^ temp2.second -= 1; max_heap.push(temp2); } } if (max_heap.size() == 1) { if (max_heap.top().second == 1) { s = s + max_heap.top().first; } else { s = ""; } } return s; } };
原文：https://www.cnblogs.com/jielearscoding/p/13174658.html