在C ++中从二进制字符串中删除子字符串010的最少步骤
问题陈述
给定一个二进制字符串，任务是计算从该二进制字符串中删除子字符串010的最少步骤
示例
如果输入字符串是010010，则需要2个步骤
将第一个0转换为1。现在字符串变为110010
将最后一个0转换为1。现在最后一个字符串变为110011
算法
1. Iterate the string from index 0 sto n-2 2. If in binary string has consecutive three characters ‘0’, ‘1’, ‘0’ then any one character can be changed Increase the loop counter by 2
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSteps(string str) {
int cnt = 0;
for (int i = 0; i < str.length() - 2; ++i) {
if (str[i] == '0' && str[i + 1] == '1' && str[i+ 2] == '0') {
++cnt;
i += 2;
}
}
return cnt;
}
int main() {
string str = "010010";
cout << "Minimum required steps = " << getMinSteps(str)
<< endl;
return 0;
}当您编译并执行上述程序时。它产生以下输出
输出结果
Minimum required steps = 2