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

问题描述

给你一个二进制字符串 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' 。

解题思路

因为可以将 "10" 转换为 "01"，所以可以把所有的 "0" 移到字符串的开头，把所有的 "1" 移动到字符串的末尾。

但是如果字符串的开头原本存在 "1" 的话，就不用移动。

比如说 "1010"，应该是 \(1010\to1001\to1101\)，而不是 \(1010\to0011\to1011\)。

---

class Solution:
    def maximumBinaryString(self, b: str) -> str:
        zeros = b.count("0")
        if zeros <= 1:
            return b

        k = 0
        for c in b:
            if c != "1":
                break
            k += 1

        s = "1" * (k + zeros - 1) + "0"
        return s + "1" * (len(b) - len(s))

返回顶部

在手机上阅读