要使数值变大,就是把0换成1,但问题是要求在连续区间取反,不然全部把0换成1就必然是最大了,不过那没有意义。
连续区间取反的话,必然是将前面的0变成1更容易使数值变大,因为前面数的权值更大。
1.如果开头就是0,不管几个,那么只要找到从头开始的第一个1然后将其前面部分的0全部取反即可。比如001001变成111001,前面两个0取反.
2.如果开头是1,那么咱们继续往后走去找第一个0,那是取反区间的左边界,找到后标记一下。比如1100100,左边界下标为2.
然后继续找右边界,找到标记一下。比如1100100,右边界下标为3
3.然后将左边界到右边界之间的值0转1即可。
char* maxLexicographical(char* num ) { int n = strlen(num); int left = -1, right = n-1; for(int i = 0; i<n; i++){ if(num[i] == '0' && left == -1) //遇到了0但是左边界还未确定,那么i就是左边界下标 left = i; if(num[i] == '1' && left != -1){ //遇到了1而且左边界已确定,那么i-1就是右边界下标 right = i-1; break; //左右边界都确定就可以跳出,然后取反了 } //除开两个if,其他情况是遇到的是1,但左边界都还没确定,那么不操作,直接i++,查看下一个字符是不是左边界 //或者遇到的是0,而且左边界确定,那么就继续找右边界,即进行i++ } if(left == -1) //如果查看完一遍,左边界仍旧为初始值,那么说明全都是1,没有0,已是最大,不需要取反,直接返回 return num; for(int i = left; i<=right; i++) //对于确定了左右边界的区间进行取反操作 num[i] = '1'; return num; }