数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 最长快乐字符串
假设有一个字符串。如果该字符串不包含任何诸如“aaa”、“bbb”或“ccc”之类的子字符串，则称其为快乐字符串。如果我们有三个整数 a、b 和 c，则返回任何满足以下条件的字符串 s：
s 是快乐的，并且尽可能长。
s 最多包含 an 次字母“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 连接从 temp.a 的索引到 val 结尾的 val。
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
586 次浏览
