题目描述
解题思路
贪心策略，用一个大顶堆维护3个字符的数量和对应字符 每次选取剩余数量最多的字符，加入一次后就入堆
问：为什么每次都只加入一个字符，不能连续加入多个吗？
因为加入一次字符后，不一定就是三个字符中剩余数量最多的了 比如a = 8, b = 8, c = 7,取出字符a加入一次后就变成了b字符数量最多 而且每次加入一个字符，可以在一定程度上避免两次加入相同字符(其实主要还是看判断)
代码
cpp
class Solution {
public:
string longestDiverseString(int a, int b, int c) {
priority_queue<pair<int,char>>q;
if (a > 0) q.push({a, 'a'});
if (b > 0) q.push({b, 'b'});
if (c > 0) q.push({c, 'c'});
string res;
while (q.size()) {
auto t1 = q.top();
q.pop();
int n = res.length();
//如果返回的字符串长度大于1并且取出的字符等于字符串末尾两位
if (n >= 2 && res[n - 1] == t1.second &&
res[n - 2] == t1.second) {
if (q.empty()) break; // 判断堆内是否还有元素
auto t2 = q.top();
q.pop();
res += t2.second; // 如果有就添入字符
if (--t2.first) q.push(t2); // 还有剩余就加入堆
q.push(t1);
}
else { // 如果长度等于1或者取出的字符不等于字符串末尾两位
res += t1.second; // 将该字符添入元素
if (--t1.first != 0) q.push(t1); // 如果还有剩余就加入队列
}
}
return res;
}
};
