我有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()
}