数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究将二进制字符串转换为另一个字符串所需的最小前缀翻转次数
在这个问题中，我们需要通过翻转第一个字符串的前缀将第一个二进制字符串转换为第二个二进制字符串。为了获得最小的前缀翻转次数，我们需要遍历字符串的末尾，如果我们在两个字符串中找到不匹配的字符，我们需要翻转第一个字符串的前缀。
问题陈述 − 我们给出了两个不同的二进制字符串，称为第一个和第二个。两个二进制字符串的长度相等，为 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 − 使用嵌套循环遍历长度等于 I + 1 的前缀，并通过执行 flipBits() 函数翻转其中的每个字符。
步骤 4.1 − 如果当前字符为 '1'，则在 flipBits() 函数中返回 '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 − 从末尾开始遍历字符串。如果 first[i] 和 second[i] 字符不匹配，请执行以下步骤。
步骤 2.1 − 如果 'inverted' 的值为 false，则将 'cnt' 变量的值增加 1，并将 'inverted' 变量的值更改为 true。
步骤 3 − 如果两个字符匹配，并且 'inverted' 的值为 true，我们需要再次翻转该位。因此，将 'cnt' 的值增加 1，并将 'inverted' 的值更改为 false。
示例
让我们通过举例来调试上述算法。
Input – first = ‘001’, second = ‘000’
在第一步中，first[2] 和 second[2] 不匹配，并且 'inverted' 的值为 false。因此，'cnt' 的值将变为 1，'inverted' 将变为 true。在这里，通过将 'inverted' 的值更改为 true，我们假设我们实际上已经翻转了前缀。
之后，first[1] 和 second[1] 匹配，但 'inverted' 的值为 true。因此，'cnt' 的值将变为 2，'inverted' 将变为 false。
接下来，first[0] 和 second[0] 匹配，并且 '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' 来跟踪前缀的翻转，而不是像第一种方法那样翻转前缀。
161 次查看
