[数据结构与算法]LeetCode767.重构字符串

题目链接:点这里
思想: 贪心
方法: 最大堆
需要先对字符串做判断, 如果最多的字符超过总字符数的一半, 那么直接返回空字符串, 如果满足条件进入下一步
使用最大堆, 堆的排序规则由字符的计数决定, 每次弹出两个最多的字符, 拼接, 如果弹出的字符没有用完, 那么计数减一在放回堆里面. 这样就能保证不会重复, 如果最后有一个字符没有弹出, 可以直接拼接.

class Solution {
public:
    string reorganizeString(string s) {
        int arr[128] = {0};
        for (int i = 0; i < s.length(); i++) {
            arr[s[i]]++;
        }
        int max = -1;
        for (int i = 'a'; i <= 'z'; i++) {
            if (max < arr[i]) max = arr[i];
        }
        // s.length()的返回值为无符号型, 所以会将int转换为uint, 使得负数变为极大数, 造成判断通过, 所以这里需要使用强转
        if (max - (int) (s.length() - max) > 1) return "";
        // 返回false把第一个放在上边, 返回true把二个放在上边
        auto cmp = [&](const char letter1, const char letter2) {
            return arr[letter1] < arr[letter2];
        };
        // 使用最大堆, 每次弹出前两个最多的字符
        priority_queue<char, vector<char>, decltype(cmp)> q{cmp};
        string sb = "";
        for (char i = 'a'; i <= 'z'; i++) {
            if (arr[i] == 0) continue;
            q.push(i);
        }
        while (q.size() > 1) {
            char letter1 = q.top(); q.pop();
            char letter2 = q.top(); q.pop();
            arr[letter1]--;
            arr[letter2]--;
            sb += letter1;
            sb += letter2;
            if (arr[letter1] != 0) q.push(letter1);
            if (arr[letter2] != 0) q.push(letter2);
        }
        if (q.size() > 0) sb += q.top();
        return sb;
    }
};