C++ 中最长的快乐字符串
假设有一个字符串。如果该字符串不包含任何像"aaa"、"bbb"或"ccc"这样的子字符串，则称该字符串是快乐的。假设有三个整数 a、b 和 c，则返回任意满足以下条件的字符串 s:−
s 是快乐的，并且是可能的最长字符串。
s 最多包含 1 个字母"a"，最多包含 b 个字母"b"，最多包含 c 个字母"c"。
s 只包含"a"和"b"。和"c"个字母。
如果不存在这样的字符串，则返回空字符串。
因此，如果输入为 a = 1, b = 1, c = 7，则输出为"ccaccbcc"。
为了解决这个问题，我们将遵循以下步骤 −
定义一个数据结构，其中包含字符 a、inx 和 cnt
定义一个优先级队列 pq，它将使用数据的 cnt 值进行优先级排序
如果 a 非零，则 −
将 new Data("a", a, 0) 插入 pq
如果 b 非零，则执行 −
将 new Data('b', b, 0) 插入 pq
如果 c 非零，则执行 −
将 new Data('c', c, 0) 插入 pq
idx := 1
ret := 空字符串
当 true 非零时，执行 −
temp := pq 的顶部元素
从中删除元素pq
如果 ret 的大小不为 0，且 ret 的最后一个元素与 temp.a 相同，则 −
如果 pq 为空，则 −
退出循环
x := temp
temp := pq 的顶部元素
从 pq 中删除元素
将 x 插入 pq
val := 0
如果 pq 不为空且 temp 的 cnt - pq 第一个元素的 cnt < 2，则 −
val := 1
否则
val := temp 的 cnt 和 2 中的最小值
ret := ret 将 val 从 temp.a 的索引处连接到末尾
temp.cnt := temp.cnt - val
如果 pq 为空，则 −
退出循环
temp.idx := idx
如果 temp.cnt > 0，然后减去;
将 temp 插入 pq
(将 idx 加 1)
返回 ret
示例
让我们看下面的实现，以便更好地理解 −
#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
