Re: [閒聊] 每日leetcode
2182. Construct String With Repeat Limit
先數所有字母的個數
接著建立一個max_heap把字母丟進去
用字母順來排列
每次都從heap裡拿兩個字母
最大字母順的就放滿repeatLimit
要記得看前一個字母是不是跟最大字母順一樣，是的話要記得算進去
第二大的就放一個
如果有剩要記得丟回heap
一直放到heap裡面只剩一種字母
就把最後一種字母放到答案裡就好
golang code :
type node struct {
letter byte
num int
}
type max_heap []node
func (h max_heap) Len() int { return len(h) }
func (h max_heap) Less(i, j int) bool { return h[i].letter > h[j].letter }
func (h max_heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *max_heap) Push(x interface{}) { (*h) = append((*h), x.(node)) }
func (h *max_heap) Pop() interface{} {
n := len(*h)
res := (*h)[n-1]
(*h) = (*h)[:n-1]
return res
}
func repeatLimitedString(s string, repeatLimit int) string {
rec := [26]int{}
for i := 0; i < len(s); i++ {
rec[int(s[i]-'a')]++
}
h := max_heap{}
for i := 0; i < 26; i++ {
if rec[i] != 0 {
heap.Push(&h, node{byte('a' + i), rec[i]})
}
}
ans := strings.Builder{}
for h.Len() > 0 {
first_letter := heap.Pop(&h).(node)
if h.Len() > 0 {
second_letter := heap.Pop(&h).(node)
cnt := 0
if len(ans.String())>0 && ans.String()[len(ans.String())-1] == first_letter
.letter {
cnt++
}
for first_letter.num > 0 && repeatLimit > cnt {
ans.WriteByte(first_letter.letter)
first_letter.num--
cnt++
}
ans.WriteByte(second_letter.letter)
second_letter.num--
if first_letter.num > 0 {
heap.Push(&h, first_letter)
}
if second_letter.num > 0 {
heap.Push(&h, second_letter)
}
} else {
cnt := 0
if len(ans.String())>0 && ans.String()[len(ans.String())-1] == first_letter
.letter {
cnt++
}
for first_letter.num > 0 && repeatLimit > cnt {
ans.WriteByte(first_letter.letter)
first_letter.num--
cnt++
}
break
}
}
return ans.String()
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.46 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734441837.A.415.html
推
12/17 21:26,
1年前
, 1F
12/17 21:26, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1212 之 1554 篇)：