将二进制字符串中的 1 和 0 分隔到两个不同的半部分

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

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

示例

Input –  str = 0011

Output – 0

解释

因为字符串已经分成了两半，所以不需要反转。

Input –  str = 0011101000

Output – 2

解释

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

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

Input –  str = 010101

Output – 2

解释

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

  • 现在，反转从第 2 个索引开始的长度为 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]。

因此，count 值为 4，答案为 count/2，等于 2。

算法

  • 步骤 1 - 将变量 'cnt' 初始化为 0。

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

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

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

示例

Open Compiler
#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 作为结果值。

更新于: 2023-07-28

238 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告