题意:
有一个二进制字符串num,可以选择该串中的任意一段区间进行取反(可以进行一次或不进行),取反指将0变为1,将1变为0。
那么取反之后的num可能的最大的字典序是多少呢。
方法一:
贪心
思路:贪心。
将第一段连续 0 变为 1 ,即可得到最大的字典序。
class Solution {
public:
string maxLexicographical(string num) {
int len=num.size();
int flag=0;
for(int i=0;i<len;i++){//遍历字符串
if(num[i]=='0'){//遇到第一次的连续0,则变为1
num[i]='1';
flag=1;
}else if(flag==1){//遇到1并且先前已遇到过0,则退出
break;
}
}
return num;
}
};
时间复杂度:
空间复杂度:![]()
方法二:
java模拟
思路:贪心。将第一段连续 0 变为 1 。
遍历字符串:
如果是字符'1',则追加'1';如果是第一段连续字符'0',则追加'1';如果不是第一段连续字符'0',则追加'0'。
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'){//如果是字符'1',则追加'1'
s.append('1');
if(f==1){
flag=1;
}
}else{
if(flag==0){//如果是第一段连续字符'0',则追加'1'
s.append('1');
f=1;
}else{//如果不是第一段连续字符'0',则追加'0'
s.append('0');
}
}
}
return s.toString();
}
}
时间复杂度:
空间复杂度:![]()



京公网安备 11010502036488号