C++ 最小化翻转的次数，使得字符串中不存在连续的0

在这里，我们需要操作二进制字符串，使其不包含连续的零。如果我们发现连续的零，就需要将任何一个零改为1。因此，我们需要计算总共需要进行多少次从0到1的转换，以便从字符串中删除所有连续的零。

问题陈述 - 给定一个只包含0和1的二进制字符串’str’，我们需要找出最小的翻转次数，使得结果字符串不包含任何连续的零。

示例

Input –  0101001

Output – 1

解释

我们只需要翻转倒数第二个零。

Input –  str = 00100000100

Output – 4

说明

我们需要翻转第2个、第5个、第7个和第11个零，以消除所有连续的零对。

Input –  0101010101

Output – 0

解释

我们需要执行零次翻转，因为该字符串不包含连续的0。

方法1

在这个方法中，我们将从头到尾遍历字符串，并在包含任何连续的0时翻转字符。最后，我们可以得到从给定二进制字符串中删除所有连续0所需的最小翻转次数。

步骤

• 步骤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)，因为我们使用常量空间来存储总数。

结论

我们学会了计算从给定的二进制字符串中移除连续的零对所需的最小翻转次数。用户可以尝试计算从给定的二进制字符串中移除连续的一对所需的最小翻转次数。