資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在給定二進位制字串中，透過最多翻轉一個'1'來最大化長度為X的0子陣列（使用C++）
在計算機程式設計中，經常需要操作二進位制字串併為各種問題找到最佳解決方案。其中一個問題是在給定的二進位制字串中最大化特定長度X的0子陣列。在我們繼續之前，必須承認存在一個限制——字串只允許修改一個'1'。讓我們深入探討一種有效的C++方法來克服這個障礙。
語法
在深入研究接下來的程式碼之前，務必闡明我們將使用的此方法的語法。
int maxSubarrays(string binaryString, int X);
演算法
以下是最大化長度為X的0子陣列的逐步演算法：
初始化變數：
`n` 為二進位制字串的長度。
`maxZeros` 為0，表示找到的最大零數量。
`currentZeros` 為0，表示當前子陣列中的零數量。
`start` 為0，表示當前子陣列的起始索引。
迭代二進位制字串：
對於從0到n-1的每個索引`i`，執行以下操作：
如果索引'i'處的當前字元為'0'，則將'currentZeros'加1。
如果'currentZeros'超過X，則將'currentZeros'減1，並將'start'索引向前移動，直到'currentZeros'再次變為X。
如果索引`i`處的當前字元為'1'，則檢查是否可以翻轉它：
如果翻轉次數不等於1，則將'currentZeros'加1。
如果翻轉次數等於1，則透過從'i-1'中減去'start'來計算當前子陣列的長度，並在必要時更新'maxZeros'。
將`currentZeros`重置為0，並將`start`更新到下一個索引。
最後，計算最後一個子陣列的長度，並在必要時更新`maxZeros`。
返回`maxZeros`作為長度為X的子陣列中最大零的數量。
方法1：滑動視窗技術
在這種方法中，我們使用滑動視窗來跟蹤子陣列。
我們維護一個大小為X的視窗，並將其沿二進位制字串移動。
透過跟蹤零的數量和翻轉次數，我們可以最大化0子陣列的數量。
示例
#include <iostream>
#include <string>
using namespace std;
int maxSubarrays(string binaryString, int X) {
int n = binaryString.length();
int maxZeros = 0;
int currentZeros = 0;
int start = 0;
for (int i = 0; i < n; i++) {
if (binaryString[i] == '0')
currentZeros++;
else if (currentZeros < X) {
currentZeros++;
} else {
maxZeros = max(maxZeros, i - start);
while (binaryString[start] != '0')
start++;
start++;
}
}
maxZeros = max(maxZeros, n - start);
return maxZeros;
}
int main() {
string binaryString = "110101001011010011";
int X = 3;
int maxZeros = maxSubarrays(binaryString, X);
cout << "Maximum number of zeros in subarrays of length " << X << ": " << maxZeros << endl;
return 0;
}
輸出
Maximum number of zeros in subarrays of length 3: 3
方法2：雙指標技術
在這種方法中，我們使用兩個指標來監控子陣列。
我們的演算法使用一對指標——稱為'left'和'right'——來識別目標子陣列的邊界。
透過根據所選範圍內的翻轉計數和零計數對這些指標進行策略性調整，我們可以增加該範圍的大小，同時保持準確性。
示例
#include <iostream>
#include <string>
using namespace std;
int maxSubarrays(string binaryString, int X) {
int n = binaryString.length();
int maxZeros = 0;
int currentZeros = 0;
int flips = 0;
int left = 0;
int right = 0;
while (right < n) {
if (binaryString[right] == '0') {
currentZeros++;
right++;
} else if (flips < 1) {
currentZeros++;
right++;
flips++;
} else {
maxZeros = max(maxZeros, currentZeros);
while (binaryString[left] != '0') {
currentZeros--;
left++;
}
left++;
flips--;
}
}
maxZeros = max(maxZeros, currentZeros);
return maxZeros;
}
int main() {
string binaryString = "110100111010";
int X = 3;
int maxZeros = maxSubarrays(binaryString, X);
cout << "Maximum number of zeros in subarrays of length " << X << ": " << maxZeros << endl;
return 0;
}
輸出
Maximum number of zeros in subarrays of length 3: 4
結論
在本文中，我們討論了一種有效的方法來最大化給定二進位制字串中特定長度X的0子陣列的數量。透過使用滑動視窗技術或雙指標技術，我們能夠操作字串以找到最佳解決方案。提供的C++程式碼是完全可執行的，可以用來有效地解決這個問題。透過理解和實現這些方法，您可以處理涉及操作二進位制字串和最佳化子陣列的類似問題。
瀏覽量：108
