Re: [閒聊] 每日leetcode
2182. Construct String With Repeat Limit
## 思路
先計算字元出現次數
用max_heap 存 (-ord(ch), freq)
每次pop找下一個要印出的字元, 最多印出repeatLimit 剩下的再塞回heap
如果pop的字元跟前面的相同就先印出另1個字元
e.g {'z': 4, 'x' 3} repeatLimit=3
zzz x z xx
## Code
```python
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
counter = Counter(s)
max_heap = [(-ord(ch), freq) for ch, freq in counter.items()]
heapq.heapify(max_heap)
ans = []
prev = None
while max_heap:
ch_ansi, freq = heapq.heappop(max_heap)
if prev == ch_ansi:
if not max_heap:
break
next_ch_ansi, next_freq = heapq.heappop(max_heap)
heapq.heappush(max_heap, (ch_ansi, freq))
ans.append(chr(-next_ch_ansi))
if next_freq > 1:
heapq.heappush(max_heap, (next_ch_ansi, next_freq-1))
prev = next_ch_ansi
else:
ans.append(chr(-ch_ansi) * min(freq, repeatLimit))
if freq > repeatLimit:
heapq.heappush(max_heap, (ch_ansi, freq-repeatLimit))
prev = ch_ansi
return ''.join(ans)
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734441677.A.505.html
推
12/17 21:21,
1年前
, 1F
12/17 21:21, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1211 之 1554 篇)：