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

在这个问题中，我们需要找到字符串旋转的开始和结束处的最大连续零。我们可以采取两种方法来解决这个问题。第一种方法是找到给定字符串的所有旋转，并计算开始和结束的零数。第二种方法是计算字符串中的最大连续零，并得到答案。

问题陈述 - 我们给出了大小为“len”的二进制字符串str。我们需要计算字符串的任何旋转中连续零的最大数目。

示例示例

输入

str = ‘101’

输出结果

1

解释 - 让我们计算字符串每次旋转时开头和结尾的零的数量的总和。

• 101 – 开头的零数 = 0，结尾的零数 = 0，总和 = 0

• 011 – 开头的零数 = 1，结尾的零数 = 0，总和 = 1

• 110 – 开头的零数 = 0，结尾的零数 = 1，总和 = 1

所有总和中的最大值为1。

输入

str = ‘111111111111111’

输出

0

解释 -由于一个字符串不包含0，字符串的任何旋转都不能以0开头或结尾。

输入

str = ‘110000010’

输出

5

解释

• 110000010 – sum = 1.

• 100000101 – sum = 0.

• 000001011 – sum = 5.

• 000010110 – sum =5.

• 000101100 – sum =5.

• 001011000 – sum =5.

• 010110000 – sum =5.

• 101100000 – sum =5.

• 011000001 – sum =1.

所有和中的最大和为5。

方法 1

在这个方法中，我们将找到二进制字符串的每个旋转。然后，我们将计算起始和结束零的总数。我们将在输出中打印最大的和值。

算法

步骤1 - 初始化’count0’变量存储给定字符串中零的总数。

步骤2 - 现在，我们需要计算给定字符串中零的总数。使用循环遍历字符串，如果当前字符是’0’，则将count0的值增加1。

步骤3 - 如果count0和字符串的长度相等，则表示字符串只包含零。因此，返回字符串的长度。

步骤4 - 现在，将二进制字符串合并到它自己。

步骤5 - 接下来，使用零初始化’maximumZeros’变量，用于存储开始和结束的零的最大和。

步骤6 - 开始遍历字符串并定义startZeros和endZeros变量。

步骤7 - 使用循环找到连续零的起始位置。

步骤8 - 然后，在字符串旋转中找到连续的结束零。

步骤9 - 将startZeros和endZeros的和取出。如果开始和结束零的和小于maximumZeros的值，则更新maximumZeros的值。

步骤10 - 返回maximumZeros变量的值。

示例

#include <bits/stdc++.h>
using namespace std;

int maxStartEndZeros(string str, int len){
    // To store the total count of zeros in the string
    int count0 = 0;
    // Traverse binary string
    for (int p = 0; p < len; ++p){
        if (str[p] == '0')
            count0++;
    }
    // If the string contains all zeros, return len
    if (count0 == len){
        return len;
    }
    // Merge string
    str = str + str;
    // to store maximum zeros at the start and end
    int maximumZeros = 0;
    // Traverse string
    for (int p = 0; p < len; ++p){
        // variables to store the count of zeros at the start and end
        int startZeros = 0;
        int endZeros = 0;
        // Get starting zeros in the current rotation
        for (int q = p; q < p + len; ++q){
            if (str[q] == '0')
                startZeros++;
            else
                break;
        }
        // Get end zeros in the current rotation
        for (int q = p + len - 1; q >= p; --q){
            if (str[q] == '0')
                endZeros++;
            else
                break;
        }
        // Get maximum zeros
        maximumZeros = max(startZeros + endZeros, maximumZeros);
    }
    // Return the final answer
    return maximumZeros;
}
int main(){
    // Given string
    string str = "110000010";
    // get string size
    int len = str.size();
    cout << "The maximum sum of start and end zeros in any rotation of binary string is " << maxStartEndZeros(str, len);
    return 0;
}

输出

The maximum sum of start and end zeros in any rotation of binary string is 5

时间复杂度 – O（N * N），因为我们找到了给定字符串的所有旋转。

空间复杂度 – O（N），因为我们存储了连接字符串。

方法 2

在这个方法中，我们将找到给定二进制字符串中连续零的最大数量。另外，我们将找到原始字符串中起始和结束零的和。我们将根据最大值在和最大连续零之间选择。

算法

步骤1 - 首先，我们需要计算给定字符串中零的总数。

步骤2 - 如果零的总数等于字符串长度，则返回字符串长度。

步骤3 - 定义’maximumZeros’和’maxConsZeros’变量以存储最大和最大连续零。

步骤4 - 在遍历字符串时，如果当前字符为’0’，则将maxConsZeros的值增加1。

步骤5 - 如果当前字符为’1’，则更新maximumZeros变量的值，并重新初始化maxConsZeros变量的值。

步骤6 - 定义left和right变量以存储字符串的索引。

步骤7 - 从开始位置遍历字符串直到遇到’1’，并增加left和maxConsZeros变量的值。

步骤8 - 从结束位置遍历字符串直到遇到’1’，减少righ值，并增加maxConsZeros变量的值。

步骤9 - 在更新后返回maximumZeros变量的值。

示例

#include <bits/stdc++.h>
using namespace std;

int maxStartEndZeros(string alpha, int len){
    // To store the total count of zeros in the string
    int count0 = 0;
    // Traverse binary string
    for (int p = 0; p < len; ++p){
        if (alpha[p] == '0')
            count0++;
    }
    // If string contains all zeros, return len
    if (count0 == len){
        return len;
    }
    // to store maximum zeros at start and end
    int maximumZeros = 0;
    // to store maximum consecutive zeros
    int maxConsZeros = 0;
    for (int p = 0; p < len; p++) {
        if (alpha[p] == '0')
            maxConsZeros++;
        else {
            maximumZeros = max(maximumZeros, maxConsZeros);
            // reinitialize maxConsZeros
            maxConsZeros = 0;
        }
    }
    // Get maximum consecutive zeros in the string
    maximumZeros = max(maximumZeros, maxConsZeros);
    // Get sum of consecutive zeros at start and end
    int left = 0, right = len - 1;
    maxConsZeros = 0;
    // Consecutive zeros at the left
    while (alpha[left] != '1' && left < len) {
        maxConsZeros++;
        left++;
    }
    // Consecutive zeros at the right
    while (alpha[right] != '1' && right >= 0){
        maxConsZeros++;
        right--;
    }
    // Get max value
    maximumZeros = max(maximumZeros, maxConsZeros);
    // return final result
    return maximumZeros;
}
int main(){
    // Given string
    string str = "110000010";
    // get string size
    int len = str.size();
    cout << "The maximum sum of start and end zeros in any rotation of binary string is " << maxStartEndZeros(str, len);
    return 0;
}

输出

The maximum sum of start and end zeros in any rotation of binary string is 5

时间复杂度 – O(N) 因为我们遍历字符串。

空间复杂度 – O(1) 因为我们不使用任何动态空间。

第二种方法在时间和空间复杂度上更加优化，因为我们只遍历一次字符串，不使用任何额外的空间。程序员也可以尝试找到字符串开头和结尾的最大数量的’1’，以便更多地练习类似的问题。