【贪心堆】3081. 替换字符串中的问号使分数最小

算法可以发掘本质，如：
一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。
三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。
四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。
一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。而这三者是等效问题。

本文涉及知识点

贪心堆

LeetCode 3081. 替换字符串中的问号使分数最小

给你一个字符串 s 。s[i] 要么是小写英文字母，要么是问号 ‘?’ 。
对于长度为 m 且只含有小写英文字母的字符串 t ，我们定义函数 cost(i) 为下标 i 之前（也就是范围 [0, i - 1] 中）出现过与 t[i] 相同字符出现的次数。
字符串 t 的分数为所有下标 i 的 cost(i) 之和。
比方说，字符串 t = “aab” ：
cost(0) = 0
cost(1) = 1
cost(2) = 0
所以，字符串 “aab” 的分数为 0 + 1 + 0 = 1 。
你的任务是用小写英文字母替换 s 中所有问号，使 s 的分数最小。
请你返回替换所有问号 ‘?’ 之后且分数最小的字符串。如果有多个字符串的分数最小，那么返回字典序最小的一个。
示例 1：
输入：s = “???”
输出： “abc”
解释：这个例子中，我们将 s 中的问号 ‘?’ 替换得到 “abc” 。
对于字符串 “abc” ，cost(0) = 0 ，cost(1) = 0 和 cost(2) = 0 。
“abc” 的分数为 0 。
其他修改 s 得到分数 0 的字符串为 “cba” ，“abz” 和 “hey” 。
这些字符串中，我们返回字典序最小的。
示例 2：
输入： s = “a?a?”
输出： “abac”
解释：这个例子中，我们将 s 中的问号 ‘?’ 替换得到 “abac” 。
对于字符串 “abac” ，cost(0) = 0 ，cost(1) = 0 ，cost(2) = 1 和 cost(3) = 0 。
“abac” 的分数为 1 。
提示：
1 <= s.length <= 10⁵
s[i] 要么是小写英文字母，要么是 ‘?’ 。

贪心

令各字母最多出现m次。
n个相同的字母，贡献的分数是： (n-1)+ (n-2) $\cdots$ + n + 1 = n *(n-1)/2 ，和n的平方有关。
显然每个?都替换当前最少的字符，如果相等则替换最小的字符。

性质一：替换出现次数少的是局部最优解

假定两个字母分别出现了a 次，b次。
方法一：?变a。
方法二：?变b。
方案一：(a+1)a/2 + b(b-1)/2
方案二：a*(a-1)/2 + (b+1)b/2
方案一2 ： a²+a + b²-b
方案二*2：a²-a + b² +b
两者相减： 2(a-b)
$\begin{cases} 替换成a，分数更小。 && a < b \\ 都一样。 && a == b \\ 替换成b,分数更小。 && a > b \\ \end{cases}$

证明一：不能将所有字符全部换到m个

对于任意a < b。假定在a <b时，b增加了若干次。则a++,b–直到 a == b，或次数用完。根据性质一，这样更优。

证明二：能全部换成m个

所有字符出现次数只会是x1和x1+1。如果有数c小于x，则不然有数d大于等于x+1。
c++,d–，会更优。

代码

核心代码

class Solution {
public:
	string minimizeStringValue(string s) {
		int cnt[26] = { 0 };
		int star = 0;
		for (const auto& ch : s) {
			if ('?' == ch) {
				star++;
			}
			else
			{
				cnt[ch - 'a']++;
			}
		}
		std::priority_queue<pair<int,int>, vector<pair<int, int>>, greater<>> minHeap;
		for (int i = 0; i < 26; i++) {
			minHeap.emplace(make_pair(cnt[i],i));
		}
		while (star > 0) {
			auto [cnt,i1] = minHeap.top();
			minHeap.pop();
			minHeap.emplace(make_pair(cnt + 1,i1));
			star--;
		}
		int cnt2[26] = { 0 };
		while (minHeap.size()) {
			auto [iCnt, i1] = minHeap.top();
			minHeap.pop();
			cnt2[i1] = iCnt - cnt[i1];
		}
		for (int i = 0, j = 0; i < s.length(); i++) {
			if ('?' != s[i]) { continue; }
			while (0 == cnt2[j]) {
				j++;
			}
			cnt2[j]--;
			s[i] = j + 'a';
		}
		return s;
	}
};

测试用例

int main()
{	
	string s;

	{
		Solution sln;
		s = "???";
		auto res = sln.minimizeStringValue(s);
		Assert(string("abc"), res);
	}
	{
		Solution sln;
		s = "a?a?";
		auto res = sln.minimizeStringValue(s);
		Assert(string("abac"), res);
	}

	
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛