สมมติว่าเรามีสตริงที่ไม่ว่าง s และจำนวนเต็ม k; เราต้องจัดเรียงสตริงใหม่เพื่อให้อักขระเดียวกันอยู่ห่างจากกันอย่างน้อย k สตริงที่กำหนดเป็นอักษรตัวพิมพ์เล็ก หากไม่มีวิธีการจัดเรียงสตริงใหม่ เราจะทำสตริงว่าง
ดังนั้น หากอินพุตเป็น s ="aabbcc", k =3 เอาต์พุตจะเป็น "abcabc" เนื่องจากตัวอักษรเดียวกันอยู่ห่างจากกันอย่างน้อย 3 ตัว
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=สตริงว่าง
-
กำหนดหนึ่งแผนที่ m
-
n :=ขนาดของ s
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
(เพิ่ม m[s[i]] ขึ้น 1)
-
-
กำหนดลำดับความสำคัญหนึ่งคิว pq
-
สำหรับแต่ละคีย์-ค่าจับคู่ในหน่วย m ให้ทำ -
-
temp :=คู่กับคีย์และค่าของมัน
-
ใส่อุณหภูมิลงใน pq
-
(เพิ่มขึ้นอีก 1)
-
-
กำหนดหนึ่ง deque dq
-
ในขณะที่ (ไม่ใช่ pq ว่างเปล่า) ทำ -
-
curr :=ด้านบนของ pq
-
ลบองค์ประกอบออกจาก pq
-
ret :=ret + curr.first
-
(ลดสกุลเงินวินาทีลง 1)
-
ใส่ curr ที่ส่วนท้ายของ dq
-
ถ้าขนาดของ dq>=k แล้ว −
-
curr :=องค์ประกอบแรกของ dq
-
ลบองค์ประกอบด้านหน้าออกจาก dq
-
ถ้าcurr.second> 0 แล้ว −
-
ใส่เคอร์เนลลงใน pq
-
-
-
-
ในขณะที่ (ไม่ใช่ dq ว่างเปล่าและองค์ประกอบแรกของ dq เหมือนกับ 0) ทำ -
-
ลบองค์ประกอบด้านหน้าออกจาก dq
-
-
return (ถ้า dq ว่างเปล่า ให้ ret หรือสตริงว่าง)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(pair<char, int> a, pair<char, int> b) {
return !(a.second > b.second);
}
};
class Solution {
public:
string rearrangeString(string s, int k) {
string ret = "";
unordered_map<char, int> m;
int n = s.size();
for (int i = 0; i < n; i++) {
m[s[i]]++;
}
unordered_map<char, int>::iterator it = m.begin();
priority_queue<pair<char, int<, vector<pair<char, int>>,
Comparator> pq;
while (it != m.end()) {
pair<char, int> temp = {it->first, it->second};
pq.push(temp);
it++;
}
deque<pair<char, int>> dq;
while (!pq.empty()) {
pair<char, int> curr = pq.top();
pq.pop();
ret += curr.first;
curr.second--;
dq.push_back(curr);
// cout << ret << " " << dq.size() << endl;
if (dq.size() >= k) {
curr = dq.front();
dq.pop_front();
if (curr.second > 0)
pq.push(curr);
}
}
while (!dq.empty() && dq.front().second == 0)
dq.pop_front();
return dq.empty() ? ret : "";
}
};
main() {
Solution ob;
cout << (ob.rearrangeString("aabbcc", 3));
} อินพุต
"aabbcc", 3
ผลลัพธ์
bacbac
