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

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

• 操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。
  • 比方说， " **00** 010" -> " **10** 010"
• 操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。
  • 比方说， "000 **10** " -> "000 **01** "

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y
对应的十进制数字，那么我们称二进制字符串 __x __ 大于二进制字符串 __y __ 。

示例 1：

**输入：** binary = "000110"
**输出：** "111011"
**解释：** 一个可行的转换为：
"0001 **10** " -> "0001 **01** " 
" **00** 0101" -> " **10** 0101" 
"1 **00** 101" -> "1 **10** 101" 
"110 **10** 1" -> "110 **01** 1" 
"11 **00** 11" -> "11 **10** 11"

示例 2：

**输入：** binary = "01"
**输出：** "01"
**解释：** "01" 没办法进行任何转换。

提示：

• 1 <= binary.length <= 105
• binary 仅包含 '0' 和 '1' 。

思路

1. 要保证数字最大，首先考虑 左侧连续的 “1” 是不需要移动的
2. 因为可以 “10” -> “01” 变换，所以可以将除 左侧连续的 “1” 之外其他的 “1” 全都移到最右侧
   21. 这样处理之后，数据变为 左侧连续的 “1”，右侧连续的 “1” ，和 中间连续的 “0”
3. 然后通过 “00” -> “10” 将 中间连续的 “0” 变换
   31. 即 “000…000” -> “111..110”
   32. 这样整个数字最终就是 “111..11011..111” ，即两侧是连续的 “1” 中间一个 “0” 的情况
4. 最后，只需要计算出 “0” 是第几位，进而就可以得到最大的数字
5. 按这个思路的代码，还需要考虑处理全 “1” 的情况

图解

答题

[]

class Solution {
public:
    string maximumBinaryString(string binary) {
        int left = 0;
        int right = 0;
        bool flag = true;
        for (auto c : binary) {
            flag = (flag && c == '1');
            left += (flag && c == '1');
            right += (!flag && c == '1');
        }

        if (left + right < binary.size() - 1) {
            int k = binary.size() - right - 1;
            for (int i = 0; i < binary.size(); i++) {
                binary[i] = (i == k) ? '0' : '1';
            }
        }
        return binary;
    }
};

致谢

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

如果感觉还不错就点个赞吧~

在 我的力扣个人主页 中有我使用的做题助手项目链接，帮助我收集整理题目，可以方便的 visual studio 调试，欢迎关注，star