C++ 最小化移除二进制字符串中的0子串，以移除所有0

在这个问题中，我们需要从给定的二进制字符串中移除所有的0。同时，我们需要一次性移除一对连续的0，并计算总共移除的0对数。

我们可以通过计算给定字符串中连续0对的数量来解决这个问题。在本教程中，我们将学习两种不同的解决方案来解决这个问题。

问题描述 − 我们给定了长度为N的循环二进制字符串str。我们需要找到将字符串中所有0移除所需的最小连续0的数量。

示例样例

Input –  str = "0011001"

Output – 2

解释

我们可以一起删除 str[0] 和 str[1]。之后，我们可以删除 str[4] 和 str[5]。所以，我们需要删除2对连续的零。

Input –  str = ‘0000000’

Output – 1

说明

我们可以一次性删除所有的零。

Input –  str = ‘00110010’

Output – 2

解释

由于二进制串是循环的，我们可以一起删除str[0]、str[1]和str[7]。接下来，我们可以一起删除str[5]和str[6]。

方法1

在这个方法中，我们将找出给定字符串中连续出现的零的总对数，这将回答给定的问题。

步骤

• 步骤1 - 将变量’cnt’初始化为0。

• 步骤2 - 将变量’isOne’初始化为false，以跟踪给定字符串中的1。

• 步骤3 - 使用循环遍历字符串。在循环中，如果当前字符是’0’，则将’cnt’的值增加1。

• 步骤4 - 使用while循环进行迭代，直到我们发现’0’作为下一个字符并将’I’的值增加1。

• 步骤5 - 如果当前字符是’1’，则将’isOne’变量的值改为true，表示字符串至少包含一个’1’。

• 步骤6 - 一旦循环迭代完成，如果’isOne’的值为false，则表示字符串只包含零。在这种情况下，返回1。

• 步骤7 - 如果第一个和最后一个字符是’0’，将’cnt’的值减1，因为字符串是循环的。

• 步骤8 - 返回’cnt’的值。

示例

#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.  

复杂度 − O(1)

方法2

在这个方法中，我们将计算移除所有零所需的最小子字符串零的数量，通过计算不同相邻元素之间的变化。

步骤

• 步骤1 − 定义变量’cnt’和’isOne’，并分别初始化为0和false。

• 步骤2 − 使用for循环进行N-1次迭代，其中N是字符串的长度。

• 步骤3 − 在循环中，检查当前字符是否为’0’，下一个字符是否为’1’，如果是，则将’cnt’的值增加1。否则，将’isOne’变量的值改为true。

• 步骤4 − 如果最后一个字符是’0’，第一个字符是’1’，则将’cnt’的值增加1。

• 步骤5 − 如果’isOne’的值为false，则返回1。

• 步骤6 − 返回’cnt’变量的值。

示例

#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

结论

我们看到了两种不同的解决方案来解决给定的问题。在第一种方法中，我们计算出连续零对的总数，在第二种方法中，我们计算出不匹配的相邻字符的总数。