LeetCode—修改后的最大二进制字符串（贪心）

题目描述

给你一个二进制字符串 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" 没办法进行任何转换。

解题思路

原理思路：
        10可以变01，可以将0都向前推，比如110->011。00可以变10，可以消耗0将高位都变为1，比如000->110。最后只剩下一个0，不用动，此时就是最大的值。

        可能会有人觉得用10换01不是变小了么，但是要想，当0的个数大于1个的时候，将0推到前面之后就可以将00替换10，相当于用高位的1换了低位的1，一定是变大的。

        所以我们只要记录第一个0开始的位置idx，并计算0的个数m，那么最后一个0就是放在idx + m - 1的位置上，其余位填充1即可。

        最后可以用char数组合并成str，我这里直接用builder拼接也能过，别用String直接+就行，会超时。

代码实现

class Solution {public String maximumBinaryString(String binary) {int n = binary.length();int idx = binary.indexOf("0");if (idx == -1) return binary;int m = 0;for (char c: binary.toCharArray()) {if (c == '0') m++;}StringBuilder res = new StringBuilder();for (int i = 0; i < n; i++) {if (i == idx + m - 1) res.append("0");else res.append("1");}return res.toString();}
}