1405. 最长快乐字符串 (Medium)
2024-10-21 06:01:07
问题描述
如果字符串中不含有任何 '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 <= 100a + 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;
}
};
最新文章
- sql的优化相关问题
- centos 关闭防火墙
- Java系列：JVM指令详解（上）（zz）
- （DFS）hdoj1312-Red and Black
- STL源码分析读书笔记--第二章--空间配置器（allocator）
- PHP学习笔记——PHP脚本和JAVA连接mysql数据库
- 两个for循环例子
- Node.js CVE-2017-1484复现（详细步骤）
- android 中的ExpandableListView取消一级图标
- Docker学习笔记 - Docker的基本概念
- [物理学与PDEs]第1章第7节 媒质中的 Maxwell 方程组 7.3 媒质中电磁场量的表示
- javeEE第二周
- POI导入具有合并了单元格的Excel
- spark面试总结1
- day5 笔记
- 转：The Difference Between a LayoutTransform and a RenderTransform
- yii2 使用多个数据库的案例
- 怎样从本地删除git远程仓库里面的文件
- Universal-Image-Loader解析（一）——ImageLoaderConfiguration的详细配置
- Android 获取本地外网IP、内网IP、计算机名等信息