题解 | #二进制取反#

二进制取反

题目描述

有一个二进制字符串num，可以选择该串中的任意一段区间进行取反(可以进行一次或不进行)，取反指将0变为1，将1变为0。那么取反之后的num可能的最大的字典序是多少呢。如有num=1000，将区间[num_{2},...,num_{4} ]取反变为1111是字典序最大的。

方法一：贪心方法

解题思路

对于本题目的求解，利用贪心的思想，遇到第一段连续的0区间，将其变为1，即可得到最大的字典序。

解题代码

class Solution {
public:   
    string maxLexicographical(string num) {
        int len=num.length();
        int flag=0;
        for(int i=0;i<len;i++){//遍历
            if(num[i]=='0'){//贪心思想
                num[i]='1';
                flag=1;
            }else if(flag==1){//退出
                break;
            }
        }
        return num;
    }
};

复杂度分析

时间复杂度：一次循环，因此时间复杂度为$O(N)O(N)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：Java方法

解题思路

思路同方法一，用Java进行编程。

解题代码

import java.util.*;
public class Solution {   
    public String maxLexicographical (String num) {
        int flag=0,f=0;
        StringBuffer s=new StringBuffer();
        int len=num.length();
        for(int i=0;i<len;i++){//遍历
            if(num.charAt(i)=='1'){//贪心
                s.append('1');
                if(f==1){
                    flag=1;
                }
            }else{
                if(flag==0){
                    s.append('1');
                    f=1;
                }else{
                    s.append('0');
                }
            }
        }
        return s.toString();
    }
}

复杂度分析

时间复杂度：一次循环，因此时间复杂度为$O(N)O(N)$。

空间复杂度：使用常数级内存地址空间，因此空间复杂度为$O(1)O(1)$