Python3 程序用于查找二进制字符串中任意旋转开始和结束处连续放置的最大 0 数量
在这个问题中，我们将编写 Python 代码来计算字符串开始和结束处连续零的最大和。
问题解决方案可分为两个部分。第一部分是查找字符串的所有旋转。第二部分是查找二进制字符串所有旋转中的开始和结束连续零。
另一种解决问题的方法是计算最大连续零的数量，这样可以解答问题。
问题陈述 – 我们需要找到给定二进制字符串的任何旋转开始和结束时的最大连续零的总数。
示例
输入
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。
方法 1
我们将字符串与其自身联系起来，并从每个索引开始获取长度为 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"，则"0"中断循环。否则，增加"endZeros"的计数。
步骤 8 – 获取起始零和结束零的总和。
步骤 9 – 使用 max() 方法从 sum 和 maxZeros 中获取最大值。
步骤 10 – 打印 maxZeros 的值。
示例
def countStartEndZeros(str, len):
# 变量来存储 1 的数量
totalOnes = 0
# 遍历字符串
for p in range(len):
if (str[p] == '1'):
totalOnes += 1
# 如果字符串不包含任何 1，则打印 len 值
if (totalOnes == 0):
print('字符串旋转中起始和结束零的最大和为 - {}'.format(len))
return
# 合并字符串
str += str
# 最大零数
maxZeros = 0
# 遍历合并后的字符串
for p in range(len):
startZeros = 0
endZeros = 0
# 开始时总共有 0
for q in range(p, p + len):
if (str[q] != '0'):
break
else:
startZeros += 1
# 最后总共有 0
for q in range(p + len - 1, p - 1, -1):
if (str[q] != '0'):
break
else:
endZeros += 1
# 开始和结束时的零之和
sum = startZeros + endZeros
# 如果总和大于，则更改 maxZeros
maxZeros = max(sum, maxZeros)
print('字符串旋转中起始零和结束零的最大和为 - {}'.format(maxZeros))
if __name__ == "__main__":
# 给定字符串
str = "00100100"
str_size = len(str)
countStartEndZeros(str, str_size)
输出
字符串旋转中起始和结束零的最大和为 - 4
时间复杂度 – 用于查找每个字符串旋转的 O(N*N)。
空间复杂度 – 用于存储连接的字符串的 O(N)。
方法 2
在这种方法中，我们将根据连续零的观察来解决问题。问题的答案是原始二进制字符串中的最大连续零或起始和结束零的总和。
算法
步骤 1 – 如果二进制字符串中 1 的总数为 0，则打印字符串长度。
步骤 2 – 定义 maxi 变量以存储任何旋转中起始和结束零的最大和。
步骤 3 – 定义"zeroConsecutive"变量以存储字符串中的最大连续零。
步骤 4 – 遍历字符串，如果第 p 个索引处的字符为"0"，则将"zeroConsecutive"加 1。否则，使用 max() 方法从 maxi 和 zeroConsecutive 中获取最大值，并将结果存储到"maxi"中。此外，用零重新初始化 zeroConsecutive。
步骤 5 – 接下来，找到字符串开头和结尾处连续零的总数。
步骤 6 – 再次，如果'zeroConsecutive'的值更大，则更新'maxi\'变量的值。
步骤 7 – 打印'maxi'变量的值。
示例
def countStartEndZeros(binStr, bin_size):
# 一个计数
cnt1 = 0
for p in range(bin_size):
if (binStr[p] == '1'):
cnt1 += 1
# 如果字符串大小等于零，则打印 len 计数
if (cnt1 == bin_size):
print('字符串旋转中起始和结束零的最大和为 - {}'.format(bin_size))
return
# 最大和
maxi = 0
zeroConsecutive = 0
for p in range(bin_size):
if (binStr[p] == '0'):
zeroConsecutive += 1
else:
maxi = max(maxi, zeroConsecutive)
zeroConsecutive = 0
# 改变 maxi 的值
maxi = max(maxi, zeroConsecutive)
# 起始和结束零
left = 0
right = bin_size - 1
zeroConsecutive = 0
# 左零
while (binStr[left] != '1' and left < bin_size):
zeroConsecutive += 1
left += 1
# 右零
while (binStr[right] != '1' and right >= 0):
zeroConsecutive += 1
right -= 1
# 改变 maxi 的值
maxi = max(maxi, zeroConsecutive)
print('字符串旋转中起始和结束零的最大和为 - {}'.format(maxi))
if __name__ == "__main__":
# 给定字符串
str = "00100100"
str_size = len(str)
countStartEndZeros(str, str_size)
输出
字符串旋转中起始和结束零的最大和为 - 4
遍历字符串的时间复杂度 – O(N)。
空间复杂度 – O(1)
程序员应始终尝试找到问题的优化解决方案。首先，我们可以像在第一种方法中一样使用朴素方法开始解决问题。之后，我们可以像在第二种方法中一样进一步优化它。
