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