首页 > 其他分享 >1405.最长快乐字符串

1405.最长快乐字符串

时间:2023-06-13 16:44:59浏览次数:53  
标签:cnt pq num res push 快乐 字符串 1405

问题描述

1405. 最长快乐字符串 (Medium)

如果字符串中不含有任何 'aaa''bbb''ccc' 这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。

给你三个整数 abc,请你返回 任意一个 满足下列全部条件的字符串 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

相关文章

  • 28.找出字符串中第一个匹配项的下标 (Medium)
    问题描述28.找出字符串中第一个匹配项的下标(Medium)给你两个字符串haystack和needle,请你在haystack字符串中找出needle字符串的第一个匹配项的下标(下标从0开始)。如果needle不是haystack的一部分,则返回-1。示例1:输入:haystack="sadbutsad",needle="sad......
  • 字符串哈希算法
    问题描述考虑1044.最长重复子串(Hard),本题思路并不难,可以使用二分答案来解决,假设答案为mid,那么长度大于mid的子串在s中只会出现一次,否则至少出现两次。因此只需要考虑子串在s中的出现次数即可,比较直接的想法是使用key为string的unordered_map,然而unoredere_map......
  • Python如何把字符串中形如'\uXXXX'的Unicode字符转换为原始字符
    jsonpickle保存的文本有形如"\u6211\u7684"的字符,看起来很不方便,怎么转换为原始字符呢?参考如下代码:importjsonpickle#定义一个包含Unicode编码字符的字符串text="我的名字是\u674e\u5b87\u5b87"#将字符串保存为JSON格式json_string=jsonpickle.encode(text)......
  • python 中格式化字符串
     001、format>>>"{0}love{1}.{2}".format("I","FishC","com")##位置参数'IloveFishC.com'>>>"{a}love{b}.{c}".format(a="I",b="FishC"......
  • 代码随想录算法训练营第五天| 242.有效的字母异位词 , 349. 两个数组的交集 , 202. 快
    242.有效的字母异位词 繁冗版:1,思路:先建立两个map,对应两个字符串对应的字符,同时对他们进行计数,如果这两个数字相等,那么就是相等2,代码1boolisAnagram_complicate(strings,stringt)2{3unordered_map<char,int>existedCharBys;45for(autoch......
  • 「UOJ700」可爱多的字符串
    题目有一次机灵鬼和学长可爱多打比赛,可爱多不会做一道字符串题,机灵鬼做了很久终于做出来了,这是机灵鬼第一次做出可爱多不会的题。可爱多觉得很丢人,于是准备研究字符串。可爱多精通\(\mathrm{kmp}\)算法。\(\mathrm{kmp}\)算法的输入是一个字符串\(S\),该算法的核心是对每个......
  • leetCode1768.交替合并字符串 && [1679] K 和数对的最大数目
    题目:给你两个字符串word1和word2。请你从word1开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。返回合并后的字符串。      输入:word1="abc",word2="pqr"      输出:"apbqcr......
  • 2023-06-12:如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为
    2023-06-12:如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为超级回文数。现在,给定两个正整数L和R(以字符串形式表示),返回包含在范围[L,R]中的超级回文数的数目。输入:L="4",R="1000"。输出:4。答案2023-06-12:该算法的基本思路是从较小的回文数开始......
  • 2023-06-12:如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为
    2023-06-12:如果一个正整数自身是回文数,而且它也是一个回文数的平方,那么我们称这个数为超级回文数。现在,给定两个正整数L和R(以字符串形式表示),返回包含在范围[L,R]中的超级回文数的数目。输入:L="4",R="1000"。输出:4。答案2023-06-12:该算法的基本思路是从较小的回......
  • Educational Codeforces Round 9-C. The Smallest String Concatenation(字符串排序)
    原题链接C.TheSmallestStringConcatenationtimelimitpertestmemorylimitpertestinputoutputn strings a1, a2, ..., an.You'dliketoconcatenatethemtogetherinsomeordersuchthattheresultings......