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的数量,并计算它们的总和。最后打印所获得的最大总和。
下面是上述方法的实现:
输出:
时间复杂度: 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 中的最大值打印为结果。
以下是上述方法的实现:
输出:
时间复杂度: O(N)
辅助空间: O(1)