將二進位字串轉換為另一個所需的最小前綴翻轉次數

在這個問題中，我們需要透過翻轉第一個二進位字串的前綴來將其轉換為第二個二進位字串。為了獲得最小的前綴翻轉次數，我們需要遍歷字串的末尾，如果在兩個字串中找到不匹配的字符，我們需要翻轉第一個字串的前綴。

問題陳述 − 我們給了兩個不同的二進位字串，分別稱為first和second。兩個二進位字串的長度相等，為N。我們需要透過翻轉第一個字串的前綴將其轉換為第二個字串。在這裡，我們需要計算將字串轉換為另一個字串所需的總前綴翻轉次數。翻轉意味著將‘0’轉換為‘1’，將‘1’轉換為‘0’。

Sample Examples

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

Output – 2

Explanation

• First, we need to flip the prefix of length 3 for the first string, and the resultant string will be 110.

• 在此之後，我們需要翻轉長度為2的前綴，結果字串將為000，與第二個字串相等。

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

Output – 1

Explanation

We require to flip the prefix of length 2, and the resultant string will be ‘01’, which is equal to the second string.

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

Output – 0

Explanation

由於兩個字串相等，我們不需要進行任何翻轉。

Approach 1

在這種方法中，我們從字串的最後開始迭代，如果找到不匹配的字符，我們會翻轉長度為‘I 1’的前綴中的所有字符。這是解決問題的簡單方法。

演算法

• 步驟 1 - 定義變數 'cnt' 並將其初始化為 0。

• Step 2 − Start traversing the string from the end using the loop.

• Step 3 − If first[i] and second[i] are not equal, we need to flip all the characters of the prefix whose length is equal to the I 1.

• Step 4 − Use the nest for loop to iterate through the prefix of length equal to I 1, and flip each character of it by executing the flipBits() function.

• Step 4.1 − We return '0' if the current character is '1' and '1' if the current character is '0' in the flipBits() function.

• Step 5 − Increase the value of the ‘cnt’ variable by 1 when we flip the prefix.

• 步驟 6 - 傳回 'cnt' 變數的值。

Example

#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;
}

Output

#

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

Approach 2

In this approach, we will use the 'inverted' variable to track whether the current bit is flipped or not, rather than flipping each prefix bit every time. We also optimized the time complexity of the app

#演算法

• Step 1 − Define the 'cnt' variable and initialize it with '0'. Also, define the 'inverted' variable and initialize it with a false value.

• #步驟 2

  - 從最後開始遍歷字串。如果第一個[i]和第二個[i]字元不匹配，請按照下列步驟操作。
Step 2.1

− If the value of the 'inverted' is false, increase the value of the 'cnt' variable by 1, and change the value of the 'inverted' variable to true .

Step 3

− If both characters match, and the value of the 'inverted' is true, we need to flip the bit again. So, increase the value of 'cnt' by 1 , and change the value of 'inverted' to false.

### ###Example### ###Let’s debug the above algorithm by taking the example.###

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

### ######在第一步中，第一個[2]和第二個[2]不匹配，'inverted'的值為false。因此，'cnt'的值將變為1，'inverted'將變為true。在這裡，透過將'inverted'的值更改為true，我們假設我們已經虛擬地翻轉了前綴。 ###### ######After that, the first[1] and second[1] match, but the value of the 'inverted' is true. So, the 'cnt' value will become 2, and the 'inverted' is false .###### ######Next, the first[0] and second[0] match, and the value of ‘inverted’ is false. So, we don’t need to perform any operation.####### ######最後，它傳回值為‘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;
}

###Output####

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

###Conclusion### ###我們學習了兩種方法來找到將一個字串轉換為另一個字串所需的最小前綴翻轉次數。邏輯是從末尾遍歷字串，如果我們發現不匹配的字符，則翻轉前綴。 ### ###我們在時間複雜度方面優化了第二段程式碼，透過使用「inverted」變數來追蹤翻轉前綴，而不是像第一種方法那樣翻轉前綴。 ###

以上是將二進位字串轉換為另一個所需的最小前綴翻轉次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！