如果字符串中不含有任何 'aaa'
,'bbb'
或 'ccc'
这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。
给你三个整数 a
,b
,c
,请你返回 任意一个 满足下列全部条件的字符串 s
:
s
是一个尽可能长的快乐字符串。s
中 最多 有a
个字母'a'
、b
个字母'b'
、c
个字母'c'
。s
中只含有'a'
、'b'
、'c'
三种字母。- 如果不存在这样的字符串
s
,请返回一个空字符串""
。
直接贪婪算法,每次只放下剩余字数最多的字母,如果已经有两个相同的,则放下第二多的。若第二多的为0,则说明无字母可放,结束循环。
class Solution: def longestDiverseString(self, a: int, b: int, c: int) -> str: # 贪婪 def findmaxmin(self, vector): if vector[0] > vector[1]: if vector[0]>vector[2]: if vector[1]>vector[2]: return [0,1,2] else: return [0,2,1] else: return [2,0,1] else: if vector[0]>vector[2]: return [1,0,2] else: if vector[2]>vector[1]: return [2,1,0] else: return [1,2,0] s = '' count = [a,b,c] prev = -1 prevv = -1 def replaceprev(self, a, prev, prevv): prevv = prev prev = a return prev, prevv while not sum(count) == 0: index = findmaxmin(self,count) nxt = index[0] if nxt == prev and nxt == prevv: nxt = index[1] if count[nxt] == 0: break if nxt == 0: s += "a" elif nxt == 1: s += "b" else: s += "c" else: if count[nxt] == 0: nxt = index[1] if count[nxt] == 0: break if nxt == 0: s += "a" elif nxt == 1: s += "b" else: s += "c" prev,prevv = replaceprev(self, nxt, prev,prevv) count[nxt] -= 1 return s
一次过。
执行用时:40 ms, 在所有 Python3 提交中击败了16.55%的用户
内存消耗:15.1 MB, 在所有 Python3 提交中击败了28.27%的用户
官方标答:一样贪心,只是高级了很多。
class Solution: def longestDiverseString(self, a: int, b: int, c: int) -> str: ans = [] cnt = [[a, 'a'], [b, 'b'], [c, 'c']] while True: cnt.sort(key=lambda x: -x[0]) hasNext = False for i, (c, ch) in enumerate(cnt): if c <= 0: break if len(ans) >= 2 and ans[-2] == ch and ans[-1] == ch: continue hasNext = True ans.append(ch) cnt[i][0] -= 1 break if not hasNext: return ''.join(ans)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-happy-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Python小知识
cnt.sort(key=lambda x: -x[0])
排序,很久没用忘了。