最小化翻轉次數，使得字串不包含任何連續的0

---

這裡，我們需要操作二進位制字串，使其不包含任何連續的零。如果我們找到連續的零，我們需要將任何一個零改為1。因此，我們需要計算為了去除字串中所有連續的零而應該進行的0到1轉換的總數。

問題陳述 − 我們給定一個僅包含0和1的二進位制字串“str”。我們需要找到所需的最小翻轉次數，以使生成的字串不包含任何連續的零。

示例

Input –  0101001

Output – 1

解釋

我們只需要翻轉最後一個零。

Input –  str = 00100000100

Output – 4

解釋

我們需要翻轉第2、5、7和11個零以去除所有連續的零對。

Input –  0101010101

Output – 0

解釋

我們不需要進行任何翻轉，因為字串不包含連續的零。

方法1

在這種方法中，我們將從頭到尾迭代字串，如果字串包含任何連續的零，則翻轉字元。最後，我們可以得到從給定的二進位制字串中去除所有連續零所需的最小翻轉總數。

演算法

• 步驟1 − 將“cnt”變數初始化為零，儲存翻轉總數。

• 步驟2 − 使用迴圈遍歷二進位制字串。

• 步驟3 − 如果索引“I”和索引“I + 1”處的字元為0，則翻轉下一個字元，並將“cnt”變數的值增加1。

• 步驟4 − 當for迴圈迭代完成時，返回“cnt”的值。

示例

#include <bits/stdc++.h>
using namespace std;
// Function to get the total number of minimum flips required so the string does not contain any consecutive 0’s
int findCount(string str, int len){

   // initialize the count
   int cnt = 0;
   
   // iterate over the string
   for (int i = 0; i < len - 1; i++){
   
      // If two consecutive characters are the same
      if (str[i] == '0' && str[i + 1] == '0'){
      
         // Flip the next character
         str[i + 1] = '1';
         
         // increment count
         cnt++;           
      }
   }
   return cnt;
}
int main(){
   string str = "00100000100";
   int len = str.length();
   cout << "The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - " << findCount(str, len);
   return 0;
}

輸出

The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - 4

時間複雜度 − O(N)，因為我們遍歷二進位制字串。

空間複雜度 − O(1)，因為我們使用常量空間來儲存總數。

結論

我們學習瞭如何計算從給定的二進位制字串中去除連續零對所需的最小翻轉次數。使用者可以嘗試計算從給定的二進位制字串中去除連續一對一的最小翻轉次數。