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

标签: 贪心 字符串

难度: Medium

给你一个二进制字符串 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 <= binary.length <= 105
  • binary 仅包含 '0' 和 '1' 。

Submission

运行时间: 49 ms

内存: 16.9 MB

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
            
        # 重新实现，考虑只有一个0或者是01的情况
        if '0' not in binary or binary == '01':
            return binary

        # 计算第一个0出现的位置和0的总数量
        zero_count = binary.count('0')
        first_zero_index = binary.find('0')

        # 结果字符串由以下部分构成：最前面的1，加上转换后的部分（除了一个0全部变为1）
        # 总长度减去0的数量表示原始字符串中1的数量加上第一个0前的1，再加上0的数量减1表示除了一个0之外全部变为1
        result = '1' * (first_zero_index + zero_count - 1) + '0' + '1' * (len(binary) - first_zero_index - zero_count)
        return result

Explain

题解采用的是直接计算最终结果的方法，而不是模拟每一步操作。首先，如果字符串中没有'0'，或者字符串为'01'，则直接返回原字符串，因为没有需要进行的操作。接着，计算字符串中'0'的总数量和第一个'0'出现的位置。最终结果可以通过以下方式构造：将第一个'0'之前所有的'1'保持不变，随后的所有'0'（除了最后一个'0'之外）都可以变为'1'，最后保留一个'0'，其余部分全部为'1'。这样构造的结果是在不违背操作规则的前提下，可以得到的最大二进制串。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        # 如果没有'0'或字符串为'01'，直接返回原字符串
        if '0' not in binary or binary == '01':
            return binary

        # 计算'0'的数量和第一个'0'出现的位置
        zero_count = binary.count('0')
        first_zero_index = binary.find('0')

        # 构建最大二进制字符串：
        # 1. first_zero_index + zero_count - 1 个 '1'
        # 2. 一个 '0'
        # 3. 剩余所有位置填充 '1'
        result = '1' * (first_zero_index + zero_count - 1) + '0' + '1' * (len(binary) - first_zero_index - zero_count)
        return result

Explore

这是题解中的一个错误。确实根据题目中描述的操作规则，'01'可以通过操作转换成'10'，从而得到一个更大的二进制数。正确的处理应该是在遇到'01'这种特殊情况时，直接将其转换成'10'。这种情况可能是题解作者的疏忽或者对题目理解的误解。

在给定的操作规则下，我们不能随意更改任意位置的'0'为'1'，而是要通过特定的操作来实现。操作规则通常允许我们在某些条件下将一个'0'和其后面相邻的'1'交换位置。当所有可操作的'0'都被移动到尽可能靠右的位置后，最后剩余的那个'0'不能再通过任何操作转换为'1'，因此需要保留这个'0'。

是的，这种策略能保证得到最大的二进制数。因为第一个'0'之前的所有'1'已经处于最高位，移动这些'1'的位置不会使得二进制数变得更大。我们的目标是尽可能让'1'占据更高的位，因此将第一个'0'之前的'1'保持不变，并尽可能将后续的'0'转换成'1'或移动到较低的位置，是实现这一目标的有效策略。

这个构造是基于将尽可能多的'0'转换为'1'的目标。首先，first_zero_index表示第一个'0'出现的位置，这之前的所有'1'已经是在尽可能高的位置。zero_count表示总共有多少个'0'。我们的目标是将除了最后一个'0'之外的所有'0'都转换成'1'。因此，在第一个'0'之后的位置上，我们可以有 zero_count - 1 个'0'被转换为'1'。加上原始的 first_zero_index 个'1'，总共就是 first_zero_index + zero_count - 1 个'1'。