【贪心 堆 】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)

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

对于任意a < b。 假定在a

证明二：能全部换成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);
  }
  
}

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。