贪心+构造，LeetCode 1702. 修改后的最大二进制字符串

本文主要是介绍贪心+构造，LeetCode 1702. 修改后的最大二进制字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

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

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

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

2、接口描述

python3

​

class Solution:def maximumBinaryString(self, binary: str) -> str:

cpp

​

class Solution {
public:string maximumBinaryString(string binary) {}
};

3、原题链接

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

---

二、解题报告

1、思路分析

1、对于高位如果出现连续0，我们进行操作一一定可以使得结果变大

2、如果出现单个0，我们可以在后面找到一个0，通过操作二使其不断前移得到连续0，从而进行操作1

假设第一个0的位置为i，那么我们可以将所有0依次排列在i后面，然后替换为0的个数-1个1加上一个0

直接构造即可

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

3、代码详解

python3

​

class Solution:def maximumBinaryString(self, binary: str) -> str:i = binary.find('0')if i < 0:return binarycnt1 = binary.count('1', i)return '1' * (len(binary) - 1 - cnt1) + '0' + cnt1 * '1'

cpp

​

class Solution {
public:string maximumBinaryString(string binary) {int i = binary.find('0');if (i < 0) return binary;int cnt1 = count(binary.begin() + i, binary.end(), '1');return string(binary.size() - cnt1 - 1, '1') + '0' + string(cnt1, '1');}
};

这篇关于贪心+构造，LeetCode 1702. 修改后的最大二进制字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---