二進位制字串中移除所有 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++ 程式碼實現了它。我們還提供了一個示例測試用例來說明演算法的工作原理。

更新於: 2023年5月18日

158 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

立即開始
廣告