使用C ++求和到二进制字符串S所需的最小操作数。
问题陈述
给定一个二进制字符串str。查找创建由str表示的数字所需执行的最少操作数。仅可以执行以下操作-
加2x
减2x
如果二进制字符串是“1000”,那么我们只需要执行1操作,即加23
如果二进制字符串是“101”,那么我们必须执行2个操作,即加22+20
示例
#include <iostream> #include <string> #include <algorithm> using namespace std; int getMinOperations(string s){ reverse(s.begin(), s.end()); int n = s.length(); int result[n + 1][2]; if (s[0] == '0') { result[0][0] = 0; } else { result[0][0] = 1; } result[0][1] = 1; for (int i = 1; i < n; ++i) { if (s[i] == '0') { result[i][0] = result[i - 1][0]; result[i][1] = 1 + min(result[i - 1][1], result[i - 1][0]); } else { result[i][1] = result[i - 1][1]; result[i][0] = 1 + min(result[i - 1][0], result[i - 1][1]); } } return result[n - 1][0]; } int main(){ string str = "101"; cout << "Minimum required operations = " << getMinOperations(str) << endl; return 0; }
输出结果
当您编译并执行上述程序时。它产生以下输出-
Minimum required operations = 2