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;
}

};

结果