数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学Python3程序：查找二进制字符串任意旋转后开头和结尾连续0的最大数量
在这个问题中，我们将编写Python代码来计算二进制字符串任意旋转后开头和结尾连续0的最大和。
问题的解决方案可以分为两个部分。第一部分是查找字符串的所有旋转。第二部分是在二进制字符串的所有旋转中查找开头和结尾的连续零。
解决此问题的另一种方法是计算最大连续零的个数。
问题陈述 – 我们需要找到给定二进制字符串任意旋转后开头和结尾连续零的最大总数。
示例
输入
str = "00100100"
输出
4
解释 – 让我们取给定字符串的所有旋转。
00100100 – 开头零 – 2，结尾零 – 2，总和 – 4。
01001000 – 开头零 – 1，结尾零 – 3，总和 – 4。
10010000 – 开头零 – 0，结尾零 – 4，总和 – 4。
00100001 – 开头零 – 2，结尾零 – 0，总和 – 2。
01000010 – 开头零 – 1，结尾零 – 1，总和 – 2。
10000100 – 开头零 – 0，结尾零 – 2，总和 – 2。
00001001 – 开头零 – 4，结尾零 – 0，总和 – 4。
00010010 – 开头零 – 3，结尾零 – 1，总和 – 4。
输入
str = ‘00000000’
输出
8
解释 – 由于字符串包含全部为零，答案等于字符串长度。
输入
str = ‘111111111’
输出
0
解释 – 由于字符串包含全部为‘1’，答案为0。
方法一
我们将字符串与自身连接起来，并从每个索引开始获取长度为N的子字符串以获得旋转字符串。之后，我们将计算开头和结尾零的总和。
算法
步骤1 – 定义变量`totalOnes`来存储给定二进制字符串中‘1’的个数。
步骤2 – 使用循环遍历字符串。如果str[p]等于‘1’，则将totalOnes加1。
步骤3 – 如果变量totalOnes的值为零，则打印字符串的长度，因为字符串只包含零。
步骤4 – 使用`+=`运算符将字符串`str`与自身连接起来，并定义变量`maxZeros`。
步骤5 – 遍历连接后的字符串。定义变量`startZeros`和`endZeros`。
步骤6 – 遍历从p到p + len索引的子字符串。如果索引q处的字符不是‘0’，则中断循环。否则，将totalZeros加1。
步骤7 – 遍历从p + len -1到p的子字符串。如果索引q处的字符不是‘0’，则中断循环。否则，将`endZeros`的计数加1。
步骤8 – 获取开头和结尾零的总和。
步骤9 – 使用max()方法从sum和maxZeros中获取最大值。
步骤10 – 打印maxZeros的值。
示例
def countStartEndZeros(str, len):
# variable to store count of ones
totalOnes = 0
# Traverse the string
for p in range(len):
if (str[p] == '1'):
totalOnes += 1
# If the string doesn't contain any 1, print the len value
if (totalOnes == 0):
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(len))
return
# Merge the string
str += str
# Maximum zeros
maxZeros = 0
# Traverse the merged string
for p in range(len):
startZeros = 0
endZeros = 0
# total zeros at start
for q in range(p, p + len):
if (str[q] != '0'):
break
else:
startZeros += 1
# total zeros at the end
for q in range(p + len - 1, p - 1, -1):
if (str[q] != '0'):
break
else:
endZeros += 1
# sum of zeros at start and end
sum = startZeros + endZeros
# change maxZeros if the sum is greater
maxZeros = max(sum, maxZeros)
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(maxZeros))
if __name__ == "__main__":
# Given string
str = "00100100"
str_size = len(str)
countStartEndZeros(str, str_size)
输出
The maximum sum of starting and end zeros in the rotation of the string is - 4
时间复杂度 – 查找每个字符串旋转为O(N*N)。
空间复杂度 – 存储连接后的字符串为O(N)。
方法二
在这种方法中，我们将根据对连续零的观察来解决问题。问题的答案是原始二进制字符串中最大连续零或开头和结尾零的总和。
算法
步骤1 – 如果二进制字符串中‘1’的总数为0，则打印字符串长度。
步骤2 – 定义变量`maxi`来存储任意旋转中开头和结尾零的最大和。
步骤3 – 定义变量`zeroConsecutive`来存储字符串中最大连续零的个数。
步骤4 – 遍历字符串，如果第p个索引处的字符为‘0’，则将`zeroConsecutive`加1。否则，使用max()方法从`maxi`和`zeroConsecutive`中获取最大值，并将结果存储到`maxi`中。同时，将`zeroConsecutive`重新初始化为零。
步骤5 – 接下来，查找字符串开头和结尾连续零的总数。
步骤6 – 如果`zeroConsecutive`的值大于`maxi`，则再次更新`maxi`的值。
步骤7 – 打印`maxi`变量的值。
示例
def countStartEndZeros(binStr, bin_size):
# one counts
cnt1 = 0
for p in range(bin_size):
if (binStr[p] == '1'):
cnt1 += 1
# print len if string size is equal to zero count
if (cnt1 == bin_size):
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(bin_size))
return
# maximum sum
maxi = 0
zeroConsecutive = 0
for p in range(bin_size):
if (binStr[p] == '0'):
zeroConsecutive += 1
else:
maxi = max(maxi, zeroConsecutive)
zeroConsecutive = 0
# Change value of maxi
maxi = max(maxi, zeroConsecutive)
# start and end zeros
left = 0
right = bin_size - 1
zeroConsecutive = 0
# lef tzeros
while (binStr[left] != '1' and left < bin_size):
zeroConsecutive += 1
left += 1
# right zeros
while (binStr[right] != '1' and right >= 0):
zeroConsecutive += 1
right -= 1
# Change value of maxi
maxi = max(maxi, zeroConsecutive)
print('The maximum sum of starting and end zeros in the rotation of the string is - {}'.format(maxi))
if __name__ == "__main__":
# Given string
str = "00100100"
str_size = len(str)
countStartEndZeros(str, str_size)
输出
The maximum sum of starting and end zeros in the rotation of the string is - 4
时间复杂度 – 遍历字符串为O(N)。
空间复杂度 – O(1)
程序员应该始终尝试找到问题的优化解决方案。首先，我们可以使用我们在第一种方法中所做的天真方法开始解决问题。之后，我们可以进一步优化它，就像我们在第二种方法中所做的那样。
浏览量：113
