最小翻转以使C ++中的左侧全为1，右侧全为0

  • Z时代
  • 2024-01-10
  • 分类：综合

问题陈述

给定一个二进制字符串，我们可以在其中将所有1翻转到左边，将所有0翻转到右边。任务是计算使左侧的所有1和右侧的全部0所需的最小翻转

示例

给定的二进制字符串为0010101。在此字符串中，有3个1位和4个0位。我们必须翻转突出显示的4位，以使所有1都在左侧，而所有0都在右侧，如下所示-

0010101

翻转字符串后将变为-

1110000

算法

  • 从左到右遍历字符串，并计算将所有0转换为1所需的翻转次数。

  • 从右到左遍历字符串，并计算将所有1转换为0所需的翻转次数

  • 遍历位之间的所有位置并找到（0的翻转+ 1的翻转）的最小值

示例

#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
   int n = binaryString.length();
   int flipCnt, zeroFlips[n], oneFlips[n];
   flipCnt = 0;
   for (int i = 0; i < n; ++i) {
      if (binaryString[i] == '0') {
         ++flipCnt;
      }
      zeroFlips[i] = flipCnt;
   }
   flipCnt = 0;
   for (int i = n - 1; i >= 0; --i) {
      if (binaryString[i] == '1') {
         ++flipCnt;
      }
      oneFlips[i] = flipCnt;
   }
   int minFlips = INT_MAX;
   for (int i = 1; i < n; ++i) {
      int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
         minFlips = sum;
      }
   }
   return minFlips;
}
int main() {
   string binaryString = "0010101";
   cout << "Minimum flips: " << minFlips(binaryString) <<
   endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它产生以下输出-

Minimum flips: 4

以上是 最小翻转以使C ++中的左侧全为1，右侧全为0 的全部内容， 来源链接： utcz.com/z/354278.html

回到顶部