题解 | #二进制取反#

二进制取反

http://www.nowcoder.com/practice/4ca47baf4d5f4417afc0f99d6efc7d42

描述

题目描述

首先给定我们一个二进制的字符串，我们有一次操作的机会就是把一段区间之内的地方取反，我们要返回最大的字典序

字典序： 这里最大的字典序就是这个字符串从左向右来看，前面尽可能都是1

样例解释

"1000"

这里我们可以把 $n u m 1, n u m 2, n u m 3$ ，都进行取反操作，即可得到最大的字典序

所以答案为：

"1111"

题解

解法一：C++代码

解题思路

我们可以直接找到从左边开始连续的0，将他们反转，这里注意，有可能这个字符串本身就是字典序最大了

代码实现

class Solution {
public:
    string maxLexicographical(string num) {
        int l = -1, r = num.size() - 1;
//         确定左右边界
        for (int i = 0; i < num.size(); i++) {
//             遍历字符串
            if (num[i] == '0' && l == -1) l = i;
//             如果发现0，并且左边界未确定，更新左边界
            if (num[i] == '1' && l != -1) {
//                 如果发现1，并且左边界已经确定，更新右边界并且跳出循环
                r = i - 1;
                break;
            }
        }
        if (l == -1) return num;
//         如果全都是1，直接返回
        for (int i = l; i <= r; i++) num[i] = '1';
//         执行反转操作后返回
        return num;
    }
};

图解代码

alt

时空复杂度分析

时间复杂度： $O (n)$

理由如下：这里我们最坏的情况就是把我们整个字符串遍历一遍，字符串的长度是 $n$ , 所以我们的时间复杂度是 $O (n)$

但是由于本题的数据范围极小，如果就本题而言，可以理解为 $O (1)$

空间复杂度： $O (1)$

理由如下：为引入新的变量空间

解法二：Java代码

解题思路

先找到最开始的连续的0，然后反转即可实现操作最大值

代码实现

import java.util.*;


public class Solution {
    public String maxLexicographical (String num) {
        int l = -1, r = num.length() - 1;
//         第一步把我们的左边界变成-1，右边界变成最后那个单词
        for (int i = 0; i < num.length(); i++) {
//             遍历我们的字符产
            if (num.charAt(i) == '0' && l == -1) l = i;
//             如果找到0，并且左边界未确定，这时候确定左边界
            if (num.charAt(i) == '1' && l != -1) {
//                 找到1，并且左边界确定了，那么更新有边界跳出循环
                r = i;
                break;
            }
        }
        if (l == -1) return num;
//         如果已经是全1的状态，直接返回原来的字符串就可以了
        StringBuffer res = new StringBuffer();
        for (int i = l; i <= r; i++) res.append('1');
//         把这段区间内的1加进来
        return num.substring(0, l) + res.toString() + num.substring(r + 1, num.length());
//         执行一个字符串的拼接操作
    }
}