LeetCode 1702.修改后的最大二进制字符串:脑筋急转弯(构造,贪心)

news/2024/5/19 17:24:01 标签: leetcode, 算法, 题解, 思维, 贪心

【LetMeFly】1702.修改后的最大二进制字符串:脑筋急转弯(构造,贪心

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

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

  • 操作 1 :如果二进制串包含子字符串 "00" ,你可以用 "10" 将其替换。
    <ul>
    	<li>比方说, <code>"<strong>00</strong>010" -> "<strong>10</strong>010"</code></li>
    </ul>
    </li>
    <li>操作 2 :如果二进制串包含子字符串 <code>"10"</code> ,你可以用 <code>"01"</code> 将其替换。
    <ul>
    	<li>比方说, <code>"000<strong>10</strong>" -> "000<strong>01</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 <= 105
  • binary 仅包含 '0' 和 '1'

解题方法:构造(贪心

题目分析

如果给定字符串中没有0,则不在本次讨论的范围之列,直接返回原字符串。

推论1:最终字符串中一定有0

仅有的两种变换分别是00->1010->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的形态。

为什么不继续变化了呢?因为1101都不可变,唯一可变的是10->01。但是这么变的话相当于“0往前移”了,字符串值更小,不可取。

如何判断最终字符串中0的位置?

由给定的两种变换00->1010->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 binary
        first0 = binary.find('0')
        pos0 = first0 + (cnt0 - 1)
        return '1' * pos0 + '0' + '1' * (len(binary) - pos0 - 1)

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/137593422


http://www.niftyadmin.cn/n/5481593.html

相关文章

35-3 使用dnslog探测fastjson漏洞

一、DNSLog 原理 DNSLog是一种记录在DNS上的域名相关信息的机制,类似于日志文件,记录了对域名或IP的访问信息。了解多级域名的概念对理解DNSLog至关重要。因特网采用树状结构的命名方法,按照组织结构划分域,每个域都是名字空间中被管理的一个划分,可以进一步划分为子域。域…

springboot+nodejs+vue残联残疾人信息服务系统django+python设计与实现

前端开发框架:vue.js 框架支持:django/sprinngboot/php/Ssm/flask/express均支持 语言&#xff1a;pythonjavanode.jsphp均支持 数据库 mysql 版本不限 数据库工具&#xff1a;Navicat/SQLyog等都可以 运行软件:idea/eclipse/vscode/pycharm/wamp/phpstudy均支持 设计框架&…

tcp 为什么要三次握手

TCP三次握手流程&#xff1a; 首先客户端发起请求&#xff0c;想服务端发送SYN报文服务端接收到客户端请求过后&#xff0c;产生SYNACK报文&#xff0c;并将SYNACK报文返回给客户端客户端收到SYNACK报文之后将此报文再发回服务端&#xff0c;至此三次握手完成&#xff0c;连接…

鸿蒙开发 一 (二)、熟悉鸿蒙之剑 ArkTS

ArkTS是HarmonyOS主要应用开发语言&#xff0c;以后也别在弄那个 java 和鸿蒙的混合版了&#xff0c; 没必要浪费时间&#xff0c; 一步到位&#xff0c; 学新的吧。 简介 ArkTS围绕应用开发在TypeScript&#xff08;简称TS&#xff09;生态基础上做了进一步扩展&#xff0c;保…

90天玩转Python—16—基础知识篇:面向对象知识详解

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇:C站最全Python标准库总结 90天玩转Python--02--基础知识篇:初识Python与PyCharm 90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装) 90天玩转Python—04—基础知识篇:Pytho…

SpringBoot和Vue2项目配置https协议

1、SpringBoot项目 ① 去你自己的云申请并下载好相关文件&#xff0c;SpringBoot下载的是Tomcat&#xff08;默认&#xff09;&#xff0c;Vue2下载的是Nginx ② 将下载的压缩包里面的.pfx后缀文件拷贝到项目的resources目录下 ③ 编辑配置文件 &#xff08;主要是框里面的内…

“植物大战僵尸:机器学习引领游戏AI新革命“

上期回顾&#xff1a; 今天给大家推荐一个Gtihub开源项目&#xff1a;PythonPlantsVsZombies&#xff0c;翻译成中就是植物大战僵尸。 《植物大战僵尸》是一款极富策略性的小游戏。可怕的僵尸即将入侵&#xff0c;每种僵尸都有不同的特点&#xff0c;例如铁桶僵尸拥有极强的抗…

牛客论坛项目中使用到Redis的地方总结

实体分为很多类&#xff0c;实体的确定要通过实体类型和实体id两个属性同时确定。牛客论坛中使用到了3类实体&#xff1a; 1 登录 使用到的Redis命令&#xff1a; set key value // 设置指定key的值为value get key // 获取指定key的值1.1 存储/获取验证码 验证码文本&…