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

2023年 9月 23日 87.5k 0

将所有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

登录后复制

说明

在给定的字符串中,所有零都已放置在 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

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论