数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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。
方法1
这是解决问题的简单方法。首先，我们将字符串与自身合并。之后，我们将从第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 – 对left和right求和。如果总和大于其值，则更新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)
127 次浏览
