C++ 最小化后缀翻转以使二进制字符串非递减

在这个问题中，我们将计算将二进制字符串的字符翻转以使其按非递减顺序转换所需的最小操作次数。

如果第p个索引处的字符为0且与前一个索引处的字符不匹配，则我们可以翻转从第p个索引开始的子字符串的所有字符，并计算最少的翻转次数。

问题描述 – 给定一个二进制字符串alpha，我们需要计算将该二进制字符串转换为递增顺序所需的最小翻转次数。在一个翻转中，我们可以选择任何索引p，并翻转从第p个索引开始的子字符串。

示例

输入：

alpha = "11000110"

输出结果

3

说明

• 我们可以在第一次移动中翻转从第2个索引开始的子字符串。所以，结果字符串将变为11111001。

• 在第二次移动中，选择从第5个索引开始的字符串，并将其翻转。所以，字符串变为11111110。

• 翻转最后一个字符，使字符串等于1111111。

所以，我们需要总共进行3次翻转，将字符串转换为递增顺序。

输入

alpha = "0011"

输出

0

解释 – 该字符串已经按递增顺序排列。

输入

alpha = "1100";

输出

1

解释 – 我们可以翻转从第2个位置开始的子字符串，得到1111字符串。

方法1

在这个方法中，我们将遍历字符串，当我们发现当前字符是’0’并且与前一个字符不匹配时，我们将翻转从当前索引右边的所有字符。

算法

步骤1 - 将’cnt’初始化为0，用于存储所需的最小翻转次数。

步骤2 - 如果索引p和p-1处的字符不相同，并且索引’p’处的字符是’0’，则执行以下步骤。

步骤3 - 从第p个索引开始遍历字符串。

步骤4 - 如果第q个索引处的字符是’0’，将其替换为’1’。否则，将其替换为’0’。

步骤5 - 将cnt值增加1。

步骤6 - 最后，返回’cnt’的值。

示例

#include <bits/stdc++.h>
using namespace std;

int GetOperations(string alpha) {
   // For storing the count of operations
   int cnt = 0;
   for (int p = 1; p < alpha.length(); p++) {
     // For different adjacent characters
     if (alpha[p] != alpha[p - 1]) {
       if (alpha[p] == '0') {
         //   Flipping all bits of a substring starting from index p
         for (int q = p; q < alpha.length(); q++) {
            if (alpha[q] == '0') {
              alpha[q] = '1';
            } else {
              alpha[q] = '0';
            }
         }
         cnt++;
       }
     }
   }
   // return answer
   return cnt;
}
int main() {
   string alpha = "11000110";
   cout << "The minimum operations required to convert the string into the increasing order is " << GetOperations(alpha);
   return 0;
}

输出

The minimum operations required to convert the string into the increasing order is 3

时间复杂度 – O(N*N)用于遍历和翻转字符串字符。

空间复杂度 – O(1)，因为我们不使用任何额外的空间。

方法2

在这种方法中，我们将使用布尔变量来跟踪字符串字符是否被翻转，而不是直接翻转它们。

算法

步骤1 - 将’cnt’和’isFlipped’初始化为’0’。

步骤2 - 开始遍历字符串。如果p和p-1索引处的字符不匹配，请按照以下步骤操作。

步骤3 - 如果isFlipped等于0，并且alpha[p]也是’0’，将isFlipped更改为1，并将’cnt’增加1。

步骤4 - 如果isFlipped为1，将’cnt’增加1。

步骤5 - 从函数中返回’cnt’。

示例

#include <bits/stdc++.h>
using namespace std;

int GetOperations(string alpha) {
   // For storing the count of operations
   int cnt = 0;
   // To keep track of the flip
   bool isFlipped = 0;
   for (int p = 1; p < alpha.length(); p++) {
     // For different adjacent characters
     if (alpha[p] != alpha[p - 1]) {
       // alpha[p] is '0' and its not equal to alpha[p-1]. So, the string is in decreasing order.
       if (isFlipped == 0 && alpha[p] == '0') {
         isFlipped = 1;
         cnt++;
       }
       // When a string is in increasing order, but the string is flipped
       else if (isFlipped == 1) {
         cnt++;
       }
     }
   }
   // return answer
   return cnt;
}
int main() {
   string alpha = "11000";
   cout << "The minimum operations required to convert the string into the increasing order is " << GetOperations(alpha);
   return 0;
}

输出

The minimum operations required to convert the string into the increasing order is 1

时间复杂度 – O(N) 来遍历字符串。

空间复杂度 – O(1)

我们使用第二种方法中的布尔变量跟踪几乎翻转的字符。所以，如果我们发现字符串不是按升序排列的，就不需要翻转所有的正确字符，从而节省了成本。