题目描述

avatar

解题思路

贪心策略,用一个大顶堆维护3个字符的数量和对应字符
每次选取剩余数量最多的字符,加入一次后就入堆

问:为什么每次都只加入一个字符,不能连续加入多个吗?

因为加入一次字符后,不一定就是三个字符中剩余数量最多的了
比如a = 8, b = 8, c = 7,取出字符a加入一次后就变成了b字符数量最多
而且每次加入一个字符,可以在一定程度上避免两次加入相同字符(其实主要还是看判断)

代码

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;
    }
};
上一篇 下一篇