算法可以发掘本质，如：
一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二，有无限多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)
{ 替换成 a ，分数更小。 a < b 都一样。 a = = b 替换成 b , 分数更小。 a > b \begin{cases} 替换成a，分数更小。 && a < b \\ 都一样。 && a == b \\ 替换成b,分数更小。 && a > b \\ \end{cases} ⎩ ⎨ ⎧替换成a，分数更小。都一样。替换成b,分数更小。a<ba==ba>b
证明一：不能将所有字符全部换到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
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。