当前位置：极客笔记 > Java > Java 精选笔记 > Java程序：找到二进制字符串旋转的开始和结束处连续放置的0的最大个数

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

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

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

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

示例示例

输入

str = ‘001’
Java

输出

2
Java

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

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

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

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

最大总和为2。

输入

str = ‘11’
Java

输出

0
Java

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

输入

str = ‘1000001’
Java

输出结果

5
Java

解释

  • 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));
    }
}
Java

输出

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

时间复杂度为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));
    }
}
Java

输出

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

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

空间复杂度 – O(1)

Camera课程

Camera API2 教程

API2 教程
Camera 性能教程

Perf 教程
Camera Native Framework 教程

Native FW 教程
Camera QCOM ISP 教程

ISP 教程
Camera QCOM Sensor 教程

Sensor 教程

Python教程

Python 教程

Python 教程
NumPy 教程

NumPy 教程
Django 教程

Django 教程

Java教程

Java 教程

Java 教程

Web教程

JavaScript 教程

JavaScript 教程
jQuery 教程

jQuery 教程
CSS 教程

CSS 教程
PHP 教程

PHP 教程
Laravel 教程

Laravel 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程

数据库教程

SQL 教程

SQL 教程
SQLite 教程

SQLite 教程
MySQL 教程

MySQL 教程
PL/SQL 教程

PL/SQL 教程
MongoDB 教程

MongoDB 教程

图形图像教程

OpenCV 教程

OpenCV 教程

办公软件教程

Excel 教程

Excel 教程

Linux教程

Linux命令全集

Linux命令全集
Linux内核API

Linux内核API
LVGL 教程

LVGL 教程

计算机教程

操作系统 教程

操作系统 教程
计算机网络 教程

计算机网络 教程
C语言 教程

C语言 教程
C++ 教程

C++ 教程
Swift 教程

Swift 教程

大数据教程

Hadoop 教程

Hadoop 教程
Spark 教程

Spark 教程
Scala 教程

Scala 教程

开发工具教程

Git 教程

Git 教程
Jenkins 教程

Jenkins 教程
ChatGPT 教程

ChatGPT 教程
IntelliJ 教程

IntelliJ 教程

Java 精选教程

登录

找回密码？

注册