二进制字符串中将所有 0 放在 1 前面所需的最小移除次数

---

问题陈述

我们给定一个二进制字符串 str，我们需要从字符串中移除最少的字符，以便我们可以将所有零放在 1 之前。

示例

输入

str = ‘00110100111’

输出

3

解释

这里，我们可以通过两种方式实现输出 3。

我们可以从字符串中移除 arr[2]、arr[3] 和 arr[5]，或者移除 arr[4]、arr[6] 和 arr[7]。

输入

str = ‘001101011’

输出

2

解释

我们可以移除 arr[4] 和 arr[6] 以将所有零放在 1 之前。

输入

str = ‘000111’

输出

0

解释

在给定的 str 中，所有零都已放在 1 之前，因此我们不需要从给定的字符串中移除任何字符。

方法 1

在第一种方法中，我们将使用两个数组。第一个数组在左侧存储所有 1，另一个数组在右侧存储所有 0。之后，我们可以在两个数组的第 i 个索引处添加元素并找到最小和。

算法

• 步骤 1 - 定义名为 ‘zeros’ 和 ‘ones’ 的长度为 n 的列表，其中 n 是字符串的长度，我们可以使用 size() 方法获取。

• 步骤 2 - 如果给定字符串中的第一个字符是 ‘1’，则在 ‘ones’ 数组的第 0 个索引处存储 1；否则，存储 0。

• 步骤 3 - 使用 for 循环遍历字符串的第二个元素。在 for 循环中，使用我们根据字符串在第 i 个索引处的字符获得的结果值初始化 ones[i]。

• 步骤 4 - 根据给定字符串中的最后一个字符，在 zeros[n-1] 中存储 1 或 0。

• 步骤 5 - 使用 for 循环从最后一个第二个字符遍历字符串，并根据字符串字符更新 zeros 列表的值。

• 步骤 6 - 定义 ‘min_zeros_to_remove’ 变量并将其初始化为最大整数值。

• 步骤 7 - 现在，遍历 ‘zeros’ 和 ‘ones’ 列表。从 zeros 列表中访问 ‘i+1’ 索引处的值，从 ‘ones’ 列表中访问 ‘I’ 索引处的值。之后，将两个元素相加。

• 步骤 8 - 如果两个数组元素的和小于 ‘min_zeros_to_remove’ 变量的当前值，则使用该和更改 ‘min_zeros_to_remove’ 的值。

• 步骤 9 - 返回结果值。

示例

#include <bits/stdc++.h>
using namespace std;

int minimumZeroRemoval(string str){
   int n = str.size();
   // arrays to store the prefix sums of zeros and ones
   vector<int> zeros(n);
   vector<int> ones(n);
   // compute total number of 1s at the left of each index
   ones[0] = (str[0] == '1') ? 1 : 0;
   for (int i = 1; i < n; i++) {
      ones[i] = ones[i - 1] + ((str[i] == '1') ? 1 : 0);
   }
   // compute total number of 0s at the right of each index
   zeros[n - 1] = (str[n - 1] == '0') ? 1 : 0;
   for (int i = n - 2; i >= 0; i--){
      zeros[i] = zeros[i + 1] + ((str[i] == '0') ? 1 : 0);
   }
   // do the sum of zeros and ones for each index and return the minimum value
   int min_zeros_to_remove = INT_MAX;
   for (int i = 0; i < n - 1; i++){
      min_zeros_to_remove = min(min_zeros_to_remove, zeros[i + 1] + ones[i]);
   }
   return min_zeros_to_remove;
}
int main() {
   string str = "00110100111";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

输出

The minimum number of zeros required to remove from the given string is - 3

• 时间复杂度 - O(N)，因为我们需要 for 循环遍历大小为 N 的字符串和列表。

• 空间复杂度 - O(N)，因为我们使用两个列表来存储 1 和 0 的计数。

方法 2

此方法是第一种方法的优化版本。在这里，我们使用两个变量来存储 1 和 0 的计数，而不是列表。

算法

• 步骤 1 - 定义 ‘zeros_right’ 变量并将其初始化为 0。

• 步骤 2 - 遍历字符串，计算给定字符串中 ‘0’ 字符的总数，并根据该总数更新 ‘zero_right’ 变量的值。

• 步骤 3 - 定义 ‘ones_left’ 变量并将其初始化为 0。

• 步骤 4 - 使用 for 循环遍历字符串。如果字符串中第 i 个索引处的字符是 ‘1’，则将 ‘ones_left’ 变量的值加 1。否则，将 ‘zeros_right’ 变量的值减 1。

• 步骤 5 - 如果 ‘zeros_right + ones_left’ 小于 ‘res’ 变量的当前值，则更新 ‘res’ 变量的值。

示例

#include <bits/stdc++.h>
using namespace std;

// function to remove zeros from the string to place all zeros before 1.
int minimumZeroRemoval(string str){
   // counting the total number of zeros in the given string
   int zeros_right = 0;
   for (int i = 0; i < str.size(); i++) {
      if (str[i] == '0')
      zeros_right += 1;
   }
   // variable to store the number of ones from left
   int ones_left = 0;
   // Size of the string
   int len = str.size();
   // variable to store the final result
   int result = INT_MAX;
   // Traverse the string from left to right
   for (int i = 0; i < len; i++){
      // If the current character is '1', then increment ones_left by 1 else, decrement zeros_right by 1
      if (str[i] == '1') {
         ones_left += 1;
      } else {
         zeros_right -= 1;
      }
      // Store the minimum result and zeros_right + ones_left in result
      result = min(result, zeros_right + ones_left);
   }
   // Return the final result
   return result;
}
int main() {
   string str = "001101011";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

输出

The minimum number of zeros required to remove from the given string is - 2

• 时间复杂度 - O(N)，因为我们迭代遍历字符串。

• 空间复杂度 - O(1)，因为我们只使用常量空间。

结论

用户学习了两种从给定二进制字符串中移除最少字符的方法。第二种方法的代码更易读，因为我们使用变量来存储零和一的计数，而不是使用列表。