將二進位制字串中的 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。

示例

#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 作為結果值。