資料結構
網路
關係資料庫管理系統 (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
