数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究使用 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
更新于: 31-Oct-2019
145 次观看
广告