欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode——767.重构字符串

程序员文章站 2024-03-16 16:44:10
...

思路

  1. 使用hashmap记录字母出现频率
  2. 如何重排不可行?size()小于2字母的最高出现频率大于length+1/2
  3. 将hashmap中不为0的元素放入优先队列中,每次取优先队列最高频率的两个字母作组合

代码

class Solution {
public:
    string reorganizeString(string s) {
        //无法重新排布
        if (s.length() < 2) 
            return s;
        
        //记录字母出现频率
        vector<int> counts(26, 0);
        int maxCount = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s[i];
            counts[c - 'a']++;
            //获取最大的出现频率
            maxCount = max(maxCount, counts[c - 'a']);
        }
        //不可行的情况
        if (maxCount > (length + 1) / 2) 
            return "";
        
        //将hashmap进行挑选 压入优先队列
        auto cmp = [&](const char& letter1, const char& letter2) {
            return counts[letter1 - 'a']  < counts[letter2 - 'a'];
        };
        priority_queue<char, vector<char>,  decltype(cmp)> queue{cmp};
        for (char c = 'a'; c <= 'z'; c++) {
            if (counts[c - 'a'] > 0) {
                queue.push(c);
            }
        }

		//字符串重排
        string sb = "";
        while (queue.size() > 1) {
            //取头两个字母进行组合
            char letter1 = queue.top(); queue.pop();
            char letter2 = queue.top(); queue.pop();
            sb += letter1;
            sb += letter2;
            //hashmap对应的字母出现频率更新
            int index1 = letter1 - 'a', index2 = letter2 - 'a';
            counts[index1]--;
            counts[index2]--;
            //取后出现频率仍大于0 压入栈
            if (counts[index1] > 0) 
                queue.push(letter1);
            if (counts[index2] > 0) 
                queue.push(letter2);
        }
        //size()为奇数情况下的最后一个元素
        if (queue.size() > 0) 
            sb += queue.top();
            
        return sb;
    }
};

相关标签: Leetcode