题目来源

• leetcode：358. K 距离间隔重排字符串

题目描述

class Solution {
    
public:
    string rearrangeString(string str, int k) {
    
      
    }
};

题目解析

思路：

• 准备：
  • 先统计所有字符出现的次数,存入一个map中（key = char, value = count）
  • 然后使用mapBuild a large root heap according to the number of repetitions from largest to smallest
  • 创建一个string ansObjects are used to represent results
  • 创建一个queueto sync has been added toans中的字符
• Loop through the large root heap of characters
  • The characters with the most numbers are inserted first,The number of characters after insertion-1,Then move the character to queue中（因为下一次不能插入它了,Have to wait until the length arriveskOnly then can it be inserted）
  • 然后判断queue中的元素是否为k,如果是的话,Indicates that the element at the head of the queue can be tried again to insert,So put it into the big root pile
• 最后,When the big root heap is empty：
  • 如果ans.size == ori.sizeDescription Refactoring is complete,返回ans
  • 如果ans.size != ori.size,The description also has some characters hanging onqueue中,重构失败,返回""

class Solution {
    
public:
    string rearrangeString(string str, int k) {
    
        if(k == 0){
    
            return str;
        }
        int N = str.size();
        std::string ans;
        std::unordered_map<char, int> m;
        // 遍历字符,统计字符的出现次数
        for(auto c : str){
    
            m[c]++;
        }
        // 装入大顶堆,按照字符重复次数作为比较
        std::priority_queue<pair<char, int>, std::vector<pair<char, int>>,
                cmp> maxHeap(m.begin(), m.end());
        std::queue<pair<char, int>> queue;
        while (!maxHeap.empty()){
    
            auto curr = maxHeap.top(); maxHeap.pop();// 从大顶堆取出重复次数最多的字符
            ans += curr.first;
            curr.second--;// 用掉一个字符,次数减一
            queue.push(curr);// 放入到queue中,因为k距离后还要用
            if(queue.size() == k){
    
                // queue的大小到达了k,也就是说我们已经越过了k个单位,在结果中应该要出现相同的字母了
                auto f = queue.front(); queue.pop();
                if(f.second > 0){
    
                    // 该字符的重复次数大于 0,则添加入大顶堆中,要是0那还加它干嘛
                    maxHeap.push(f);
                }
            }
        }

        return ans.size() == str.size() ? ans : "";
    }
};

类似题目

• leetcode：358. K 距离间隔重排字符串
• leetcode：621. Task Scheduler
• leetcode：767. 重构字符串（堆）