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

Here, we require to manipulate the binary string so that it doesn’t contain any consecutive zeros. If we find consecutive zeros, we need to change any zero to 1. So, we require to count the total number of 0 to 1 conversion we should make to remove all consecutive zeros from the string.

问题陈述 − 我们给定一个只包含0和1的二进制字符串‘str’。我们需要找到所需的最小翻转次数，以便结果字符串不包含连续的零。

示例示例

Input –  0101001

Output – 1

Explanation

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

Input –  str = 00100000100

Output – 4

Explanation

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

Input –  0101010101

Output – 0

Explanation

我们不需要进行任何翻转，因为字符串中没有连续的零。

方法一

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

算法

• Step 1 − Initialize the ‘cnt’ variable with zero, storing a total number of flips.

  

  a0.dev

  专为移动端应用开发设计的AI编程平台

  下载

• Step 2 − Iterate through the binary string using the loop.

• Step 3 − If the character at index ‘I’ and index ‘I +1’ is 0, flip the next character, and increase the value of the ‘cnt’ variable by 1.

• 步骤 4 - 当 for 循环的迭代完成时，返回 'cnt' 的值。

Example

#include 
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;
}

Output

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

Time complexity − O(N), as we iterate through the binary string.

Space complexity − O(1), as we use constant space to store total counts.

结论

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