首页 > 试题广场 >

二进制取反

[编程题]二进制取反

热度指数：4493 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

示例1

输入

"1000"

输出

"1111"

说明

如题意描述。

示例2

输入

"1001"

输出

"1111"

说明

对区间取反能使得字典序最大。

备注:

的长度不超过1000。

算法知识视频讲解

pein531

其实只要把最左边的连续0全部翻转成1就可以了

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    public String maxLexicographical (String num) {
        // write code here
        char[] str = num.toCharArray();
        // 找到第一个0
        int idx = 0;
        while(idx < str.length && str[idx] != '0') idx++;
        // 把从这个0开始的连续0全部变为1
        while(idx < str.length && str[idx] == '0') str[idx++] = '1';
        return new String(str);
    }
}

发表于 2021-10-18 16:42:48 回复(0)

tach1koma

class Solution {
public:
    string maxLexicographical(string num) {
        int n = num.size(), i = 0;
        while (i < n && num[i] == '1')
            ++i;
        while (i < n && num[i] == '0') {
            num[i] = '1';
            ++i;
        }
        return num;
    }
};

发表于 2022-01-15 12:09:22 回复(0)

Ryoryo

python题解 ：先找出0出现的位置存入列表c，然后判断首个0后面是否有连续0，得出要把0变成1的个数i+1个，然后把num首歌0前面的和 i+1个0 和连续0的最后一位后面的字符串连起来。

class Solution:
    def maxLexicographical(self , num ):
        # 第一部分找0位置
        c = []
        for i,a in enumerate(num):
            if a=='0':
                c.append(i)
        if c == []:
            return num
                # 第二部分找出连续0个数和分割点j     
        i = 0
        j = 0
        while i < len(c)-1:
            if c[i]+1 == c[i+1]:
                i += 1
                j = c[i]+1
            else:
                j = c[i]+1
                break
        num = num[0:c[0]] + '1'*(i+1) + num[j:] #连接字符串
        return num

编辑于 2022-04-06 16:10:54 回复(0)

GuoGuoCaptital

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param num string字符串

# @return string字符串

class Solution:

def maxLexicographical(self , num: str) -> str:

# write code here

n = len(num)

res = []

flag = 0

i = 0

while i < n:

j = i

if num[i] == "0" and not flag:

flag = 1

while j < n:

if num[j] == "0":

flag = 1

res.append("1")

j += 1

else:

break

i = j

else:

res.append(num[i])

i += 1

return "".join(res)

发表于 2025-06-25 11:50:07 回复(0)

Python3

牛客721126320号

class Solution:
    def maxLexicographical(self, num: str) -> str:
        # write code here
        i = 0
        numlist = list(num)
        while i < len(numlist) and numlist[i] == "1":
            i += 1
        while i < len(numlist) and numlist[i] == "0":
            numlist[i] = "1"
            i += 1
        return "".join(numlist)

发表于 2024-09-28 17:34:52 回复(0)

牛客916859058号

题意不明，我一直当作是对任意0个数大于1个数的情况取反。

发表于 2024-09-04 12:42:58 回复(0)

唐氏综合征

8岁李琛解法，简单明了

public String maxLexicographical (String num) {
        // write code here
        StringBuilder sb = new StringBuilder( num);
        for (int i = 0 ; i < num.length(); i++) {
            if (num.charAt(i) == '0') {
                int j = i;
                while (j < num.length() && num.charAt(j) == '0') {
                    sb.setCharAt(j, '1');
                    j++;
                }
                break;
            }
        }

        return sb.toString();
    }

发表于 2024-07-12 14:23:11 回复(0)

小谷围做题家

package main

import _"fmt"
import "strings"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num string字符串 
 * @return string字符串
*/
func maxLexicographical( num string ) string {
    ans:=""
    var flag bool
    var end int
    for i,ch:=range num{
        if ch=='0'{
            flag=true
        }
        if flag{
            if ch=='1'{
                end=i
                break
            }
            if i+1==len(num){
                end=i+1
                break
            }
        }
    }
    ans=strings.Repeat("1",end)+num[end:]
    return ans
}

发表于 2023-03-07 18:59:04 回复(0)

hqw11

func maxLexicographical( num string ) string {
    // write code here
    hasZero := false
    res := []byte(num)
    for i:=0; i<len(res); i++ {
        if res[i] == '0' {
            hasZero = true
            res[i] = '1'
        } else if hasZero {
            break
        }
    }
    return string(res)
}

发表于 2023-02-05 06:14:24 回复(0)

C++

牛客318321373号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    string maxLexicographical(string num) {
        // write code here
        int i = 0;
        int j = i;
        for(i=0; i<num.length(); i++){
            if(num[i] == '0'){
                while(i<num.length() && num[i] != '1'){
                    num[i] = '1';
                    i++;
                }
                break;
            }
        }
        return num;
    }
};

发表于 2022-12-09 14:51:27 回复(0)

BlueProtocol

		char[] chars = num.toCharArray();
		// 如果是第一个字符是0
		if (chars[0] == '0') {
         int oneIndex = num.indexOf("1");
         if(oneIndex == -1) {
          return num.replaceAll("0","1");
         }
         String pre = num.substring(0, oneIndex).replaceAll("0", "1");
         return pre + num.substring(oneIndex,num.length());
        }
		// 遍历
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] != '1') {
				int nextOneIndex = num.indexOf('1', i);
				if (nextOneIndex == -1) {
				 return num.replaceAll("0","1");
                }
				return num.substring(0, nextOneIndex).replaceAll("0", "1")  + num.substring(nextOneIndex,num.length());
			}
		}
		return num;

发表于 2022-10-10 12:01:13 回复(0)

真·气死我了

char* maxLexicographical(char* num ) {
    // write code here
    int i = 0;
    while (num[i]) {
        if (num[i] == '0') {
            num[i] = '1';
            if (num[i + 1] != '0')
                break;
        }
        i++;
    }
    return num;

}

发表于 2022-09-22 21:34:34 回复(0)

Python 3

LuckCen

class Solution:
    def maxLexicographical(self , num ):
        # write code here
        try:#直接替换100110000的00部分，但是1000会报错
            return num.replace('0','1',num.index('1',num.index('0'))-num.index('0'))
        except:#解决1000的情况
            return num.replace('0','1')

发表于 2022-08-09 13:31:58 回复(0)

牛客310270168号

char* maxLexicographical(char* num )
{
// write code here
int i=0;
while(num[i]=='1') i++;
while(num[i]=='0') num[i++]='1';
return num;
}

发表于 2022-08-06 16:05:30 回复(0)

Python 3

来牛客玩玩

class Solution:
    def maxLexicographical(self , num ):
        # write code here
        res = ''
        for i in range(len(num)):
            if num[i] == '0':
                while i < len(num):
                    if num[i] == '1':
                        res += num[i:]
                        return res
                    res += '1'
                    i += 1
                    if i == len(num):
                        return res
            else:
                res += num[i]
        return res

发表于 2022-07-06 23:56:42 回复(0)

Python 3

danspace

class Solution:
    def maxLexicographical(self , num ):
        # write code here
        l, r = -1, len(num)-1
        for i in range(len(num)):
            if num[i] == '0' and l==-1:
                l = i
            if num[i] == '1' and l != -1:
                r = i-1
                break
        if l==-1: return num
        res = num[:l] + '1'*len(num[l:r+1]) + num[r+1:]
        return res

发表于 2022-04-21 16:58:08 回复(0)

JavaScript

better<br/>

从左开始连续的 0 翻转即可

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param num string字符串
 * @return string字符串
 */
function maxLexicographical( num ) {
    // write code here
    let newStr = "", status = "";
    for(let i = 0; i < num.length; i ++) {
        if(+num[i] === 0 && (!status || status === "open")) {
            newStr += 1;
            status = "open";
        } else if(+num[i] === 1 && status === "open") {
            newStr += num[i];
            status = "close";
        } else {
            newStr += num[i];
        }
    }
    return newStr;
}
module.exports = {
    maxLexicographical : maxLexicographical
};

发表于 2021-12-04 17:52:22 回复(0)

Java

翠花上子弹

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num string字符串 
     * @return string字符串
     */
    public String maxLexicographical (String num) {
        // write code here
        if(num.length()<2)return "1";
        char[] max = num.toCharArray();
        int low=0,high=0;
        while(low < max.length){
            if(max[low]=='0'){
                while(max[low]=='0'&&low<max.length){
                    max[low]='1';
                low++;
                    if(low>max.length-1)
                        break;
                }
                break;
            }
            low++;
}
        String s =String.valueOf(max);
        return s;
    }
}

发表于 2021-11-18 20:16:58 回复(0)

一念永恒201907311824587

    public String maxLexicographical (String num) {
        // write code here
        char[] c = num.toCharArray();
        int a = 0;
        int b = 0;
        for(int i = 0; i < c.length; i++){
            if(c[i] == '0'){
                a = i;
                i++;
                while(i < num.length() && c[i] != '1'){
                    i++;
                }
                b = i;
                break;
            }
        }
        StringBuffer s = new StringBuffer();
        for(int i = a ;i < b; i++){
            s.append('1');
        }
        return num.substring(0,a) +s.toString() + num.substring(b,num.length());
    }
}

发表于 2021-10-13 22:26:43 回复(0)

提交观点

问题信息

字符串

上传者：小小

难度：

19条回答 49收藏 6029浏览

通过挑战的用户

查看代码

malimal...

2022-11-18 14:14:16
大胆的悲伤蛙说...

2022-10-28 23:28:10
来不及了来不及了

2022-10-23 20:16:00
牛客10556...

2022-10-18 00:47:53
牛客13331...

2022-10-07 10:05:57

二进制取反

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题