C++ 中從給定二進位制字串子串中最大化可刪除的少數字符

---

我們當前的任務涉及最大化我們可以刪除任何包含少數字符的出現的次數，這些出現位於完全由“0”或“1”組成的部分中。最終目標只是在仍然遵守所有給定規則和約束的情況下，達到最大可能的刪除次數。

語法

為了全面理解即將到來的程式碼，讓我們首先熟悉將在探索演算法和策略之前採用的方法的語法 -

int maximizeDeletions(string binaryString, int startIndex, int endIndex)

演算法

從給定二進位制字串子串中最大化少數字符刪除的演算法可以用以下步驟描述 -

• 首先，讓我們開始初始化一個名為刪除的變數為零。此變數的主要目的是監控發生的刪除次數。

• 要確定數字“0”和“1”在二進位制字串的特定子串中出現的頻率。可以分別計算這些數字的每個出現次數。

• 為了查明少數字符，我們必須參考上一步中獲得的計數。

• 從子字串中刪除少數字符的所有出現次數，並相應地更新刪除計數。

• 將刪除的最終值作為結果返回

方法 1：遍歷方法

我們方法的執行涉及以線性方式遍歷二進位制字串子串，然後一次性刪除少數字符。

示例

#include <iostream>
#include <algorithm>
using namespace std;

int maximizeDeletionsLinear(string binaryString, int startIndex, int endIndex) {
   int countZero = 0;
   int countOne = 0;

   for (int i = startIndex; i <= endIndex; i++) {
      if (binaryString[i] == '0') {
         countZero++;
      } else {
         countOne++;
      }
   }

   int deletions = endIndex - startIndex + 1 - min(countZero, countOne);
   return deletions;
}

int main() {
   string binaryString;
   int startIndex, endIndex;

   cout << "Enter the binary string: ";
   cin >> binaryString;
   cout << "Enter the start index: ";
   cin >> startIndex;
   cout << "Enter the end index: ";
   cin >> endIndex;

   int deletions = maximizeDeletionsLinear(binaryString, startIndex, endIndex);
   cout << "Maximum deletions: " << deletions << endl;
   
   return 0;
}

輸出

Enter the binary string: 1011010011
Enter the start index: 2
Enter the end index: 8
Maximum deletions: 2

解釋

在方法 1 中，我們利用線性遍歷來最大化從給定二進位制字串子串中刪除少數字符的次數。透過遍歷指定的子串，我們可以識別“0”和“1”在該部分中出現的次數。在查明哪個字元在該區域或組內出現頻率較低（即，找到“少數”）之後，我們可以透過從該指定區域內所有字元的總數中減去其各自的計數來計算可能的刪除次數。

這導致了一種有效的方法，它揭示了簡單而實用的解決方案 - 只需要對我們的初始字串進行一次遍歷 - 使得這種方法特別適合較短的輸入字串。

方法 2：滑動視窗

滑動視窗技術是解決此問題的另一種有效方法。它涉及使用固定大小的視窗遍歷二進位制字串的子串

示例

#include <iostream>
#include <algorithm>
using namespace std;

int maximizeDeletionsSlidingWindow(string binaryString, int startIndex, int endIndex) {
   int left = startIndex;
   int right = startIndex;
   int countZero = 0;
   int countOne = 0;
   int deletions = 0;

   while (right <= endIndex) {
      if (binaryString[right] == '0') {
         countZero++;
      } else {
         countOne++;
      }

      while (min(countZero, countOne) > 0) {
         if (binaryString[left] == '0') {
            countZero--;
         } else {
            countOne--;
         }
         left++;
      }

      deletions = max(deletions, right - left + 1);
      right++;
   }

   return deletions;
}

int main() {
   string binaryString;
   int startIndex, endIndex;

   cout << "Enter the binary string: ";
   cin >> binaryString;
   cout << "Enter the start index: ";
   cin >> startIndex;
   cout << "Enter the end index: ";
   cin >> endIndex;

   int deletions = maximizeDeletionsSlidingWindow(binaryString, startIndex, endIndex);
   cout << "Maximum deletions: " << deletions << endl;

   return 0;
}

輸出

Enter the binary string: Enter the start index: Enter the end index: Maximum deletions: 0

解釋

方法 2 涉及利用滑動視窗技術來最大化少數字符的刪除次數。使用固定大小的視窗，我們遍歷子字串，並在移動視窗時更新“0”和“1”的計數。透過根據計數調整視窗邊界，我們識別少數字符並計算最大可能的刪除次數。這種方法透過有效地滑動視窗減少了冗餘計算的數量，使其更適合較大的輸入並提供更快的解決方案。

結論

在本文中，我們探討了從給定二進位制字串子串中最大化少數字符刪除的問題。我們討論了兩種方法 - 線性遍歷和滑動視窗技術。這兩種方法都提供了有效的解決方案來實現預期的結果。透過理解演算法並研究提供的可執行程式碼示例，您可以將這些概念應用於解決您自己專案中的類似問題。請記住分析問題，選擇最合適的方法，並相應地實施。