Java程序：找到二进制字符串旋转的开始和结束处连续放置的0的最大个数

在这个问题中，我们将编写Java代码来找到任何字符串旋转的开始和结束处的连续零的最大和。首先，我们将使用一种简单的方法来解决这个问题，它会生成二进制字符串的所有旋转，并计算开始和结束处的连续零的个数。之后，我们将学习一种优化算法，它可以计算出最大的连续零个数。

问题陈述 - 这里，我们有一个大小为N的字符串，其中只包含0和1字符。我们需要找到给定字符串的任何旋转的开始和结束处的连续零的最大和。

示例示例

输入

str = ‘001’

输出

2

解释 - 让我们计算每个旋转中起始和结束的零的总和。

• 在‘001’中，起始连续零有2个，结束零有01个。所以，最终总和为2。

• 在‘011’中，起始连续零有1个，结束零有1个。所以，最终总和为2。

• 在‘100’中，起始连续零有0个，结束零有2个。所以，最终总和为2。

最大总和为2。

输入

str = ‘11’

输出

0

解释 - 字符串中不包含任何零。

输入

str = ‘1000001’

输出结果

5

解释

• 1000001 – 开始的零 = 0，结尾的零 = 0，总和 = 0。

• 0000011 – 开始的零 = 5，结尾的零 = 0，总和 = 5。

• 0000110 – 开始的零 = 4，结尾的零 = 1，总和 = 5。

• 0001100 – 开始的零 = 3，结尾的零 = 2，总和 = 5。

• 0011000 – 开始的零 = 2，结尾的零 = 3，总和 = 5。

• 0110000 – 开始的零 = 1，结尾的零 = 4，总和 = 5。

• 1100000 – 开始的零 = 0，结尾的零 = 5，总和 = 5。

最终总和为5。

方法一

这是解决问题的朴素方法。首先，我们将字符串与自身合并。然后，我们将从第p个索引开始并与原始字符串相等的子字符串作为结果字符串。这给出了我们在二进制字符串的p次旋转后得到的结果字符串。

算法

步骤1 - 将’cnt0’变量初始化为0，以存储给定字符串中零的计数。

步骤2 - 如果’cnt0’和’len’相等，则返回’len’作为字符串只包含零。

步骤3 - 定义字符串s，并将alpha + alpha存储在其中。

步骤4 - 定义’maxZeros’变量以存储开始和结尾零的最大总和。

步骤5 - 使用循环使总迭代次数等于字符串长度。在循环中，使用’left’和’right’变量来存储最大的连续开始和结尾零。

步骤6 - 从第m个索引开始遍历字符串到(m + len)个索引。使用charAt()方法访问第m个索引处的字符，如果它等于’0’，则将’left’变量的值增加1。否则，使用’break’关键字终止循环。

步骤7 - 从(m + len – 1)个索引开始遍历字符串到m个索引，并增加’right’变量的值直到我们得到零。

步骤8 - 对左和右进行求和。如果总和大于maxZeros的值，则更新maxZeros。

步骤9 - 返回包含任何字符串旋转中开始和结尾零的最大总和的maxZeros变量的值。

示例

import java.util.*;

public class Main {
    static int getMaxZeros(String alpha, int len) {
        // count zeros in the string
        int cnt0 = 0;
        // Traverse the string
        for (int m = 0; m < len; ++m) {
            if (alpha.charAt(m) == '0')
                cnt0++;
        }
        // If total zeros are equal to len, return len
        if (cnt0 == len) {
            return cnt0;
        }
        // Merge string to find rotations
        String s = alpha + alpha;
        // to store the maximum sum of zeros
        int maxZeros = 0;
        // Traverse string
        for (int m = 0; m < len; ++m) {
            // to store zeros at the start and end
            int left = 0;
            int right = 0;
            // calculate starting zeros in the current rotation
            for (int n = m; n < m + len; ++n) {
                if (s.charAt(n) == '0') {
                    left++;
                } else {
                    break;
                }
            }
            // Calculate ending zeros
            for (int n = m + len - 1; n >= m; --n) {
                if (s.charAt(n) == '0') {
                    right++;
                } else {
                    break;
                }
            }
            // Get max value
            maxZeros = Math.max(left + right, maxZeros);
        }
        return maxZeros;
    }
    public static void main(String[] args) {
        String alpha = "10001";
        // string length
        int len = alpha.length();
        System.out.println("The maximum sum of start and end zeros in the rotations of the given string is - "
                + getMaxZeros(alpha, len));
    }
}

输出

The maximum sum of start and end zeros in the rotations of the given string is - 3

时间复杂度为O(N^2)，因为长度为N的字符串可以有N个旋转。

空间复杂度为O(N)，因为我们将合并的字符串存储起来以便使用它来获取旋转。

方法2

该方法计算给定字符串中连续零的总数。当我们旋转字符串时，我们可以观察到开头和结尾连续零的总和保持不变。

例如，当我们旋转字符串’0000011’时，我们得到’0000110’字符串，其开头和结尾零的总和等于连续零的数目。

算法

步骤1： - 在第一步中，计算字符串中零的总数，并且如果零的计数等于字符串长度，则返回长度值。

步骤2： - 变量maxZeros用于存储开头和结尾连续零的最大总和。此外，maxConsZeros变量用于存储最大连续零的计数。

步骤3： - 遍历字符串，计算字符串中的最大连续零的数目。

步骤4： - 同时更新maxZeros变量的值。

步骤5： - 计算字符串开头的连续零的总数。同时计算字符串末尾的连续零数目。

步骤6： - 如果开头和结尾连续零的和大于maxZeros，则更新maxZeros的值，并返回更新后的值。

例子

import java.util.*;

public class Main {
    static int getMaxZeros(String alpha, int len) {
        // count zeros in the string
        int cnt0 = 0;
        // Traverse the string
        for (int m = 0; m < len; ++m) {
            if (alpha.charAt(m) == '0')
                cnt0++;
        }
        // If total zeros are equal to len, return len
        if (cnt0 == len) {
            return cnt0;
        }
        // to store maximum sum of zeros
        int maxZeros = 0;
        // to store max consecutive zeros
        int maxconZeros = 0;
        for (int m = 0; m < len; m++) {
            if (alpha.charAt(m) == '0')
                maxconZeros++;
            else {
                // update max consecutive zeros
                maxZeros = Math.max(maxZeros, maxconZeros);
                maxconZeros = 0;
            }
        }
        // Change max zeros if required
        maxZeros = Math.max(maxZeros, maxconZeros);
        // Calculate the sum of zeros at the start and end
        int left = 0, right = len - 1;
        maxconZeros = 0;
        // total zeros at start
        while (alpha.charAt(left) != '1' && left < len) {
            maxconZeros++;
            left++;
        }
        // total zeros at end
        while (alpha.charAt(right) != '1' && right >= 0) {
            maxconZeros++;
            right--;
        }
        // Change the maximum sum of zeros
        maxZeros = Math.max(maxZeros, maxconZeros);
        return maxZeros;
    }
    public static void main(String[] args) {
        String alpha = "10001";
        // string length
        int len = alpha.length();
        System.out.println("The maximum sum of start and end zeros in the rotations of the given string is - "
                + getMaxZeros(alpha, len));
    }
}

输出

The maximum sum of start and end zeros in the rotations of the given string is - 3

时间复杂度 – O(N)，用于遍历给定的二进制字符串。

空间复杂度 – O(1)