Medium

题目描述

给你一个只含 0 和 1 的二进制字符串 binary。你可以使用下面的操作任意次对它进行修改：

操作 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 <= binary.length <= 10^5
  • binary 由 ‘0’ 和 ‘1’ 组成

提示： 通过这些操作，你总是可以让字符串最多只包含 1 个零。

解题思路

这道题的关键观察是理解两个操作的本质：

  1. 操作1（00 -> 10）：将左边的0变成1，右边的0保持不变
  2. 操作2（10 -> 01）：将1向左移动，0向右移动

通过这两个操作，我们可以发现一个重要规律：最终结果最多只有一个0。

核心思路：

  1. 如果字符串全是1：无法进行任何操作，直接返回原字符串
  2. 如果有0存在：我们可以通过操作让所有的1都移到前面，所有的0（除了一个）都变成1

具体策略：

  • 使用操作2将所有的1移到最前面
  • 使用操作1将连续的00变成10，这样每次操作都会减少一个0
  • 最终结果是：前面若干个1 + 一个0 + 后面若干个1

算法步骤：

  1. 找到第一个0的位置
  2. 统计总共有多少个0
  3. 如果没有0，返回原字符串
  4. 如果有k个0，最终结果是：(n-k)个1 + 1个0 + (k-1)个1

其中n是字符串长度，这个唯一的0的位置在第(n-k)位。

代码实现

class Solution {
public:
    string maximumBinaryString(string binary) {
        int n = binary.length();
        int firstZero = -1;
        int zeroCount = 0;
        
        // 找到第一个0的位置并统计0的个数
        for (int i = 0; i < n; i++) {
            if (binary[i] == '0') {
                if (firstZero == -1) {
                    firstZero = i;
                }
                zeroCount++;
            }
        }
        
        // 如果没有0，返回原字符串
        if (zeroCount == 0) {
            return binary;
        }
        
        // 构造结果：前面全是1，然后一个0在位置firstZero + zeroCount - 1，后面全是1
        string result(n, '1');
        result[firstZero + zeroCount - 1] = '0';
        
        return result;
    }
};

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        n = len(binary)
        first_zero = -1
        zero_count = 0
        
        # 找到第一个0的位置并统计0的个数
        for i in range(n):
            if binary[i] == '0':
                if first_zero == -1:
                    first_zero = i
                zero_count += 1
        
        # 如果没有0，返回原字符串
        if zero_count == 0:
            return binary
        
        # 构造结果：前面全是1，然后一个0在位置first_zero + zero_count - 1，后面全是1
        result = ['1'] * n
        result[first_zero + zero_count - 1] = '0'
        
        return ''.join(result)

public class Solution {
    public string MaximumBinaryString(string binary) {
        int n = binary.Length;
        int firstZero = -1;
        int zeroCount = 0;
        
        // 找到第一个0的位置并统计0的个数
        for (int i = 0; i < n; i++) {
            if (binary[i] == '0') {
                if (firstZero == -1) {
                    firstZero = i;
                }
                zeroCount++;
            }
        }
        
        // 如果没有0，返回原字符串
        if (zeroCount == 0) {
            return binary;
        }
        
        // 构造结果：前面全是1，然后一个0在位置firstZero + zeroCount - 1，后面全是1
        char[] result = new char[n];
        for (int i = 0; i < n; i++) {
            result[i] = '1';
        }
        result[firstZero + zeroCount - 1] = '0';
        
        return new string(result);
    }
}

var maximumBinaryString = function(binary) {
    const n = binary.length;
    let firstZero = -1;
    let zeroCount = 0;
    
    // 找到第一个0的位置并统计0的个数
    for (let i = 0; i < n; i++) {
        if (binary[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：需要遍历一次字符串统计0的个数和位置，然后构造结果字符串
  • 空间复杂度：需要创建新的字符串存储结果

相关题目