做网站怎么选服务器,嘉兴快速建站合作,网站建设的常用软件有哪些,哪个网站做中高端衣服上一篇博客#xff1a;LeetCode 2529. 正整数和负整数的最大计数 写在前面#xff1a;大家好#xff01;我是晴空๓。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正#xff0c;感谢大家的不吝赐教。我的唯一博客更新地址是#xff1a;https://ac-fun.blog.…上一篇博客LeetCode 2529. 正整数和负整数的最大计数 写在前面大家好我是晴空๓。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正感谢大家的不吝赐教。我的唯一博客更新地址是https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油冲鸭 用知识改变命运用知识成就未来加油 (ง •̀o•́)ง (ง •̀o•́)ง 原题链接LeetCode 1702. 修改后的最大二进制字符串 文章目录 题目信息题目描述示例 1示例 2提示 题解解题思路解题代码力扣官方题解 题目信息
题目描述 给你一个二进制字符串 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 1 0 5 {10^5} 105binary 仅包含 0和 1 。
题解
解题思路 本题的标签是 贪心 和 字符串贪心类的题目还是第一次做最开始的想法是尽量将 0 变成 1而且 1 的位置越靠左越好但是具体实现没有想出来。贪心算法还需要多做一些题目去体会贪心算法的思想和证明方法。《算法竞赛进阶指南》里面是这样介绍贪心算法的 贪心是一种在每次决策时采取当前意义下最优策略的解法因此使用贪心法要求问题的整体最优性可以由局部最优性导出。贪心算法的正确性需要证明常见的证明手段有 微扰 证明在任意局面下任何对局部最优策略的微小改变都会造成整体结果变差。经常以 “排序” 为贪心策略的证明。范围缩放 证明对局部最优策略作用范围的扩展都不会造成整体结果变差。决策包容性 证明在任意局面下做出局部最优决策以后在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换言之这个局部最优策略提供的可能性包含其他所有策略提供的可能性。反证法数学归纳法 解题代码力扣官方题解
class Solution {public String maximumBinaryString(String binary) {int n binary.length();char[] s binary.toCharArray();int j 0;for (int i 0; i n; i) {if (s[i] 0) {while (j i || (j n s[j] 1)) {j;}if (j n) {s[j] 1;s[i] 1;s[i 1] 0;}}}return new String(s);}
}作者力扣官方题解
链接https://leetcode.cn/problems/maximum-binary-string-after-change/solutions/2726979/xiu-gai-hou-de-zui-da-er-jin-zhi-zi-fu-c-put3/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
