数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使给定二进制字符串相等所需的最小相邻位翻转次数
二进制字符串是指只包含两种不同字符“0”和“1”的字符串。我们将得到两个长度相同的二进制字符串，我们的任务是通过切换第一个字符串的两个相邻字符来使它们相等。此外，我们必须尽可能以最少的步骤来完成此操作。如果不可能将第一个字符串转换为第二个字符串，则返回-1。
示例
输入1
字符串1：101001
字符串2：100110
输出：2
解释 − 我们可以切换第一个字符串的第二个索引字符和相邻的第三个字符，然后我们将得到100101。再次，我们将切换第四个和第五个索引并获得等于给定第二个字符串的字符串。
输入2
字符串1：100
字符串2：011
输出：-1
解释 − 没有办法使两个字符串相等，我们可以切换第零个和第一个索引，并将得到010，然后我们有两个相同的索引，但第三个不同，我们可以得出结论，不可能使第一个字符串等于第二个字符串。
方法
我们已经看到了给定问题的示例，现在让我们来看一下实现给定问题代码的步骤或方法。
首先，我们将创建一个函数，该函数将两个字符串作为参数并返回一个整数。
返回值表示将第一个字符串转换为另一个字符串所需的最小步骤数，或者对于不可能的情况返回-1。
在函数中，首先我们将获得字符串的长度以遍历字符串。
我们将创建一个变量来存储使字符串相等所需的步骤数。
使用for循环，我们将遍历字符串，如果当前索引具有相同的字符，则我们将移动到下一个字符。
我们将切换当前索引和下一个索引的值，并将增加计数。
当我们向前移动并将当前值等于第二个字符串的值时，这意味着两个字符串在倒数第二个索引之前是相等的。
如果两个字符串的最后一个索引相同，则意味着两个字符串最终相等，我们将返回计数。
否则，字符串不可能相等，我们将返回-1。
从主函数中，我们将调用该函数，并根据返回值打印结果。
示例
#include <iostream>
using namespace std;
// function to check if it is possible to make the string equal
int makeEqual(string str1, string str2){
int len = str1.length(); // getting length of the strings
int count = 0; // variable to count the number of steps
// traversing over the string
for(int i=0; i<len-1; i++){
if(str1[i] == str2[i]){
// Both the charcters are the same
continue;
}
else{
count++;
// update the current and the next character
str1[i] = '1' + '0' - str1[i]; // technique to toggle the characters
str1[i+1] = '1' + '0' -str1[i+1];
}
}
// if the last element is the same means the strings are the same
if(str1[len-1] == str2[len-1]){
return count;
}
else{
return -1;
}
}
int main(){
string str1 = "101010"; // given first string
string str2 = "100101"; // given second string
// calling the function to count the minimum steps
// to make the string equal
int steps = makeEqual(str1,str2);
if(steps == -1){
cout<<"It is not possible to make string "<<str1<<" equal to the string "<<str2<<endl;
}
else{
cout<<"We can make string "<< str1<<" equal to string "<<str2<< " in "<<steps<<" number of steps"<<endl;
}
return 0;
}
输出
We can make string 101010 equal to string 100101 in 2 number of steps
时间和空间复杂度
上述代码的时间复杂度为O(N)，其中N是给定字符串的长度。因为我们只遍历字符串一次，所以时间复杂度是线性的。
上述代码的空间复杂度为O(1)，我们在这里没有使用任何额外的空间。
注意 − 在这个问题中，我们被告知两个字符串的长度相等，如果没有给出，那么我们必须在函数中添加一个额外的条件来比较长度，如果长度不同，则我们必须返回-1或不可能。
结论
在本教程中，我们实现了一种方法来检查如果可能的话，我们是否可以在最小移动次数内将一个给定的二进制字符串转换为另一个给定的二进制字符串。我们已经实现了一个具有线性时间复杂度和常数空间复杂度的代码，该代码在给定的相邻元素切换约束下工作。
浏览量：327
