LeetCode 1702. 修改后的最大二进制字符串——每日一题

上一篇博客：LeetCode 2529. 正整数和负整数的最大计数

 写在前面：大家好！我是晴空๓。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油，冲鸭！
 用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง

原题链接：LeetCode 1702. 修改后的最大二进制字符串

题目信息

题目描述

 给你一个二进制字符串 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 <= $10^5$
• binary 仅包含 '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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。