資料結構
網路
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 次觀看
廣告