好，好题

好题好题，醉了醉了

参考文章：

题库来源及思路：https://wiki.dwj601.cn/ds-and-algo/topic/base/#__tabbed_1_2

反悔贪心：https://www.cnblogs.com/RioTian/p/14513549.html

感谢感谢ξ( ✿＞◡❛)

贪心

1.1 交换类

1702. 修改后的最大二进制字符串 给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改： 操作 1 ：如果二进制串包含子字符串 “00” ，你可以用 “10” 将其替换。 比方说， “00010” -> “10010” 操作 2 ：如果二进制串包含子字符串 “10” ，你可以用 “01” 将其替换。 比方说， “00010” -> “00001” 请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。   示例 1： 输入：binary = “000110” 输出：”111011″ 解释：一个可行的转换为： “000110” -> “000101” “000101” -> “100101” “100101” -> “110101” “110101” -> “110011” “110011” -> “111011” 示例 2： 输入：binary = “01” 输出：”01″ 解释：”01″ 没办法进行任何转换。

我们可以发现，首先字符串最左边的所有1自然是不用动的，遇到从左到右第一个0的时候，从这个0开始，它往右边的所有1都可以统一通过10 -> 01给挪到最右边去：以case1为例

000110->100101->100011->101011->110111->111011 最大嘞

这样所有的0就都聚在最中间。然后再通过00 -> 10把聚在中间的所有0（假设有k个）给变成111…(k – 1个)0，这样就是最大的。

class Solution {
public:
    string maximumBinaryString(string binary) {
        int n = binary.size(), i = binary.find('0');
        if (i == string::npos) {
            return binary;
        }
        int zeros = count(binary.begin(), binary.end(), '0');
        string s(n, '1');//创建了一个长度为 n 且每个字符都是 '1' 的字符串
        s[i + zeros - 1] = '0';//无法操作改变的0
        return s;
    }
};
string::npos
查找操作的返回值：当使用 std::string 类的查找函数（如 find、rfind、find_first_of、find_last_of、find_first_not_of、find_last_not_of 等 ）时，如果没有找到匹配的字符或子字符串，这些函数会返回 string::npos。
使用 std::count(binary.begin(), binary.end(), '0') 统计 binary 中字符 '0' 的数量
count(InputIt first, InputIt last, const T& value);