用 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

更新于：2019 年 12 月 23 日

105 次浏览

开启你的 职业生涯

完成课程以获得认证

开始
广告