我有10个每月徽章了
在两个就可以摆脱惹
1405. Longest Happy String
一个s字串可以称做happy如果他满足下列条件
(1)只包含a、b、c
(2)没有包含aaa、bbb、ccc的子字串
(3)要包含最多的a
(4)要包含最多的b
(5)要包含最多的c
给你a、b、c的数量
请回传最长的happy字串
如果有多个请回传任何一个
思路:
用max_heap纪录目前是a、b、c哪一个数量最多
每次pop出两个
当最多的数量和第二多的数量相差 > 2时
就把最多的放2个、第二多的放1个
不然就都放2个
然后再把更新过后的数量push进heap
这样就可以得到答案了
golang code :
type h [][2]int
func (this h) Len() int { return len(this) }
func (this h) Swap(i, j int) { this[i], this[j] = this[j], this[i] }
func (this h) Less(i, j int) bool { return this[i][0] > this[j][0] }
func (this *h) Pop() interface{} {
n := len(*this)
res := (*this)[n-1]
(*this) = (*this)[:n-1]
return res
}
func (this *h) Push(x interface{}) {
*this = append(*this, x.([2]int))
}
func longestDiverseString(a int, b int, c int) string {
max_heap := h{}
if a != 0 {
heap.Push(&max_heap, [2]int{a, 0})
}
if b != 0 {
heap.Push(&max_heap, [2]int{b, 1})
}
if c != 0 {
heap.Push(&max_heap, [2]int{c, 2})
}
heap.Init(&max_heap)
var res strings.Builder
for max_heap.Len() > 0 {
tmp := heap.Pop(&max_heap).([2]int)
if max_heap.Len() == 0 {
if tmp[0] > 1 {
res.WriteByte('a' + byte(tmp[1]))
res.WriteByte('a' + byte(tmp[1]))
tmp[0] -= 2
} else {
res.WriteByte('a' + byte(tmp[1]))
tmp[0] -= 1
}
break
}
tmp1 := heap.Pop(&max_heap).([2]int)
if tmp[0]-tmp1[0] > 2 {
res.WriteByte('a' + byte(tmp[1]))
res.WriteByte('a' + byte(tmp[1]))
tmp[0] -= 2
res.WriteByte('a' + byte(tmp1[1]))
tmp1[0] -= 1
} else {
if tmp[0] > 1 {
res.WriteByte('a' + byte(tmp[1]))
res.WriteByte('a' + byte(tmp[1]))
tmp[0] -= 2
} else {
res.WriteByte('a' + byte(tmp[1]))
tmp[0] -= 1
}
if tmp1[0] > 1 {
res.WriteByte('a' + byte(tmp1[1]))
res.WriteByte('a' + byte(tmp1[1]))
tmp1[0] -= 2
} else {
res.WriteByte('a' + byte(tmp1[1]))
tmp1[0] -= 1
}
}
if tmp1[0] != 0 {
heap.Push(&max_heap, tmp1)
}
if tmp[0] != 0 {
heap.Push(&max_heap, tmp)
}
}
return res.String()
}