สมมติว่ามีสตริง สตริงนั้นเรียกว่ามีความสุขหากไม่มีสตริงใด ๆ เช่น 'aaa', 'bbb' หรือ 'ccc' เป็นสตริงย่อย หากเรามีจำนวนเต็มสามจำนวน เช่น a, b และ c ให้คืนค่าสตริง s ซึ่งเป็นไปตามเงื่อนไขต่อไปนี้ -
-
มีความสุขและยาวนานที่สุด
-
s มีตัวอักษร 'a' ได้มากที่สุด มากที่สุด b ปรากฏของตัวอักษร 'b' และมากที่สุด c ที่เกิดขึ้นของตัวอักษร 'c'
-
s จะมีเฉพาะตัวอักษร 'a', 'b' และ 'c' เท่านั้น
หากไม่มีสตริงดังกล่าว ให้คืนค่าสตริงว่าง
ดังนั้น หากอินพุตเป็น a =1, b =1, c =7 เอาต์พุตจะเป็น "ccaccbcc"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดโครงสร้างข้อมูลหนึ่งโครงสร้างที่มีอักขระ a, inx และ cnt
-
กำหนดลำดับความสำคัญของคิว pq ซึ่งจะจัดลำดับความสำคัญโดยใช้ค่า cnt ของข้อมูล
-
ถ้า a ไม่ใช่ศูนย์ แล้ว −
-
แทรกข้อมูลใหม่ ('a', a, 0) ลงใน pq
-
-
ถ้า b ไม่ใช่ศูนย์ ดังนั้น −
-
แทรกข้อมูลใหม่ ('b', b, 0) ลงใน pq
-
-
ถ้า c ไม่ใช่ศูนย์ ดังนั้น −
-
แทรกข้อมูลใหม่ ('c', c, 0) ลงใน pq
-
-
idx :=1
-
ret :=สตริงว่าง
-
ในขณะที่ true ไม่ใช่ศูนย์ ให้ทำ -
-
temp :=องค์ประกอบด้านบนของ pq
-
ลบองค์ประกอบออกจาก pq
-
หากขนาดของ ret ไม่ใช่ 0 และองค์ประกอบสุดท้ายของ ret เหมือนกับ temp.a ดังนั้น −
-
ถ้า pq ว่างเปล่า −
-
ออกจากวง
-
-
x :=อุณหภูมิ
-
temp :=องค์ประกอบด้านบนของ pq
-
ลบองค์ประกอบออกจาก pq
-
แทรก x ลงใน pq
-
-
ค่า :=0
-
ถ้าไม่ใช่ pq ว่างเปล่าและ cnt ของ temp - cnt ขององค์ประกอบแรกของ pq <2 แล้ว -
-
ค่า :=1
-
-
มิฉะนั้น
-
val :=ขั้นต่ำของ cnt ของ temp และ 2
-
-
ret :=ret concatenate val จากดัชนีของ temp.a ใน val ถึงจุดสิ้นสุด
-
temp.cnt :=temp.cnt - วาล
-
ถ้า pq ว่างเปล่า −
-
ออกจากวง
-
-
temp.idx :=idx
-
ถ้า temp.cnt> 0 แล้ว −
-
ใส่อุณหภูมิลงใน pq
-
-
(เพิ่ม idx ขึ้น 1)
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
struct Data{
char a;
int cnt;
int idx ;
Data(char c, int x, int k){
a = c;
cnt = x;
idx = k;
}
};
struct Cmp{
bool operator()(Data& a, Data& b) {
return !(a.cnt>b.cnt);
}
};
class Solution {
public:
string longestDiverseString(int a, int b, int c) {
priority_queue<Data, vector<Data>, Cmp> pq;
if (a)
pq.push(Data('a', a, 0));
if (b)
pq.push(Data('b', b, 0));
if (c)
pq.push(Data('c', c, 0));
int idx = 1;
string ret = "";
while (true) {
Data temp = pq.top();
pq.pop();
if (ret.size() && ret.back() == temp.a) {
if (pq.empty())
break;
Data x = temp;
temp = pq.top();
pq.pop();
pq.push(x);
}
int val = 0;
if (!pq.empty() && temp.cnt - pq.top().cnt < 2) {
val = 1;
}
else
val = min(temp.cnt, 2);
ret += string(val, temp.a);
temp.cnt -= val;
if (pq.empty())
break;
temp.idx = idx;
if (temp.cnt > 0)
pq.push(temp);
idx++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestDiverseString(1,1,7));
} อินพุต
1,1,7
ผลลัพธ์
ccbccacc
