本文主要是介绍Leetcode 3081. Replace Question Marks in String to Minimize Its Value,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- Leetcode 3081. Replace Question Marks in String to Minimize Its Value
- 1. 解题思路
- 2. 代码实现
- 题目链接:3081. Replace Question Marks in String to Minimize Its Value
1. 解题思路
这一题其实感觉还是有点难的,主要一开始确实走了弯路,想着用greedy算法逐一推断每一个?
的替换字符,但是这很快就遇到了问题,因为要使得总的score最小,那么在替换时不但要考察之前的字母出现次数,还需要考察后续的字母出现次数。
但是也正因此,事实上我们只需要整体上进行分析讨论就行了,要使得最终的string的score最小,我们只需要考察已有的所有字符的出现频次然后进行?
符号的替换即可,我们只需要基于总的频数进行替换,就能很快获取我们所需要替换的字符。
然后,我们将其进行进行字符排序后依次填入即可,他们的顺序不会影响最终的score。
2. 代码实现
给出python代码实现如下:
class Solution:def minimizeStringValue(self, s: str) -> str:cnt = Counter(s)rep = []q = [(cnt[ch], ch) for ch in string.ascii_lowercase]heapq.heapify(q)for _ in range(cnt["?"]):c, ch = heapq.heappop(q)rep.append(ch)heapq.heappush(q, (c+1, ch))rep = sorted(rep)t = ""for ch in s:if ch == "?":t += rep.pop(0)else:t += chreturn t
提交代码评测得到:耗时1800ms,占用内存18.8MB。
这篇关于Leetcode 3081. Replace Question Marks in String to Minimize Its Value的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!