สมมติว่าเรามีสตริง S ให้ตรวจสอบว่าสามารถจัดเรียงตัวอักษรใหม่ได้หรือไม่เพื่อให้อักขระสองตัวที่อยู่ติดกันไม่เหมือนกัน ถ้าเป็นไปได้ ให้แสดงผลใดๆ ที่เป็นไปได้ หากไม่สามารถทำได้ ให้ส่งคืนสตริงว่าง ดังนั้นหากอินพุตเป็นเหมือน “AAB” เอาต์พุตจะเป็น “ABA”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างคิวลำดับความสำคัญของคู่อักขระจำนวนเต็มที่เรียกว่า pq กำหนดหนึ่งแผนที่ m
- n :=ขนาดของสตริง
- เก็บความถี่ของอักขระในแผนที่ m
- สำหรับคู่คีย์-ค่าแต่ละคู่ p ในหน่วย m
- แทรก (ส่วนจำนวนเต็มของ p ส่วนอักขระของ p)
- ans :=สตริงว่าง
- ในขณะที่ pq ไม่ว่างเปล่า
- ตั้งค่าหนึ่ง :=คู่บนจาก pq และลบคู่บนสุดจาก pq
- ถ้า pq ว่างเปล่า
- ถ้าเป็นจำนวนเต็มของหนึ่ง> 1 ให้คืนค่าสตริงว่าง
- ans :=ans + ส่วนของตัวละครหนึ่งตัว
- คืนสินค้า
- สอง :=คู่บนจาก pq และลบคู่บนสุดจาก pq
- ans :=ans + ส่วนของตัวละครหนึ่งตัว
- ans :=ans + ส่วนของอักขระสองตัว
- เพิ่มส่วนจำนวนเต็มของหนึ่งและสองขึ้น 1
- ถ้าส่วนจำนวนเต็มของตัวใดตัวหนึ่งไม่ใช่ 0 ให้แทรกส่วนใดส่วนหนึ่งลงใน pq
- หากส่วนจำนวนเต็มของสองส่วนไม่ใช่ 0 ให้แทรกส่วนหนึ่งลงใน pq
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
