C++ 字符串重排

假设我们有一个字符串 S，检查其字母是否可以重新排列，使得任何两个相邻的字符都不相同。如果可以，输出任何一个可能的排列结果。如果不可以，则返回空字符串。例如，如果输入是“AAB”，则输出将是“ABA”。

为了解决这个问题，我们将遵循以下步骤：

  • 创建一个名为 pq 的整数字符对优先队列，定义一个 map m
  • n := 字符串的长度
  • 在 map m 中存储字符频率
  • 对于 m 中的每个键值对 p
    • 插入 (p 的整数部分，p 的字符部分)
  • ans := 空字符串
  • 当 pq 不为空时
    • 设置 one := pq 中的顶部对，并从 pq 中删除顶部对
    • 如果 pq 为空，则
      • 如果 one 的整数部分 > 1，则返回空字符串
      • ans := ans + one 的字符部分
      • 返回 ans
    • two := pq 中的顶部对，并从 pq 中删除顶部对
    • ans := ans + one 的字符部分
    • ans := ans + two 的字符部分
    • 将 one 和 two 的整数部分加 1
    • 如果 one 的整数部分不为 0，则将 one 插入 pq
    • 如果 two 的整数部分不为 0，则将 two 插入 pq
  • 返回 ans

让我们看下面的实现来更好地理解：

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string reorganizeString(string S) {
      priority_queue <pair <int, char>> pq;
      map <char, int> m;
      int n = S.size();
      for(int i = 0; i < n; i++){
         m[S[i]]++;
      }
      map <char, int> :: iterator i = m.begin();
      while(i != m.end()){
         pq.push({i->second, i->first});
         i++;
      }
      string ans = "";
      while(!pq.empty()){
         pair <int, char> one = pq.top();
         pq.pop();
         if(pq.empty()){
            if(one.first > 1)
            return "";
            ans += one.second;
            return ans;
         }
         pair <int, char> two = pq.top();
         pq.pop();
         ans += one.second;
         ans += two.second;
         //cout << ans << endl;
         one.first--;
         two.first--;
         if(one.first)pq.push(one);
         if(two.first)pq.push(two);
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   cout << ob1.reorganizeString("AAB") << endl;
   return 0;
}

输入

S = "AAB"
ob1.reorganizeString("AAB")

输出

ABA

更新于: 2020年4月30日

511 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告