一、题目

1、题目描述

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

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

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

2、接口描述

python3

​

class Solution:
    def maximumBinaryString(self, binary: str) -> str:

cpp

​

class Solution {
public:
    string maximumBinaryString(string binary) {

    }
};

3、原题链接

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

---

二、解题报告

1、思路分析

1、对于高位如果出现连续0，我们进行操作一一定可以使得结果变大

2、如果出现单个0，我们可以在后面找到一个0，通过操作二使其不断前移得到连续0，从而进行操作1

假设第一个0的位置为i，那么我们可以将所有0依次排列在i后面，然后替换为0的个数-1个1加上一个0

直接构造即可

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

3、代码详解

python3

​

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        i = binary.find('0')
        if i < 0:
            return binary
        cnt1 = binary.count('1', i)
        return '1' * (len(binary) - 1 - cnt1) + '0' + cnt1 * '1'

cpp

​

class Solution {
public:
    string maximumBinaryString(string binary) {
        int i = binary.find('0');
        if (i < 0) return binary;
        int cnt1 = count(binary.begin() + i, binary.end(), '1');
        return string(binary.size() - cnt1 - 1, '1') + '0' + string(cnt1, '1');
    }
};