题意:
有一个二进制字符串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(); } }
时间复杂度:空间复杂度: