1405.最长快乐字符串

链接：1405.最长快乐字符串
难度：Medium
标签：贪心、字符串、堆（优先队列）
简介：给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s。

题解 1 - cpp

• 编辑时间：2022-02-07
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：贪心,堆,每次取最大的元素进行塞入。

class Solution {
   public:
    typedef pair<char, int> node;
    string longestDiverseString(int a, int b, int c) {
        auto cmp = [&](node x, node y) -> bool { return x.second < y.second; };
        priority_queue<node, vector<node>, decltype(cmp)> q(cmp);
        q.push(make_pair('a', a));
        q.push(make_pair('b', b));
        q.push(make_pair('c', c));
        string ans = "";
        while (1) {
            node v = q.top();
            int prev_cnt = 0;  // 看看前面有几个一样的
            for (int i = ans.size() - 1; i >= 0 && ans[i] == v.first; i--)
                prev_cnt++;
            if (v.second == 0 || prev_cnt >= 2)
                break;  // 如果所有的都没了或者前面有两个一样的，就不要了
            q.pop();
            int cnt = prev_cnt == 1 ? 1 : v.second >= 2 ? 2 : 1;
            v.second -= cnt;
            while (cnt--) ans += v.first;  // 塞进去
            node nv = q.top();  // 尝试从下一个字符拿一个做间隔
            q.pop();
            if (nv.second >= 1) {
                ans += nv.first;
                nv.second -= 1;
            }
            q.push(nv);
            q.push(v);
        }
        return ans;
    }
};