极客教程C++程序 以查找任何二进制字符串的旋转中连续排放的0的数量的最大值
给定一个大小为 N 的二进制字符串 S，任务是最大化给定字符串 S 的任何旋转中连续 0 的计数在字符串开头和结尾的总和。
例子：
输入： S = “1001”
输出： 2
说明：
所有可能的旋转字符串为：
“1001”：开头的0的总数=0；结尾的0的总数=0。总和=0+0=0。
“0011”：开头的0的总数=2；结尾的0的总数=0。总和=2+0=2。
“0110”：开头的0的总数=1；结尾的0的总数=1。总和=1+1=2。
“1100”：开头的0的总数=0；结尾的0的总数=2。总和=0+2=2。
因此，最大总和为2。
输入： S = “01010”
输出： 2
说明：
所有可能的旋转字符串为：
“01010”：开头的0的总数=1；结尾的0的总数=1。总和=1+1=1。
“10100”：开头的0的总数=0；结尾的0的总数=2。总和=0+2=2。
“01001”：开头的0的总数=1；结尾的0的总数=0。总和=1+0=1。
“10010”：开头的0的总数=0；结尾的0的总数=1。总和=0+1=1。
“00101”：开头的0的总数=2；结尾的0的总数=0。总和=2+0=2。
因此，最大总和为2。
Naive方法： 最简单的想法是生成给定字符串的所有旋转字符串，并对于每个旋转字符串，计算其中连续地排放在字符串开头和结尾的0的数量，并计算它们的总和。最后打印所获得的最大总和。
下面是上述方法的实现：
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of a string present in any
// of the rotations of the given string
void findMaximumZeros(string str, int n)
{
// Check if all the characters
// in the string are 0
int c0 = 0;
// Iterate over characters
// of the string
for (int i = 0; i < n; ++i) {
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n) {
// Print n as the result
cout << n;
return;
}
// Concatenate the string
// with itself
string s = str + str;
// Stores the required result
int mx = 0;
// Generate all rotations of the string
for (int i = 0; i < n;++) {
// Store the number of consecutive 0s
// at the start and end of the string
int cs = 0;
int ce = 0;
// Count 0s present at the start
for (int j = i; j < i + n; ++j) {
if (s[j] == '0')
cs++;
else
break;
}
// Count 0s present at the end
for (int j = i + n - 1; j >= i; --j) {
if (s[j] == '0')
ce++;
else
break;
}
// Calculate the sum
int val = cs + ce;
// Update the overall
// maximum sum
mx = max(val, mx);
}
// Print the result
cout << mx;
}
// Driver Code
int main()
{
// Given string
string s = "1001";
// Store the size of the string
int n = s.size();
findMaximumZeros(s, n);
return 0;
}
输出：
2
时间复杂度: O(N 2 )
辅助空间: O(N)
高效方法: 思路是在给定字符串中查找连续0的最大数量。此外，找到字符串开头和结尾的连续 0 0，并打印它们中的最大值。
遵循以下步骤来解决问题:
- 检查字符串 S 中‘1’的频率是否等于 0 。如果是，将 N 的值打印为结果。
- 否则，执行以下步骤:
- 将给定字符串中连续0的最大数量存储在变量 X 中。
- 初始化两个变量，将 start 初始化为 0 ，将 end 初始化为 N-1 。
- 只要 S[start] 不等于‘ 1 ’，就将 cnt 和 start 增加 1 。
- 只要 S[end] 不等于‘ 1 ’，就将 cnt 增加 1 ，将 end 减少 1 。
- 将 X 和 cnt 中的最大值打印为结果。
以下是上述方法的实现:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// consecutive 0s present at the start
// and end of any rotation of the string str
void findMaximumZeros(string str, int n)
{
// Stores the count of 0s
int c0 = 0;
for (int i = 0; i < n; ++i) {
if (str[i] == '0')
c0++;
}
// If the frequency of '1' is 0
if (c0 == n) {
// Print n as the result
cout << n;
return;
}
// Stores the required sum
int mx = 0;
// Find the maximum consecutive
// length of 0s present in the string
int cnt = 0;
for (int i = 0; i < n; i++) {
if (str[i] == '0')
cnt++;
else {
mx = max(mx, cnt);
cnt = 0;
}
}
// Update the overall maximum sum
mx = max(mx, cnt);
// Find the number of 0s present at
// the start and end of the string
int start = 0, end = n - 1;
cnt = 0;
// Update the count of 0s at the开头
while (str[start] != '1' && start < n) {
cnt++;
start++;
}
// Update the count of 0s at the end
while (str[end] != '1' && end >= 0) {
cnt++;
end--;
}
// Update the maximum sum
mx = max(mx, cnt);
// Print the result
cout << mx;
}
// Driver Code
int main()
{
// Given string
string s = "1001";
// Store the size of the string
int n = s.size();
findMaximumZeros(s, n);
return 0;
}
输出:
2
时间复杂度: O(N)
辅助空间: O(1)