LeetCode 最长快乐字符串使用 JavaScript 解题
有人相爱,有人夜里开车看海,我是 leetcode 第一题都做不出来
题目
如果字符串中不含有任何 'aaa','bbb' 或 'ccc' 这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。
给你三个整数 a,b ,c,请你返回 任意一个 满足下列全部条件的字符串 s:
s 是一个尽可能长的快乐字符串。
s 中 最多 有 a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
s 中只含有 'a'、'b' 、'c' 三种字母。
如果不存在这样的字符串 s ,请返回一个空字符串 ""。
输入:a = 1, b = 1, c = 7
输出:"ccaccbcc"
解释:"ccbccacc" 也是一种正确答案。
快乐字符串中不含有三个连续相同的字母。为了找到最长的字符串,我们可以使用如下贪心策略:
尽可能优先使用当前数量最多的字母,因为最后同一种字母剩余的越多,越容易出现字母连续相同的情况。如果构建完成最长的快乐字符串后还存在剩余未选择的字母,则剩余的字母一定为同一种字母且该字母的总数量最多。
依次从当前数量最多的字母开始尝试,如果发现加入当前字母会导致出现三个连续相同字母,则跳过当前字母,直到我们找到可以添加的字母为止。实际上每次只会在数量最多和次多的字母中选择一个。
如果尝试所有的字母都无法添加,则直接退出,此时构成的字符串即为最长的快乐字符串。
上面一大串内容太多了,看不进去;来,咱们简化一下捋一下思路
第一步:建立一个二维数组,记录 a,b,c 的他们的名字和次数。
第二步:建立一个空字符串,把出现次数最多的字母加入字符串后面。
第三步:当数量最多的字母在字符串末尾出现了两次,则推入第二多的字母,以此类推。
第四步:都推不了的时候,就返回结果。
知识点
repeat
是将字符串自身进行复制,传入的参数就是复制几次
版权声明: 本文为 InfoQ 作者【董员外】的原创文章。
原文链接:【http://xie.infoq.cn/article/4f4c7393b8a24ec671614d94a】。文章转载请联系作者。
评论