数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究通过翻转除任何一个1位之外的所有位，将给定的二进制字符串转换为另一个字符串，所需操作次数最少
在这个问题中，我们需要通过翻转字符串的字符来将一个二进制字符串转换为另一个二进制字符串。我们可以保留任何一位1，并翻转其他位，我们需要计算达到另一个字符串所需的总操作次数。
我们可以根据给定字符串中“01”和“10”对的总数来解决这个问题。
问题陈述 - 我们得到了两个长度相同的字符串str1和str2，它们包含“0”和“1”字符，表示二进制字符串。我们需要通过执行以下操作将字符串str1转换为str2。
我们可以选择任何一位1，并翻转所有其他位。翻转位意味着将“0”转换为“1”，将“1”转换为“0”。
如果无法将str1转换为str2，则打印-1。
示例
输入
str1 = "001001111", str2 = "011111000";
输出
3
解释 -
在第一次操作中，我们将第2位索引的“1”保留原样，并翻转str1中的所有其他字符。因此，str1将是111110000。
在第二次操作中，我们将第0位索引的“1”保留原样，并翻转所有其他字符。因此，str1将是100001111。
在最后一次操作中，我们将第5位索引的“1”保留原样。因此，str1将变为011111000。
输入
str1 = "0000", str2 = "1111";
输出
-1
解释 - 无法将str1转换为str2，因为str1不包含任何需要保留的“1”字符。
输入
str1 = "0111", str2 = "1000";
输出
-1
解释 - 无法将str1转换为str2。
方法1
我们可以通过观察来解决这个问题。观察结果是，当我们保留任何单个设定的位并执行2次操作时，我们可以得到相同的字符串。因此，我们需要选择1的不同索引来更改字符串。
此外，我们需要执行2次操作才能将01对转换为10。例如，保留“01”中的“1”。因此，我们得到“11”。之后，在“11”中保留第0位索引的“1”，所以我们将得到“10”。
为了得到答案，“01”（0 -> str1，1 -> str2）和“10”（1 -> str1，0 -> str2）对应该相同。否则，我们可以说答案不存在。
我们的主要目标是最小化“01”和“10”对，因为我们可以用2次操作将“01”转换为“10”。
算法
步骤1 - 定义totalOperatrions()函数来计算将str1转换为str2所需的运算次数。
步骤1.2 - 初始化count10和count01变量来存储字符串中的“01”和“10”对。
步骤1.3 - 遍历字符串并计算两个字符串中的01和10对。
步骤1.4 - 如果count10和count01相同，则返回2*count10。否则返回-1。
步骤2 - 定义minimumOperations()函数来计算将str1转换为str2所需的最小运算次数。
步骤3 - 将“ans”初始化为最大值。
步骤4 - 使用原始字符串调用totalOperations()函数，并将结果存储在“operation1”变量中。如果返回值不等于-1，则从ans和operation1中将最小值存储在ans中。
步骤5 - 现在，我们将修改字符串以最小化01和10的对。因此，定义字符串修改函数stringModification()。
步骤5.1 - 在函数中，我们找到字符串中的第一个“1ch”对，“ch”作为参数传递，可以是“0”或“1”。因此，对应该类似于1 -> str1和ch -> str。
步骤5.2 - 如果找不到“1ch”对，则返回false。
步骤5.3 - 如果找到“1ch”对，则保留对的原样并翻转str1的其他字符。
步骤6 - 执行stringModification函数以保留“11”对并翻转其他字符。之后，再次调用totalOperations()函数以查找将str1转换为str2所需的运算。
步骤7 - 如果operation2不等于-1，则从“ans”或“1 + operation2”中将最小值存储在“ans”中。在这里，我们添加了1，因为我们已经使用一次操作修改了字符串。
步骤8 - 通过保留第一个“10”对并计算运算来修改字符串。再次将最小值赋给“ans”。
步骤9 - 如果“ans”等于INT_MAX，则返回-1。否则，返回ans。
示例
#include <bits/stdc++.h>
using namespace std;
// counting 01 and 10 pairs
int totalOperations(string str1, string str2) {
int len = str1.size();
int count10 = 0, count01 = 0;
for (int p = 0; p < len; p++) {
// If characters at p index are not same
if (str1[p] != str2[p]) {
// Increase count01 if 0(str1)-1(str2), else count10 if 1(str1)-0(str2)
if (str1[p] == '0')
count01++;
else
count10++;
}
}
// If we have euqal number of 01 and 10 pairs, we need 2 operations to flip one pair.
if (count01 == count10)
return 2 * count01;
return -1;
}
bool StringModification(string &temp1, string &temp2, char ch) {
int len = temp1.size();
int index = -1;
// Find the pair of 1c character. (1 -> temp1, c -> temp2)
for (int p = 0; p < len; p++) {
if (temp1[p] == '1' && temp2[p] == ch) {
index = p;
break;
}
}
// return 0 if pair is not found
if (index == -1)
return false;
// Flip other characters in both strings
for (int p = 0; p < len; p++) {
if (p != index) {
if (temp1[p] == '1')
temp1[p] = '0';
else
temp1[p] = '1';
}
}
return true;
}
// finding minimum operations
int minimumOperations(string str1, string str2) {
int ans = INT_MAX;
// first case with initial strings
int operation1 = totalOperations(str1, str2);
if (operation1 != -1)
ans = min(ans, operation1);
string temp1 = str1, temp2 = str2;
// Case 2, modification for 11 pair
if (StringModification(temp1, temp2, '1')) {
// get operations after modification
int operation2 = totalOperations(temp1, temp2);
// adding 1 to operation2 as we have done one modification initially
if (operation2 != -1)
ans = min(ans, 1 + operation2);
}
// Case 3 modification for 10 pair
temp1 = str1, temp2 = str2;
if (StringModification(temp1, temp2, '0')) {
int operation3 = totalOperations(temp1, temp2);
if (operation3 != -1)
ans = min(ans, 1 + operation3);
}
if (ans == INT_MAX)
return -1;
else
return ans;
}
int main() {
string str1 = "001001111";
string str2 = "011111000";
int ans = minimumOperations(str1, str2);
if (ans == -1){
cout << "S1 to S2 conversion is not possible";
}
else{
cout << "Minimum number of operations required are: " << ans << "\n";
}
return 0;
}
输出
Minimum number of operations required are: 3
时间复杂度 - O(N)，因为我们在stringModification()和totalOperations()函数中遍历字符串。
空间复杂度 - O(1)，因为我们在不使用任何额外空间的情况下修改相同的字符串。
在代码中，我们的主要目的是在修改字符串以最小化操作后，减少给定字符串中01和10对的数量。程序员可以使用各种输入并尝试理解答案。
444 次浏览
