问题陈述
我们给定了二进制字符串 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
说明
在给定的字符串中，所有零都已放置在 1 之前，因此我们不需要从给定字符串中删除任何字符。
方法 1
在第一种方法中，我们将使用两个数组。第一个数组将所有 1 存储在左侧，另一个数组将所有 0 存储在右侧。之后，我们可以将两个数组中第 i 个索引处的元素相加，并找到最小总和。
算法
第 1 步 – 定义长度为 n 的“零”和“一”命名列表，其中 n 是我们可以使用 size() 方法获取的字符串的长度。
步骤 2 – 如果给定字符串中的第一个字符是“1”，则将 1 存储在“ones”数组的第 0 个索引处；否则，存储 0。
步骤 3 – 使用 for 循环从字符串的第二个元素开始遍历。在 for 循环中，使用根据第 i 个索引处的字符串的字符将 Ones[i-1] 与 1 或 0 相加得到的结果值来初始化 Ones[i]。
第 4 步 – 根据给定字符串中的最后一个字符，将 1 或 0 存储在 Zeros[n-1] 处。
步骤 5 – 使用 for 循环从最后第二个字符开始遍历字符串，并根据字符串字符更新零列表的值。
第 6 步 – 定义“min_zeros_to_remove”变量并使用最大整数值对其进行初始化。
第 7 步 – 现在，遍历“零”和“一”列表。从零列表中的“i+1”索引和“一”列表中的“I”索引访问值。之后，添加这两个元素。
步骤 8 – 如果“min_zeros_to_remove”的值小于“min_zeros_to_remove”变量的当前值，则将其值更改为两个数组元素的总和。
步骤 9 – 返回结果值。
示例
#include using namespace std;int minimumZeroRemoval(string str){ int n = str.size(); // arrays to store the prefix sums of zeros and ones vector zeros(n); vector 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 = 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 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)，因为我们仅使用常量空间。
结论
用户学习了两种从给定二进制字符串中删除最少字符的方法。第二种方法的代码更具可读性，因为我们使用变量来存储零和一的计数，而不是使用列表。
以上就是将所有0放在1之前所需的最小移动次数在二进制字符串中的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445630.html
微信扫一扫 
支付宝扫一扫 
