leetcode 767. 重构字符串

插空法

class Solution {
public:
    string reorganizeString(string S) {
        char result[S.size()+1];
        int index = 0;
        int chrCount[26]={0};
        for(char &c:S){
            chrCount[c-'a']++;
            if(chrCount[c-'a']>(S.size()+1)/2) return "";
        }
        map<int,vector<char>,greater<int>> m;
        for(int i=0;i<26;i++) m[chrCount[i]].push_back(i+'a');
        for(auto a:m){
            for(int j=0;j<a.second.size();j++){
                for(int i=0;i<a.first;i++){
                    if(index>S.size()-1) index=1;
                    result[index] = (a.second)[j];
                    index+=2;
                }
            }
        }
        result[S.size()]=0;
        return result;
    }
};

最大堆

这个我是没有想到的，关键的一点就是利用贪心思想，又要满足题意要求，所以读取一个最大堆的顶端之后，要把它pop了，这样下一个字母就不会重复了，但是读取下一个字母之后，要再把它push进去，因为还没读完。

class Solution {
public:
    string reorganizeString(string S) {
        char result[S.size()+1];
        int index = 0;
        vector<int> charCount(26,0);
        priority_queue<pair<int,char>> maxHeap;
        for(char &c:S) {
            charCount[c-'a']++;
            if(charCount[c-'a']>(S.size()+1)/2) return "";
        }
        for(int i=0;i<26;i++) 
            if(charCount[i]!=0)
                maxHeap.push(pair<int,char>(charCount[i],'a'+i));
        pair<int,char> pre(0,' ');
        while(!maxHeap.empty()){
            pair<int,char> tmp = maxHeap.top();
            maxHeap.pop();
            if(pre.first!=0) maxHeap.push(pre);
            pre.first = tmp.first-1;
            pre.second = tmp.second;
            result[index++] = tmp.second;
        }
        result[S.size()] = 0;
        return result;
    }
};