佛山网站建设no.1,泰安肥城做网站的公司,做企业网站步骤,株洲渌口区【LetMeFly】1702.修改后的最大二进制字符串#xff1a;脑筋急转弯#xff08;构造#xff0c;贪心#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-binary-string-after-change/
给你一个二进制字符串 binary #xff0c;它仅有 0 或者 1 组…【LetMeFly】1702.修改后的最大二进制字符串脑筋急转弯构造贪心
力扣题目链接https://leetcode.cn/problems/maximum-binary-string-after-change/
给你一个二进制字符串 binary 它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改
操作 1 如果二进制串包含子字符串 00 你可以用 10 将其替换。 ulli比方说 codestrong00/strong010 - strong10/strong010/code/li
/ul
/li
li操作 2 如果二进制串包含子字符串 code10/code 你可以用 code01/code 将其替换。
ulli比方说 code000strong10/strong - 000strong01/strong/code/li
/ul
/li请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 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 105binary 仅包含 0 和 1 。
解题方法构造贪心
题目分析
如果给定字符串中没有0则不在本次讨论的范围之列直接返回原字符串。
推论1最终字符串中一定有0
仅有的两种变换分别是00-10和10-01只能减少0的个数但永远不可能将所有0消除。
推论2最终字符串中一定只有一个0
以10111011为例该字符串中有两个0则可以进行以下变换10111011-10011111-11011111具体变换过程如下
10111011
10110111 ---
10101111 ---后面的那个0不断地通过10-01的变换最终和前面那个0相邻
10011111 ---
11011111 - 相邻两个0通过00-10的变换使得二进制字符串相比于初始值更大了也就是说假设最终字符串中有两个0那么后面的那个0一定可以通过10-01的变换与前面的0相邻相邻两个0再通过00-10变换使得第一个0变成了1字符串值更大了。
若有多个0则同理最终一定只剩下一个0变成111..11011..111的形态。
为什么不继续变化了呢因为11、01都不可变唯一可变的是10-01。但是这么变的话相当于“0往前移”了字符串值更小不可取。
如何判断最终字符串中0的位置
由给定的两种变换00-10和10-01可以发现0要么被消除变换一要么左移变换二单纯的左移会导致字符串变小因此尽量将最前面的0“消除”。
如何消除通过变换一消除。通过推论2我们知道只要存在两个0则右边的0必定能千里迢迢地来到左边的0身边并与之进行变换一
111..11011..11011..11
111..11001..11111..11
111..11101..11111..11也就是说第一个0的右边每存在一个0就能让第一个0的位置“右移一位”。
最终第一个0也就是唯一的一个0的位置是原始字符串中第一个0的位置再右移 0 的总个数 − 1 0的总个数 - 1 0的总个数−1位。
具体方法
给定字符串统计其中0的个数记为cnt0。
若无0则直接返回原始字符串否则继续。
找到字符串中第一个0的位置记为pos0构造一个只有pos0 cnt0 - 1这个位置为0其余位置全部为1的字符串并返回。
时空复杂度分析
时间复杂度 O ( l e n ( b i n a r y ) ) O(len(binary)) O(len(binary))空间复杂度 O ( l e n ( b i n a r y ) ) O(len(binary)) O(len(binary))空间复杂度来自字符串构造过程中的临时变量。
AC代码
C
class Solution {
public:string maximumBinaryString(string binary) {int cnt0 count(binary.begin(), binary.end(), 0);if (!cnt0) {return binary;}int first0 binary.find(0);return string(first0 (cnt0 - 1), 1) 0 string(binary.size() - (first0 (cnt0 - 1)) - 1, 1);}
};Python
class Solution:def maximumBinaryString(self, binary: str) - str:cnt0 binary.count(0)if not cnt0:return binaryfirst0 binary.find(0)pos0 first0 (cnt0 - 1)return 1 * pos0 0 1 * (len(binary) - pos0 - 1)同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/137593422
