資料結構
網路
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 次檢視
