最大化在給定的二進位字串子字串中可以刪除的少數字元數量，使用C++實現

Our current undertaking involves maximizing the number by which we can delete any occurrences containing the minority character(s) within a section comprised entirely by either '0' or '1'. goal is simply to reach maximum possible deletions while still respecting all given rules and constraints.

Syntax

To ensure a comprehensive understanding of the upcoming codes let us first familiarize ourselves with the syntax of the method that will be employed before exploring the algorithm and strategies −

#

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

Algorithm

最大化給定二進位字串子字串中少數字元刪除的演算法可以透過以下步驟描述：

• 首先，讓我們先將一個名為 deletions 的變數初始化為零來開始。這個變數的主要目的是監控發生的刪除操作的計數。

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

• To pinpoint the minority character(s), we must refer to the counts obtained in the previous step.

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

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

方法一：遍歷方法

The execution of our approach involves traversing through the binary strings substring in a linear fashion and then deleting the minority character(s) all at once.

Example

的中文翻譯為：

範例

#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

Explanation

在方法1中，我們利用線性遍歷來最大化從給定二進位字串子字串中刪除少數字元的數量。透過遍歷指定的子字串，我們可以確定在該部分內每個實例的'0'和'1'出現的次數。在確定該區域或群組內較少頻繁出現的字元（即找到"少數派"）之後，我們可以透過從該指定區域內所有字元的計數中減去它們各自的計數來計算可能的刪除次數。

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

方法二：滑動視窗

The sliding window technique is another efficient approach to solve this problem. It involves using a window of fixed size to traverse the substring of the binary string

Example

的中文翻譯為：

範例

#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

Explanation

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

結論

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

以上是最大化在給定的二進位字串子字串中可以刪除的少數字元數量，使用C++實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！