最小化翻轉次數，使得字串中不存在連續的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.

• 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 <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;
}

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.

結論

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

以上是最小化翻轉次數，使得字串中不存在連續的0對的詳細內容。更多資訊請關注PHP中文網其他相關文章！