深远互动 网站建设/服务网站排名咨询

767. 重构字符串

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

思路

• 其实就是一个贪心的思想，统计每个字符出现的次数，如果最多的出现次数大于字符串长度的一半，则无法完成任务，否则就可以错位安排最大次数的字符，直到所有字符安排完毕。
• 数据结构：优先队列，方便找到出现次数最大的字符。

代码

class Solution {
public:struct cmp {bool operator() (const pair<int, int>& a, const pair<int, int>& b) {return a.first < b.first;}};string reorganizeString(string S) {priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;vector<int> count(26, 0);int maxCount = 0;int n = S.size();for(int i = 0; i < n; i++) {count[S[i] - 'a']++;maxCount = max(maxCount, count[S[i] - 'a']);}if(maxCount > (n + 1) / 2) {return "";}for(int i = 0; i < 26; i++) {if(count[i]) {pq.push(make_pair(count[i], i));}}string ans(n, ' ');int pos = 0;while(!pq.empty()) {pair<int, int> tmp = pq.top();pq.pop();char c = tmp.second + 'a';int num = tmp.first;while(num != 0) {ans[pos] = c;pos += 2;num--;if(pos >= n) {pos = 1;}}}return ans;}
};