leetcode 767. Reorganize String 重构字符串-耗时100%

Problem: 767. 重构字符串

解题过程

耗时100%，优先队列的，也就是堆的，先统计字符个数，然后放入队列中，最后拿到堆顶的字符和个数，放入结果字符串，计数-1，pop堆顶，pre = tmp，然后放入下一个字符串，之前堆顶的保存在pre中，放完下一个字符，然后将pre再次放到队列，做到拿一个，隔一个放回去，保证结果字符相邻的不相同，优先放置数量多的字符，数量少的放在中间

Code

using pr = pair<int, char>; class Solution { public: int ch[26]; string reorganizeString(string s) { priority_queue<pr, vector<pr>, less<pr>> pq; memset(ch, 0, sizeof(ch)); for(char& c : s) { ch[ c - 'a' ]++; } for(int i = 0; i < 26; i++) { if(ch[i]!=0) { pq.push({ch[i], i + 'a'}); } } pr tmp, pre={-100000,'a'}; string ret; while(!pq.empty()) { tmp = pq.top(); ret += tmp.second; // if(ret.size() > 1 && ret.back()==ret[ret.size()-2]) { // return ""; // } tmp.first--; pq.pop(); if(pre.first > 0) { pq.push(pre); } pre = tmp; } if(pre.first > 0) return ""; return ret; } };