移除二進位字串中所有的0所需的最小非相鄰對翻轉次數

在二進位字串中，翻轉一對相鄰位元可以輕鬆地從字串中刪除單一 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中文網其他相關文章！