C++ 将二进制字符串中的1和0分别分隔到不同的半部分

在这个教程中，我们需要将给定二进制字符串中的所有1和0分隔到两个半部分。在这里，我们需要从给定字符串中取一个子字符串并翻转它，以便将0和1分隔到不同的部分。最终，我们需要计算子字符串分隔1和0到两个半部分所需的翻转总数。

问题陈述 ：我们有一个偶数长度的二进制字符串。我们需要多次从给定字符串中取任意子字符串并将其翻转，以使其分成两半。最后，我们需要打印所需翻转总数。

示例：

Input –  str = 0011

Output – 0

说明

由于字符串分成了两半，所以我们不需要进行任何反转。

Input –  str = 0011101000

Output – 2

解释

• 首先，从第5个索引开始，取长度为2的子字符串并反转它。结果字符串将为0011110000。

• 然后，从开头取长度为6的字符串并反转它。结果字符串将为1111000000。

Input –  str = 010101

Output – 2

解释

• 逆转从第一个索引开始的长度为2的字符串。结果字符串将变为001101。

• 现在，逆转从第二个索引开始的长度为3的字符串。最终字符串将变为000111。

方法1

这种方法将计算不同相邻元素的总数。然后，我们可以说所需的逆转总数是 count / 2。

通过调试示例输入来理解它。

Input –  str = 00111010

所以，不同相邻元素的总数是4。在此例中，str[1] != str[2]，str[4] != str[5]，str[5] != str[6]，str[6] != str[7]。

所以，计数值为4，答案是count/2，等于2。

步骤

• 步骤1 - 用0初始化变量‘cnt’。

• 步骤2 - 使用for循环，遍历字符串。

• 步骤3 - 在for循环中，如果当前元素不等于前一个元素，则将变量‘cnt’的值增加1。

• 步骤4 - 如果‘cnt’的值是奇数，则返回(cnt -1) /2。否则，返回cnt/2。

示例

#include <bits/stdc++.h>
using namespace std;
//  function to find the minimum number of reversals required to segregate 1s and 0s in a separate half
int minimumReversal(string str, int len){
   int cnt = 0; // initialize count with zero
   for (int i = 1; i < len; i++){

      // if the adjacent elements are not the same, then the increment count
      if (str[i] != str[i - 1]){
         cnt++;
      }
   }

   // For odd count
   if (cnt % 2 == 1){
      return (cnt - 1) / 2;
   }
   return cnt / 2; // For even count
}
int main(){
   string str = "00111010";
   int len = str.size();
   cout << "Minimum number of operations required is : " << minimumReversal(str, len);
   return 0;
}

输出

Minimum number of operations required is : 2

时间复杂度 – O(N)，因为我们遍历字符串。

空间复杂度 – O(N)，因为我们使用固定空间来存储计数。

在这里，我们使用的逻辑是，当我们发现两个不同的相邻元素时，我们需要进行反转。在单次反转中，我们可以设置两个元素，所以我们将返回count/2作为结果值。