题解 | #二进制取反#

题意整理

给定一个二进制字符串num，可以选择该串中的任意一段区间进行取反（将0变为1，或将1变为0）。
求取反之后的num可能的最大的字典序。

方法一（循环+标记）

1.解题思路

首先将字符串转化为字符数组。
然后只要遍历到一个为0的位置，则将当前所有连续为0的位变为1。并且将标记打为true。
如果标记为true，则终止循环。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    public String maxLexicographical (String num) {
        //转换为字符数组
        char[] arr=num.toCharArray();
        //终止标记
        boolean f=false;
        for(int i=0;i<arr.length;i++){
            //将当前所有连续为0的位变为1
            while(i<arr.length&&arr[i]=='0'){
                f=true;
                arr[i++]='1';
            }
            //如果取反已经进行过一次，则终止循环
            if(f) break;
        }
        return new String(arr);
    }
}

3.复杂度分析

时间复杂度：最多遍历整个字符串一次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。

方法二（循环）

1.解题思路

首先将字符串转化为字符数组。
然后通过循环找到第一个不为1的位置。
再次通过循环遍历当前所有连续为0的位，并将其变为1。如果遇到1，则终止循环。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    public String maxLexicographical (String num) {
        //转化为字符数组
        char[] arr=num.toCharArray();
        int i=0;
        //找到第一个为0的位置
        while(i<arr.length&&arr[i]=='1'){
            i++;
        }
        
        //从当前位置起，将所有连续为0的位置变为1
        while(i<arr.length&&arr[i]=='0'){
            arr[i]='1';
            i++;
        }
        return new String(arr);
    }
}

3.复杂度分析

时间复杂度：最多遍历整个字符串一次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。