將以下內容翻譯為中文：最小化刪除0子字串以從循環二進位字串中刪除所有0的出現

在這個問題中，我們需要從給定的二進位字串中移除所有的零。同時，我們需要一次移除連續的一對零，並計算移除的零對的總數。

We can solve the problem by counting the number of pairs of consecutive zeros in the given string. In this tutorial, we will learn two different solutions to solve the problem.

問題陳述 − 我們給了一個長度為N的循環二進位字串str。我們需要找到從字串中移除所有零所需的最小連續零的數量。

範例範例

Input –  str = "0011001"

Output – 2

Explanation

我們可以一起刪除str[0]和str[1]。之後，我們可以刪除str[4]和str[5]。所以，我們要刪除2對連續的零。

Input –  str = ‘0000000’

Output – 1

Explanation

我們可以一次刪除所有的零。

Input –  str = ‘00110010’

Output – 2

Explanation

We can remove str[0], str[1], and str[7] together as the binary string is circular. Next, we can remove str[5] and str[6] together.

Approach 1

在這種方法中，我們將找到給定字串中連續零對的總數，這將回答給定的問題。

Algorithm

• 步驟 1 - 將'cnt'變數初始化為零。

• 第二步 - 將'isOne'變數初始化為false值，以追蹤給定字串中的數字1。

• 步驟 3 - 使用循環迭代字串。在循環中，如果當前字元是 '0'，則將 'cnt' 的值增加 1。

• 步驟 4 − 使用 while 迴圈進行迭代，直到我們繼續找到下一個字元為 '0'，並將 'I' 的值增加 1。

• 第五步 - 如果目前字元是'1'，將'isOne'變數的值改為true，表示字串中至少包含一個'1'。

• Step 6 − Once the iteration of the loop completes, If the value of 'isOne' is false, it means the string contains only zeros. Return 1 in such cases.

• Step 7 − If the first and last characters are ‘0’, decrease the value of the ‘cnt’ by 1 as the string is circular.

• Step 8 − Return the value of ‘cnt’.

Example

的中文翻譯為：

範例

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   bool isOne = false;
   
   // Iterate over the string
   for (int i = 0; i < N; i++){
   
      // If the current character is 0, increment the count of 0s
      if (str[i] == '0'){
         cnt++;
         
         // traverse the string until a 1 is found
         while (str[i] == '0'){
            i++;
         }
      }
      else{
      
         // If the current character is 1, then set isOne as true
         isOne = true;
      }
   }
   
   // If string contains only 0s, then return 1.
   if (!isOne)
      return 1;
      
   // If the first and last character is 0, then decrement the count, as the string is circular.
   if (str[0] == '0' && str[N - 1] == '0'){
      cnt--;
   }
   
   // return cnt
   return cnt;
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

輸出

The total number of minimum substrings of consecutive zeros required to remove is - 2<font face="sans-serif"><span style="font-size: 16px; background-color: rgb(255, 255, 255);">.</span></font></p><p>

空間複雜度 - O(1)

方法二

在這個方法中，我們將透過計算相鄰元素的不同來計算所需的最小刪除零子字串數量，以便刪除所有零。

Algorithm

• Step 1 − Define the ‘cnt’ and ‘isOne’ variables, and initialize with 0 and false, respectively.

• #Step 2 − Use for loop to make N-1 iterations, where N is the length of the string.

• Step 3 − In the loop, check if the current character is '0,' and the next character is '1', increase the value of 'cnt' by 1. Otherwise, change the value of the 'isOne' variable to true.

• #第4步 - 如果最後一個字元是'0'，並且第一個字元是'1'，則將'cnt'的值增加1。

• 步驟 5 - 如果 'isOne' 的值為 false，則傳回 1。

• 第6步 - 傳回‘cnt’變數的值。

Example

的中文翻譯為：

範例

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   
   // to check if there is at least one 1
   bool isOne = false;
   
   // traverse the string
   for (int i = 0; i < N - 1; i++) {
   
      // if the current character is 0, the next is 1, then increment count by 1
      if (str[i] == '0' && str[i + 1] == '1'){
         cnt++;
      }
      else{
      
         // if the current character is 1, then set isOne to true
         isOne = true;
      }
   }
   
   // for circular string, if the last character is 0 and the first is 1, then increment count by 1
   if (str[N - 1] == '0' && str[0] == '1'){
      cnt++;
   }
   
   // if there is no 1 in the string, then return 1
   if (!isOne){
      return 1;
   }
   return cnt; // return cnt
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

輸出

The total number of minimum substrings of consecutive zeros required to remove is - 2

結論

我們已經看到了兩種不同的解決方案來解決給定的問題。在第一種方法中，我們計算連續的零對的總數，在第二種方法中，我們計算不匹配的相鄰字元的總數。

以上是將以下內容翻譯為中文：最小化刪除0子字串以從循環二進位字串中刪除所有0的出現的詳細內容。更多資訊請關注PHP中文網其他相關文章！