数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学最小化移除0子串以从循环二进制字符串中移除所有0
在这个问题中，我们需要从给定的二进制字符串中移除所有零。此外，我们需要一次移除一对连续的零，并计算移除的零对的总数。
我们可以通过计算给定字符串中连续零对的数量来解决这个问题。在本教程中，我们将学习两种不同的解决方案来解决这个问题。
问题陈述 − 我们给定长度为N的循环二进制字符串str。我们需要找到移除字符串中所有零所需的最小连续零数。
示例
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’变量初始化为零。
步骤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
结论
我们已经看到了给定问题的两种不同的解决方案。在第一种方法中，我们计算连续零对的总数；在第二种方法中，我们计算不相邻相邻字符的总数。
83 次浏览
