记录一道贪心算法的题目 -----重构字符串

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了记录一道贪心算法的题目 -----重构字符串，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1813字，纯文字阅读大概需要3分钟。

内容图文

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"
示例 2:

输入: S = "aaab"
输出: ""

分析：首先统计S中各个字符出现的次数，比如说实例1中，a:2，b:1，然后放到最大堆里，每次从中拿出出现次数最多的两个字符，输出字符。接着把字符出现次数减1，如果字符出现的次数仍然大于0,那么放回最大堆里去。重新选择出现次数最多的两个字符。最后，最大堆里面要么剩下一个元素，要么不剩元素，如果剩下的那个字符出现的次数大于1,那么题目中的要求达不到，如果字符出现次数为1,就要输出。

#include <map>
#include <string>
#include <queue>
#include <iostream>
#include <vector>

using namespace std;
// 自定义优先级队列排序规则
class mycomparison
{
bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (pair<char, int>& lhs, pair<char,int>&rhs) const
  {
    if (reverse) return (lhs.second > rhs.second);
    else return (lhs.second < rhs.second);
  }
};



class Solution {
public:
    string reorganizeString(string S) 
    {
        map<char, int> my_map;
        pair<char, int> temp1, temp2;
        string s = "";
        // 查找字符串次数
        int length = S.size();
        for(int i = 0; i < length; i++)
        {
            my_map[S[i]]++;
        }
        // 放入最大堆
        priority_queue<pair<char, int>,vector<pair<char,int>> ,mycomparison> max_heap;
        map<char, int>::iterator begin = my_map.begin();
        for(begin; begin != my_map.end(); begin++)
        {
            max_heap.push(*(begin)); 
        }
　　      // 弹出两个元素
        while(max_heap.size() > 1)
        {
            temp1 = max_heap.top();
            max_heap.pop();
            temp2 = max_heap.top();
            max_heap.pop();
            s = s + temp1.first + temp2.first;
            if(temp1.second >= 2)
            {
                //减1放回去
                temp1.second -= 1;
                max_heap.push(temp1);
            }
            if(temp2.second >= 2)
            {
                //减1放回去,重新调整顺序，优先级队列，好爽^-^
                temp2.second -= 1;
                max_heap.push(temp2);
            }
        }
        if (max_heap.size() == 1)
        {
          if (max_heap.top().second == 1)
          {
                s = s + max_heap.top().first;
          }
            else
            {
                s = "";
            }
        }
        return s;
    }
};

 

内容总结

以上是互联网集市为您收集整理的记录一道贪心算法的题目 -----重构字符串全部内容，希望文章能够帮你解决记录一道贪心算法的题目 -----重构字符串所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---