Leetcode 1702. Maximum Binary String After Change

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Maximum Binary String After Change

2. Solution

解析:Version 1,先找到第一个0,然后找到其后的第一个1,从这里开始,每碰到一个0就将其置为11之后的数字对应的置为0,相当于互换二者位置,这样让所有的0集中在一起,然后执行第一条规则。Version 2,根据规则可知,第一个0后面的零都应该跟其相连,即其后的数字顺序应按照01的顺序排序,然后将执行第一条规则。Version 3根据规则可知,如果字符串中的0少于两个,则字符串没变化,0多于1个时,最终结果只有1个0,且其位置应该位于第一个0之后的第count位,count为字符串中0的总数。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def maximumBinaryString(self, binary: str) -> str:
digits = list(binary)
n = len(digits)
i = 0
while i < n and digits[i] != '0':
i += 1
m = i
while i < n and digits[i] != '1':
i += 1
k = i
for j in range(i, n):
if digits[j] == '0':
digits[j] = '1'
digits[k] = '0'
k += 1
i = m
while i < n - 1 and digits[i] == '0' and digits[i+1] == '0':
digits[i] = '1'
i += 1
ans = ''.join(digits)
return ans
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def maximumBinaryString(self, binary: str) -> str:
digits = list(binary)
n = len(digits)
i = 0
while i < n and digits[i] != '0':
i += 1
digits = digits[:i] + sorted(digits[i:])
i = 0
while i < n - 1:
if digits[i] == '0' and digits[i+1] == '0':
digits[i] = '1'
i += 1

ans = ''.join(digits)
return ans
  • Version 3
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def maximumBinaryString(self, binary: str) -> str:
digits = ['1'] * len(binary)
count = binary.count('0')
if count <= 1:
return binary
n = len(digits)
i = 0
while i < n and binary[i] != '0':
i += 1
digits[i+count-1] = '0'
ans = ''.join(digits)
return ans

Reference

  1. https://leetcode.com/problems/maximum-binary-string-after-change/
如果有收获,可以请我喝杯咖啡!