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

题目描述

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

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

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

思路

看上去是贪心，那么该怎样贪？列个表试试，对两位的字符串：

00 -> 10
10 x
01 x

对三位的字符串：

000 -> 100 -> 110
001 -> 101
010 -> 001 -> 101
011 x
100 -> 110
101
110 x
111 x

那么贪心的思想也比较显然，1 是最大的数字，我们希望将 0 转换成 1，那么遇到 0 的时候就可以尝试向后寻找其他的 0，在找到下一个 0 的时候，通过 10->01 的操作将 0 前移，最后合并成为 00->10，那么可以得出以下转换：

00 -> 10
01...10 -> 10...11

可以用一个指针 l 遍历所有数字，如果当前数字为 0 则：

• 使用一个右指针 r 寻找下一个 0，如果找到了就进行更新：
• 指针 l 和 r 指向的 0 都置为1，指针 l+1 指向的值置为 0

这样的想法会 TLE：

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        binList = [ch for ch in binary]
        lbin = len(binList)
        for i, ch in enumerate(binList):
            if ch == '0':
                for j in range(i+1, lbin):
                    if binList[j] == '0':
                        binList[i] = '1'
                        binList[j] = '1'
                        binList[i+1] = '0'
                        break
        return "".join(binList)

因为这里的时间复杂度是 $O(n^2)$。

考虑如何降低时间复杂度，思考一下，在发现 0 的时候不需要在更新状态后返回，而是继续寻找下一个 0。假设在第一个 0 之后找到了 n 个 0，那么只需要更新第 l+n 个值为 0，而其他的数字都将转换成 1。

这样我们可以将上面的代码改造一下：

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        binList = [ch for ch in binary]
        lbin = len(binList)
        for i, ch in enumerate(binList):
            cnt = 0
            if ch == '0':
                for j in range(i+1, lbin):
                    if binList[j] == '0':
                        binList[i] = '1'
                        binList[j] = '1'
                        cnt+=1
                binList[i+cnt] = '0'
                return "".join(binList)
        return "".join(binList)

当然，在这种情况下我们其实不必使用一个循环去计算了，直接通过 find 和 count 进行计数就行：

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        n = len(binary)
        i = binary.find("0")
        if i < 0:
            return binary
        zeros = binary.count('0')
        s = ['1'] * n
        s[i + zeros - 1] = '0'
        return ''.join(s)

这样的时间复杂度就是 $O(n)$ 了。

想得太多