JZX轻语：简

LeetCode每日一题(20240410) - 修改后的最大二进制字符串

发表于2024年04月10日

比较偏脑筋急转弯的题目，类似于冒泡排序。分析可以得到，题目的两个操作只能将0往前面挪，不能往后面移动，且两个以上的连续0可以最终合并成一个0(在最后一个连续0的位置上)。因此，可以有以下做法：将所有的0都逐步冒泡集合到第一个0的后面, 然后再全部合并至只剩下一个0。而第一个0就没必要往前移动了，这样结果会更小(最后剩下的0的位置会往前了)。

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        first_zero_pos = -1  # 第一个零的位置
        zero_cnt = 0  # 零的计数
        for i, ch in enumerate(binary):
            if ch == '0':
                if first_zero_pos == -1:
                    first_zero_pos = i
                zero_cnt += 1
        if zero_cnt <= 1:  # 零的计数小于等于1, 直接返回即可
            return binary
        # 将所有的0都拼接在第一个0后面，然后除了最后一个0, 其他都转为1
        return '1' * (first_zero_pos + zero_cnt - 1) + '0' + '1' * (len(binary) - first_zero_pos - zero_cnt)

闪念标签：LC

题目链接：https://leetcode.cn/problems/maximum-binary-string-after-change/description/