使用C ++求和到二进制字符串S所需的最小操作数。

2024-05-15 01:47:04 383

问题陈述

给定一个二进制字符串str。查找创建由str表示的数字所需执行的最少操作数。仅可以执行以下操作-

加2^x

减2^x

如果二进制字符串是“1000”，那么我们只需要执行1操作，即加2³

如果二进制字符串是“101”，那么我们必须执行2个操作，即加2²+2⁰

示例

#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

使用C ++求和到二进制字符串S所需的最小操作数。

问题陈述

示例

热门推荐

随机推荐