标签： 直接构造

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'

思路

看到这道题我最先想到的是使用字符串替换，先把00的都替换为10，直到不能替换为止。然后再替换10为01，直到不能替换为止。然后再从头替换，相当于是一个while里面套两个while。

通过对具体例子的观察可以发现将10替换为01不是无条件的，我甚至还写了比较字符串大小的方法，如果字符串变小了就不变了。但其实是不行的，因为中间过程确实存在变小的情况。

最后经过观察分析发现必须要前面有0才可以替换，因为这样可以将高位的0置为1。以01110为例，最后能够转换为10111。

于是就想通过replace方法替换捕获组来实现，例如匹配 0(1*)0，替换为 10(匹配到的1)，试了一下发现replacement不支持。Pattern 类也是无法使用的。

基于上面的分析，我们可以通过算法模拟出替换过程，这里面需要用到双指针 start 与 i：

  1. 如果 start 与 i 相同且都指向1，那么直接跳过
  2. 如果 start 与 i 相差1，且 i 指向0，即00的情况，那么将 start 指向置1，start++
  3. 否则，如果 start 与 i 相差大于1，且 i 指向0，即0(1+)0的情况，那么需要将start 指向置1，start 后面的置0，i 指向的置1 即可

需要注意的是，如果 start 与 i 不同，那么 start 指向的一定是0。其实步骤2与3可以合并，只需先将 i 置1，然后再将 start 后面的置0即可。

看了官网的题解，还提供了一种直接构建的算法。

如果字符串中有多个0，总可以将它们通过10->01将其前移至第一个0的位置，然后通过00->10，使高位的0变为1。最终的结果中至多包含1个0。

因此，直接构建的方法是：从第一个0开始，后面的0全置为1，然后将第一个0后移 0的个数减1 个位置。

代码

/**
 * @date 2024-04-10 0:53
 */
public class MaximumBinaryString1702 {

    /** 直接构造 */
    public String maximumBinaryString_v2(String binary) {
        char[] b = binary.toCharArray();
        int firstZero = binary.indexOf('0');
        if (firstZero == -1) {
            return binary;
        }
        int cnt = 0;
        for (int i = firstZero; i < b.length; i++) {
            cnt += '1' - b[i];
            b[i] = '1';
        }
        b[firstZero + cnt - 1] = '0';
        return new String(b);
    }

    public String maximumBinaryString_v1(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start <= i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[i] = '1';
                b[start] = '0';
            }
        }
        return new String(b);
    }

    public String maximumBinaryString(String binary) {
        char[] b = binary.toCharArray();
        int start = 0;
        for (int i = 0; i < b.length; i++) {
            if (start == i && '1' == b[i]) {
                start++;
            } else if (start == i - 1 && '0' == b[i]) {
                b[start++] = '1';
            } else if (start < i - 1 && '0' == b[i]) {
                b[start++] = '1';
                b[start] = '0';
                b[i] = '1';
            }
        }
        return new String(b);
    }

}

性能