在二進位字串中，翻轉一對相鄰位元可以輕鬆地從字串中刪除單一 0。然而，當我們需要從二進位字串中刪除所有 0 時，我們可能還需要翻轉不相鄰的位元對。在本文中，我們將討論如何確定從二進位字串中刪除所有 0 所需的非相鄰對翻轉的最小次數。
為了解決這個問題，我們將使用一個簡單的貪心演算法。這個想法是始終選擇彼此相距最遠並且之間至少有一個 0 的一對位。然後我們可以翻轉這兩位，有效地從字串中刪除一個 0。我們重複這個過程，直到所有的 0 都被刪除。
現在讓我們用 C 實作這個演算法。
#include <iostream>
#include <cstring>
using namespace std;
int main() {
string s;
s="100101000";
int n = s.size();
int cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
cnt++;
if (i+2 < n && s[i+2] == '0') {
i += 2;
}
else {
i++;
}
}
}
cout << cnt << endl;
return 0;
}
3
上面的程式碼採用二進位字串作為輸入，並計算從字串中刪除所有 0 所需的非相鄰對翻轉的最小次數。現在讓我們詳細了解程式碼。
首先，我們將二進位字串作為輸入並將其儲存在字串變數「s」中。我們也將字串的大小儲存在整數變數“n”中。
string s; cin >> s; int n = s.size();
接下來，我們初始化變數「cnt」來儲存字串中 0 的數量。然後我們使用 for 循環迭代該字串。對於遇到的每個 0，我們都會增加 0 的計數並檢查接下來的兩位是否也是 0。如果是，我們透過將索引增加 2 來翻轉這對位。否則，我們透過將索引增加 1 來僅翻轉相鄰的位對。
int cnt = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
cnt++;
if (i+2 < n && s[i+2] == '0') {
i += 2;
}
else {
i++;
}
}
}
最後，我們輸出從字串中刪除所有 0 所需的非相鄰對翻轉的計數。
cout << cnt << endl;
讓我們考慮二進位字串「100101000」。可以使用上述演算法計算從該字串中刪除所有 0 所需的非相鄰對翻轉的最小次數。
首先，我們在位置 2 遇到 0。我們翻轉 (1,3) 對以獲得字串「110101000」。然後我們在位置 5 遇到下一個 0。我們翻轉 (1,7) 對以獲得字串「111101000」。然後我們在位置 8 遇到下一個 0。我們翻轉 (1,9) 對以獲得字串「111111000」。現在所有 0 都已從字串中刪除。
從字串中刪除所有 0 所需的非相鄰對翻轉次數為 3。我們可以透過對輸入字串「100101000」運行上述 C 程式碼來驗證這一點。
在本文中，我們討論瞭如何確定從二進位字串中刪除所有 0 所需的非相鄰對翻轉的最小次數。我們使用簡單的貪心演算法來解決這個問題，並用C 程式碼實作。我們還提供了一個範例測試案例來說明演算法的工作原理。
以上是移除二進位字串中所有的0所需的最小非相鄰對翻轉次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
