leetcode0767. 重构字符串-medium

1 题目：重构字符串

官方标定难度：中

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

返回 s 的任意可能的重新排列。若不可行，返回空字符串 “” 。

示例 1:

输入: s = “aab”
输出: “aba”
示例 2:

输入: s = “aaab”
输出: “”

提示:

1 <= s.length <= 500
s 只包含小写字母

2 solution

贪心算法，将数量的大优先排

代码

class Solution {
public:
string reorganizeString(string s) {vector<int> count(26);for (char c: s) count[c - 'a']++;auto f = [&](int a, int b) { return count[a] < count[b]; };priority_queue<int, vector<int>, decltype(f)> q(f);for(int i = 0; i < 26; i++){if(count[i]) q.push(i);}string res;int last = -1;while (!q.empty()) {if (q.size() == 1) {int cnt = count[q.top()];if (cnt > 1) return "";if (q.top() == last) return "";else {res.push_back(q.top() + 'a');return res;}}int x = q.top();q.pop();if (x != last) {count[x]--;res.push_back(x + 'a');last = x;if(count[x])q.push(x);}else{int y = q.top();q.pop();res.push_back(y + 'a');last = y;count[y]--;if(count[y])q.push(y);if(count[x])q.push(x);}//cout << res << endl;}return res;
}};

结果