Leetcode 3081. Replace Question Marks in String to Minimize Its Value

本文主要是介绍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