在這個問題中，我們需要透過翻轉第一個二進位字串的前綴來將其轉換為第二個二進位字串。為了獲得最小的前綴翻轉次數，我們需要遍歷字串的末尾，如果在兩個字串中找到不匹配的字符，我們需要翻轉第一個字串的前綴。
問題陳述 − 我們給了兩個不同的二進位字串，分別稱為first和second。兩個二進位字串的長度相等，為N。我們需要透過翻轉第一個字串的前綴將其轉換為第二個字串。在這裡，我們需要計算將字串轉換為另一個字串所需的總前綴翻轉次數。翻轉意味著將‘0’轉換為‘1’，將‘1’轉換為‘0’。
Input – first = "001", second = "000"
Output – 2
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
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
由於兩個字串相等，我們不需要進行任何翻轉。
在這種方法中，我們從字串的最後開始迭代，如果找到不匹配的字符，我們會翻轉長度為‘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' 變數的值。
#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
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 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’
#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
以上是將二進位字串轉換為另一個所需的最小前綴翻轉次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
