|
767. 重构字符串
法1：贪心，每次在\(res\)尾巴放剩余数目最多的字符，但要保证与当前尾巴字符不同，若相同则换次大字符，用堆维护。
using PIC = pair;
class Solution {
public:
string reorganizeString(string s) {
unordered_mapcnt;
for(auto& c : s) cnt[c] ++;
priority_queuepq;
for(auto [k, v] : cnt) pq.push({v, k});
string res = "";
char av,bv,cv = '#';
while(res.size() != s.size()){
auto a = pq.top();
pq.pop();
if(a.second != cv){
a.first -= 1;
res += a.second;
if(a.first) pq.push(a);
}
else {
if(!pq.size()) return "";
auto b = pq.top();
pq.pop();
res += b.second;
b.first -= 1;
if(b.first) pq.push(b);
pq.push(a);
}
cv = res.back();
}
return res;
}
};
法2：构造\(res\)，先放偶数位置再放奇数位置。出现次数最大值\(maxc\)如果大于\(\lceil\frac{n}{2}\rceil\)则一定无解，否则有解。
class Solution {
public:
string reorganizeString(string S) {
unordered_map cnt;
int maxc = 0;
for (auto c: S) {
cnt[c] ++ ;
maxc = max(maxc, cnt[c]);
}
int n = S.size();
if (maxc > (n + 1) / 2) return "";
string res(n, ' ');
int i = 1, j = 0;
for (char c = 'a'; c |