文章目录
- 题目描述
- 思路分析
- 完整代码
题目描述
如果字符串中不含有任何 ‘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”
解释：这是该测试用例的唯一正确答案。
思路分析
这道题的关键就是看好题目要求，题目中只有 ‘a’ ‘b’ ‘c’ 三种字母，并且这三个字母 没有三连的情况 就是 ‘aaa’ 'bbb ‘ccc’ 的情况，并且可以 以任意形式进行组合。
要组成尽可能长的串，那思路就很清晰了，贪心嘛，先看那个字母给的最多，先用两个这个最多的字母，然后用一个第二多的字母，然后再重新排序看那个最多，依次循环。 这个重新排序的过程可能用到优先队列。
大多数都是这个 贪心+优先队列的思路。
不过我在写的时候调试出了点bug，所以直接换了一个比较有意思的思路。
假设给的字母 ，6个a 4个b 3个c。
- 首先将a分组，两个a一组，则可以分成三组 分别是 aa aa aa，
- 然后遍历次多的b， 每次将每个b放到分组里，aab，aab, aab
- 此时b用了3个了。还剩一个 继续放进去了，就变成 aabb,aab,aab，
- 这时候b用完了，该去用c了,这里要注意，在用c的时候，不要重新遍历上面的分组，也就是说c要从 第二个分组 aab开始，不要从第一个分组aabb开始。所以遍历3个c，就变成了 aabbc，aabc，aabc。然后融合一下这几个就行了。
这里还有个小问题，假如给的是 a = 1, b = 1, c = 7 按照上面的思路 分组好之后是 [‘cca’,‘ccb’,‘cc’,‘c’] 拼接之后是 ccaccbccc 可以发现 末尾变成三个c了，需要去掉一个，所以程序的最后一步就是处理这个末尾就行了。
完整代码
class Solution:def longestDiverseString(self, a: int, b: int, c: int) -> str:ll = [[a,'a'],[b,'b'],[c,'c']]ll.sort(reverse=True)res = []num_max = ll[0][0]word_max = ll[0][1]# 分组最多的元素while num_max >1:res.append([word_max *2])num_max -=2if num_max == 1:res.append([word_max])# 分组最多的元素完成后，将每个元素逐次的加入到刚才分的组中，每次每组加一个元素# 将第二多的元素 每个元素加入j = 0for i in range(ll[1][0]):res[j].append(ll[1][1])j +=1if j == len(res) :j = 0# 将第三多的元素 每个元素加入k = jfor i in range(ll[2][0]):res[k].append(ll[2][1])k +=1if k == len(res) :k = 0# 将二维数组变成字符串ans = ''for i in res:ans += ''.join(i)# 处理末尾字符的多余情况for i in range(len(ans) - 3):if ans[i] == ans[i+1] == ans[i+2]:ans = ans[:i+2] # 不含末尾breakreturn ans```