資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 次瀏覽
廣告