问题描述
如果字符串中不含有任何 'aaa'
, 'bbb'
或 'ccc'
这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。
给你三个整数 a
, b
, c
,请你返回 任意一个 满足下列全部条件的字符串 s
:
s
是一个尽可能长的快乐字符串。s
中 最多 有a
个字母'a'
、b
个字母'b'
、c
个字母'c'
。s
中只含有'a'
、'b'
、'c'
三种字母。
如果不存在这样的字符串 s
,请返回一个空字符串 ""
。
示例 1:
输入:a = 1, b = 1, c = 7
输出:"ccaccbcc"
解释:"ccbccacc" 也是一种正确答案。
示例 2:
输入:a = 2, b = 2, c = 1
输出:"aabbc"
示例 3:
输入:a = 7, b = 1, c = 0
输出:"aabaa"
解释:这是该测试用例的唯一正确答案。
提示:
0 <= a, b, c <= 100
a + b + c > 0
解题思路
贪心,即每次选择剩余数量最多的字符加入到字符串中,如果s
中最后两个字符都相同,且剩余数量最多的字符与该字符相同,就选择数量次多的那个字符;
注意细节的处理,尤其是cnt
的变化。
代码
class Solution {
public:
string longestDiverseString(int a, int b, int c) {
pair<char, int> a_num{'a', a};
pair<char, int> b_num{'b', b};
pair<char, int> c_num{'c', c};
auto cmp = [&](pair<char, int> &p1, pair<char, int> &p2) {
if (p1.second == p2.second) {
return p1.first < p2.first;
}
return p1.second < p2.second;
};
priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(cmp)> pq(cmp);
if (a > 0)
pq.push(a_num);
if (b > 0)
pq.push(b_num);
if (c > 0)
pq.push(c_num);
string res;
int cnt = 0;
while (!pq.empty() && cnt < 3) {
auto [letter, num] = pq.top();
pq.pop();
if (cnt == 2 && res[res.size() - 1] == letter) {
if (pq.empty()) {
return res;
}
auto [letter1, num1] = pq.top();
pq.pop();
res.push_back(letter1);
cnt = 1;
--num1;
if (num1 > 0) {
pq.push({letter1, num1});
}
pq.push({letter, num});
} else {
if (!res.empty() && res[res.size() - 1] != letter) {
cnt = 1;
} else {
++cnt;
}
res.push_back(letter);
--num;
if (num > 0) {
pq.push({letter, num});
}
}
}
return res;
}
};
标签:cnt,pq,num,res,push,快乐,字符串,1405
From: https://www.cnblogs.com/zwyyy456/p/17478046.html