LeetCode 1702 修改后的最大二进制字符串

https://leetcode-cn.com/problems/maximum-binary-string-after-change/

法一模拟

要让二进制字符串所表示的十进制数最大，则我们需要遵循的原则有：

（1）让字符串中“1”的个数尽可能多
（2）让字符串中的“1”尽可能靠近字符串左侧

仔细观察题目中给定的操作，易知：
（1）操作1（00 --> 10）可以将两个“0”变成只含一个“0”
（2）操作2（10 --> 01）可以将“1”右侧的“0”移动到“1”的左侧
结合（1）和（2）可以推出第一个结论：修改后的最大二进制字符串最终只能含有一个“0”。下面我们来证明这个结论。

首先，证明经过有限次修改后可以将字符串中“0”的个数降为1。
假设字符串中含有(N(N > 1))个“0”，则

（1）如果有两个以上的“0”是连续的，则可以利用操作1去掉一个“0”，“0”的个数变成了(N - 1)；
（2）如果没有两个以上的“0”是连续的，则可以利用操作2不断地将“0”往字符串左侧移动，最终一定可以使得字符串至少有两个“0”是连续的，此时，转到（1）。

不断进行上述算法步骤，最终可以使得二进制字符串中“0”的个数降到1为止。

然后，证明经过有限次修改之后字符串中“0”的个数将为1时的二进制字符串是最大的。
我们假设二进制字符串中含有两个“0”，用*表示含有(N(N >= 0))个“1”的字符串。则

如果两个“0”是连续的，比如*00*，则利用操作1可以将其变成*10*。显然*10*比*00*大而且也不能继续使用操作2否则只能得到更小的数。所以此时*10*是最大的二进制字符串。
如果两个“0”不是连续的，比如*0*1*0*，则不断利用操作2可以将其变成*00*1**，再利用操作1可以变成*10*1**。显然*10*1**要比原先的*0*1*0*要大，所以此时*10*1**是最大的二进制字符串。

如果“0”的个数大于2，则选择相近的两个“0”，将剩余的“0”固定不动，重复上述的证明过程直到最终只剩一个“0”为止。

最后，显然最大的二进制字符一定是唯一的。

那怎样才能经过有限次操作得到这个最大的二进制字符串呢？参考上面的证明过程可以得到以下的操作方法：
（1）首先，字符串中从左往右起的第一个“0”左侧的“1”不能往右移动。比如1010，如果我们选择将第一个“1”往右移动，那么为了将两个“0”凑到一起，最终可以得到“0011”。然后利用操作1可以得到最终结果为1011。但是，如果我们跳过第一个“0”左侧的“1”，将第二个“0”往左移动，可以得到1001，利用操作1可以得到1101，这显然要比1011要大。虽然利用操作2时，我们把一个“1”往右移动了一位，但是移动之后两个连续的“0”利用操作1可以变得比原先的数更大。这启发我们修改的过程中要跳过第一个“0”左侧的“1”

（2）将第一个“0”右侧的所有“0”利用操作2连在一起，得到*0...00*的形式。
（3）利用操作1，将*0...0*变成*1...10*的形式，此时得到了最终结果。

实现代码如下：

class Solution {
public:
    string maximumBinaryString(string binary) {
        size_t sz = binary.size();
        int cnt0 = 0, cnt1 = 0;
        // 统计左侧连续的“1”的个数，存于idx中
        int idx = 0;
        while (binary[idx] == '1') ++idx;
        // 统计左侧连续的“1”之后的“0”和“1”的个数，分别存于cnt0和cnt1中
        for (size_t i = idx; i < sz; ++i) {
            if (binary[i] == '0') ++cnt0; else ++cnt1;
        }
        // 如果“0”的个数不足2个则直接返回
        if (cnt0 <= 1) return binary;

        string ans;
        while (idx--) ans += '1';   // 添加idx个“1”
        --cnt0;
        while (cnt0--) ans += '1';  // 添加cnt0-1个“1”和一个“0”
        ans += '0';
        while (cnt1--) ans += '1';  // 添加cnt1个“1”
        return ans;
    }
};