C++ 将一个二进制字符串转换为另一个所需的最小前缀翻转次数

在这个问题中，我们需要通过翻转第一个字符串的前缀来将其转换为第二个二进制字符串。为了获得最小的前缀翻转次数，我们需要从字符串的末尾开始迭代，如果在两个字符串中找到了不匹配的字符，我们需要翻转第一个字符串的前缀。

问题描述 - 我们给定了两个不同的二进制字符串，称为第一个字符串和第二个字符串。这两个二进制字符串的长度都是相等的，为N。我们需要通过翻转第一个字符串的前缀来将其转换为第二个字符串。在这里，我们需要计算将一个字符串转换为另一个字符串所需的总前缀翻转次数。翻转意味着将’0’转换为’1’，将’1’转换为’0’。

示例

Input –  first = "001", second = "000"

Output – 2

说明

• 首先，我们需要将第一个字符串的长度为3的前缀翻转，得到的字符串将是110。

• 之后，我们需要将长度为2的前缀翻转，得到的字符串将是000，与第二个字符串相等。

Input –  first = "10", second = "01"

Output – 1

解释

我们需要翻转长度为2的前缀，其结果字符串为’01’，与第二个字符串相等。

Input –  first = "11", second = "11"

Output – 0

解释

由于两个字符串相等，我们不需要翻转字符。

方法1

在这种方法中，我们从字符串的最后一个字符开始遍历，如果找到不匹配的字符，我们翻转长度为’I+1’的前缀中的所有字符。这是解决问题的一种朴素方法。

步骤

• 步骤1 - 定义变量’cnt’并将其初始化为0。

• 步骤2 - 使用循环从末尾开始遍历字符串。

• 步骤3 - 如果first[i]和second[i]不相等，我们需要翻转长度为I + 1的前缀的所有字符。

• 步骤4 - 使用嵌套的for循环遍历长度为I + 1的前缀，并通过执行flipBits()函数翻转每个字符。

• 步骤4.1 - 如果flipBits()函数中的当前字符为’1’，则返回’0’，如果当前字符为’0’，则返回’1’。

• 步骤5 - 当我们翻转前缀时，增加’cnt’变量的值1。

• 步骤6 - 返回’cnt’变量的值。

示例

#include <bits/stdc++.h>
using namespace std;
char flipBits(char ch){
   // if the bit is '0', flip it to '1', else flip it to '0'.
   return (ch == '0') ? '1' : '0';
}
int minimumFlips(string first, string second, int n){
   // to store the count of flips
   int cnt = 0;

   // Traverse the string
   for (int i = n - 1; i >= 0; i--){

      // If first[i] is not equal to second[i]
      if (first[i] != second[i]){

         // flip the bits
         for (int j = 0; j <= i; j++){
            first[j] = flipBits(first[j]);
         }
         cnt++;
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

输出

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

方法2

在这种方法中，我们将使用’inverted’变量来跟踪当前位是否翻转，而不是每次都翻转前缀位。在这种方法中，我们还优化了代码的时间复杂性。

步骤

• 步骤1 - 定义变量’cnt’并将其初始化为0。还要定义变量’inverted’并将其初始化为false的值。

• 步骤2 - 从末尾开始遍历字符串。如果第一个[i]和第二个[i]字符不匹配，请按照以下步骤进行。

• 步骤2.1 - 如果’inverted’的值为false，则将’cnt’变量的值增加1，并将’inverted’变量的值更改为true。

• 步骤3 - 如果两个字符匹配，并且’inverted’的值为true，则我们需要再次翻转位。所以，将’cnt’的值增加1，并将’inverted’的值更改为false。

示例

让我们通过以下示例来调试上述算法。

Input – first = ‘001’, second = ‘000’

• 在第一步中，第一个和第二个不匹配，并且’inverted’的值为false。所以，’cnt’的值将变为1，而’inverted’将变为true。在这里，通过将’inverted’的值改为true，我们假设我们已经虚拟地翻转了前缀。

• 然后，第一个和第二个匹配，但’inverted’的值为true。所以，’cnt’的值将变为2，而’inverted’为false。

• 接下来，第一个和第二个匹配，而且’inverted’的值为false。所以，我们不需要执行任何操作。

• 最后，返回’cnt’的值，即2。

#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of flips of prefixes required to convert the first binary string to the second
int minimumFlips(string first, string second, int N){

   // number of flips
   int cnt = 0;

   // to track whether the current bit is already flipped.
   // When we flip a bit 2 times, it becomes the same as the original bit.
   bool inverted = false;

   // Traverse the given string
   for (int i = N - 1; i >= 0; i--){

      // If A[i] is not equal to B[i]
      if (first[i] != second[i]){

         // If the current bit is not already flipped
         if (!inverted){
            cnt++; // Increase the count of flips
            inverted = true; // Invert all prefix bits
         }
      }
      else{

         // If A[i] is equal to B[i], but a current bit is flipped, we need to flip it again
         if (inverted){

            // Increase the count of flips
            cnt++;

            // Update inverted to false
            inverted = false;
         }
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

输出

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

结论

我们学到了两种找到将一个字符串转换为另一个字符串的最小前缀翻转次数的方法。逻辑是从字符串的末尾遍历，并在找到不匹配的字符时翻转前缀。

我们优化了第二段代码的时间复杂性，因为我们使用’inverted’变量来跟踪翻转前缀，而不是像第一种方法中那样翻转前缀。