专栏首页Michael阿明学习之路LeetCode 1405. 最长快乐字符串(贪心)

LeetCode 1405. 最长快乐字符串(贪心)

1. 题目

如果字符串中不含有任何 '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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-happy-string 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        vector<pair<int,char>> v;
        v.push_back({a,'a'});
        v.push_back({b,'b'});
        v.push_back({c,'c'});
        string ans;
        int len, i;
        while(true)
        {
        	len = ans.size();//记录长度,一次下来,没变化就退出
        	sort(v.rbegin(), v.rend());//剩余多的放前面
        	for(i = 0; i < v.size(); ++i)
        	{
        		if(ans.empty() || (i==0 && ans.back() != v[i].second))
        		{	//空 或者 剩余最多的字符 跟 ans末尾不同,尽量多放
        			if(v[i].first >= 2)
        			{	//尽量放两个
        				ans += v[i].second;
                        ans += v[i].second;
        				v[i].first -= 2;
        				break;
        			}
        			else if(v[i].first >= 1)
        			{
        				ans += v[i].second;
        				v[i].first -= 1;
        				break;
        			}
        		}
        		if(i != 0 && ans.back() != v[i].second)
        		{	//如果 最多的剩余字符不能放,那么次多的,只放1个
        			if(v[i].first >= 1)
        			{
        				ans += v[i].second;
        				v[i].first -= 1;
        				break;
        			}
        		}
	        }
	        if(ans.size() == len)
	        	break;//字符串没有变化,退出
        }
        return ans;
    }
};

0 ms 6.5 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 67. 二进制求和

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-binary 著作权归领扣网络所有。商业转载...

    Michael阿明
  • LeetCode 524. 通过删除字母匹配到字典里最长单词(双指针)

    给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以通过删除给定字符串的某些字符来得到。 如果答案不止一个,返回长度最长且字典顺序最小的字符...

    Michael阿明
  • LeetCode 831. 隐藏个人信息

    定义名称 name 是长度大于等于 2 (length ≥ 2),并且只包含小写字母 a-z 和大写字母 A-Z 的字符串。

    Michael阿明
  • 重温统计学\u000B①统计学研究方法概论

    抽象概念(Construct):抽象概念很难被定义和度量,也许每个人都有自己的定义方式和度量方法。

    统计学家
  • SEO人员,为什么要避免趋前退后?

    做seo与战争指挥类似,出现问题应该当机立断进行处理,应该避免趋前退后,以免耽误时机。

    蝙蝠侠IT
  • Hibernate 5 的模块/包(modules/artifacts)

    Hibernate 的功能被拆分成一系列的模块/包(modules/artifacts),其目的是为了对依赖进行独立(模块化)。

    HoneyMoose
  • 脑科学大国之争:人工智能发展将获全新“助推器”

    【新智元导读】中科院外籍院士蒲慕明在接受采访时说,由中国科技部和国家自然基金委牵头的中国脑科学计划有望于今年年内启动。这是国内人工智能产业发展的一个利好消息。 ...

    新智元
  • 来自于编程大师的职业建议:别老想着写码

    随着编程语言种类的急速扩张,程序员的需求量在2014到2024会有17%的增长率 ,这是美国劳工统计局的官方数据 -- 而其他职业的增长率只有7%。我们不得不说...

    ConardLi
  • 【编程基础】C语言常见宏定义

    我们在使用C语言编写程序的时候,常常会使用到宏定义以及宏编译指令,有的可能比较常用,有的可能并不是很常用,是不是所有的C语言宏定义以及宏指令你都清楚呢? 指令 ...

    程序员互动联盟
  • 05|指标关系:你知道并发用户数应该怎么算吗?

    我在性能综述的那三篇文章中,描述了各种指标,比如 TPS、RPS、QPS、HPS、CPM 等。我也强调了,我们在实际工作的时候,应该对这些概念有统一的认识。

    软测小生

扫码关注云+社区

领取腾讯云代金券