首页 > 试题广场 >

二进制取反

[编程题]二进制取反

热度指数：3905 时间限制：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。

算法知识视频讲解

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)

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)