Python3程序——在二进制字符串的任意旋转中找到连续放置在开头和结尾的0的最大数量

在这个问题中，我们将编写Python代码来计算字符串开头和结尾连续0的最大总和。

问题的解决可以分为两个部分。第一部分是找到字符串的所有旋转。第二部分是找到二进制字符串所有旋转中开始和结束的连续0。

解决问题的另一种方法是计算最大连续0的数量可以解答问题。

问题陈述 - 我们需要找到给定二进制字符串的任意旋转中开始和末尾的最大连续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

Explanation – 由于字符串中全为零，答案等于字符串长度。

Input

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’，则退出循环。否则，增加’endZeros’的计数。

步骤 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)。

方法2

在这种方法中，我们将根据连续的零的观察来解决问题。问题的答案要么是最大连续零，要么是原始二进制字符串中起始和末尾零的和。

算法

第1步 - 如果二进制字符串中1的总数为0，则打印字符串的长度。

第2步 - 定义maxi变量来存储任何旋转中起始和末尾零的最大和。

第3步 - 定义’zeroConsecutive’变量来存储字符串中最大连续的零。

第4步 - 遍历字符串，如果第pth个索引处的字符为’0’，则将’zeroConsecutive’加1。否则，使用max()方法从’maxi’和’zeroConsecutive’中获取最大值，并将结果存储到’maxi’中。同时，将’zeroConsecutive’重新初始化为零。

第5步 - 接下来，找到字符串起始和末尾的连续零的总数。

第6步 - 如果’zeroConsecutive’的值更大，则再次更新’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)

程序员应该始终尝试寻找问题的最优解。首先，我们可以使用天真的方法来解决问题，就像我们在第一种方法中所做的那样。然后，我们可以进一步优化，就像我们在第二种方法中所做的那样。