数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找二进制字符串任意旋转后，开头和结尾连续放置的0的最大数量
在这个问题中，我们需要找到字符串旋转后开头和结尾连续出现的0的最大数量。我们可以采用两种方法来解决这个问题。第一种方法是找到给定字符串的所有旋转，并计算开头和结尾的0的数量。第二种方法是计算字符串中连续0的最大数量，并得到答案。
问题陈述 – 我们给定一个名为str的二进制字符串，其大小等于'len'。我们需要计算该字符串任意旋转后开头和结尾连续出现的0的最大数量。
示例
输入
str = ‘101’
输出
1
解释 – 让我们计算字符串每个旋转中开头和结尾0的总和。
101 – 开头0的数量 = 0，结尾0的数量 = 0，总和 = 0
011 – 开头0的数量 = 1，结尾0的数量 = 0，总和 = 1
110 – 开头0的数量 = 0，结尾0的数量 = 1，总和 = 1
所有总和中的最大值为1。
输入
str = ‘111111111111111’
输出
0
解释 -由于字符串不包含0，因此字符串的任何旋转都不能在开头或结尾处有0。
输入
str = ‘110000010’
输出
5
解释
110000010 – 总和 = 1。
100000101 - 总和 = 0。
000001011 - 总和 = 5。
000010110 – 总和 =5。
000101100 – 总和 =5。
001011000 – 总和 =5。
010110000 – 总和 =5。
101100000 – 总和 =5。
011000001 – 总和 =1。
所有总和中的最大值为5。
方法1
在这种方法中，我们将找到二进制字符串的每个旋转。之后，我们将计算开头和结尾0的总和。我们将打印输出中的最大总和值。
算法
步骤1 – 初始化'count0'变量以存储给定字符串中0的总数。
步骤2 – 现在，我们需要计算给定字符串中0的总数。使用循环遍历字符串，如果当前字符为'0'，则将count0的值增加1。
步骤3 – 如果count0和字符串长度相等，则表示字符串仅包含0。因此，返回字符串的长度。
步骤4 – 现在，将二进制字符串与自身合并。
步骤5 – 接下来，初始化'maximumZeros'变量为零，以存储开头和结尾0的最大和。
步骤6 – 开始遍历字符串并定义startZeros和endZeros变量。
步骤7 – 使用循环查找连续的开头0。
步骤8 – 之后，在字符串旋转中查找连续的结尾0。
步骤9 – 获取startZeros和endZeros的总和。如果其小于开头和结尾0的总和，则更新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
在这种方法中，我们将找到给定二进制字符串中连续0的最大数量。此外，我们还将找到原始字符串中开头和结尾0的总和。我们将根据最大值在总和和连续0的最大数量之间进行选择。
算法
步骤1 – 最初，我们需要计算给定字符串中0的总数。
步骤2 – 如果0的总数等于字符串长度，则返回字符串长度。
步骤3 – 定义'maximumZeros'和'maxConsZeros'变量以存储最大值和连续0的最大数量。
步骤4 – 在循环遍历字符串时，如果当前字符为'0'，则将maxConsZeros的值增加1。
步骤5 – 如果当前字符为'1'，则更新maximumZeros变量的值并重新初始化maxConsZeros变量的值。
步骤6 – 定义left和right变量以存储字符串的索引。
步骤7 – 从开头遍历字符串，直到我们得到'1'，并将left和maxConsZeros变量的值增加。
步骤8 - 从结尾遍历字符串，直到我们得到'1'，减少right的值，并增加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'的最大数量，以获得更多类似问题的练习。
浏览量 118
