資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢使左部分 0 的數量和右部分 1 的數量之和最大的分割槽
程式設計需要定期最佳化面向特定結果的演算法。一項基本任務是在 C++ 中識別陣列的分割槽，以最大化完全由左側零和右側一組成的總和。為了獲得解決方案，本文將探討不同的方法以及分步說明和兩個功能程式碼演示。
語法
為了確保我們的讀者能夠輕鬆地跟隨我們的程式碼示例。預先建立一致的語法至關重要。因此，在深入研究演算法和方法之前，讓我們確定這個基本基線。−
#include <iostream>
#include <vector>
using namespace std;
// Function to find partitions with maximum zero and one counts
pair<int, int> findMaxPartition(const vector<int>& arr) {
// Implementation code
}
演算法
以下是我們演算法的分步分解：−
將兩個計數器 zeroCount 和 oneCount 初始化為 0。
將兩個變數 maxZeroCount 和 maxOneCount 初始化為 0。
從左到右遍歷陣列 arr：−
如果元素為 0，則遞增 zeroCount。
如果元素為 1，則遞增 oneCount。
再次從左到右遍歷陣列 arr：−
如果元素為 0，則遞減 zeroCount。
如果元素為 1，則遞減 oneCount。
將 maxZeroCount 更新為 maxZeroCount 和 zeroCount 之間的最大值。
將 maxOneCount 更新為 maxOneCount 和 oneCount 之間的最大值。
返回包含 maxZeroCount 和 maxOneCount 的一個對。
方法 1：貪心演算法
貪心演算法專注於透過僅遍歷一次陣列來查詢左部分中零的最大數量和右部分中一的最大數量。它遵循前面描述的演算法。
示例
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> findMaxPartition(const vector<int>& arr) {
int zeroCount = 0, oneCount = 0;
int maxZeroCount = 0, maxOneCount = 0;
for (int i = 0; i < arr.size(); i++) {
zeroCount += (arr[i] == 0);
oneCount += (arr[i] == 1);
}
for (int i = 0; i < arr.size(); i++) {
zeroCount -= (arr[i] == 0);
oneCount -= (arr[i] == 1);
maxZeroCount = max(maxZeroCount, zeroCount);
maxOneCount = max(maxOneCount, oneCount);
}
return make_pair(maxZeroCount, maxOneCount);
}
int main() {
// Test the findMaxPartition function
vector<int> arr = {0, 1, 0, 1, 1, 0, 0};
pair<int, int> result = findMaxPartition(arr);
cout << "Max Zero Count: " << result.first << endl;
cout << "Max One Count: " << result.second << endl;
return 0;
}
輸出
Max Zero Count: 3 Max One Count: 3
解釋
首先，包含必要的庫：− <iostream> 用於輸入/輸出操作，<vector> 用於使用動態陣列。
using namespace std; 語句允許我們使用標準庫函式和物件，而無需顯式指定 std:: 字首，這增強了程式碼的可讀性。
接下來，定義函式 findMaxPartition。它接受對整數向量的常量引用，表示為 const vector<int>& arr，表示輸入陣列。此函式返回的整數對分別指示零和一的最大數量。
此函式內的宣告涉及四個變數 - zeroCount 和 oneCount 用於分別維護零或一的當前計數的更新，而儲存迄今為止最高計數的記錄則屬於 maxZeroCounts 或 maxOneCounts。
輸入陣列 arr 經歷一個初始迴圈，其中每個元素的值（0 或 1）確定 zeroCount 和 oneCount 變數是否遞增。
第二個迴圈再次遍歷陣列，但這次它遞減 zeroCount 和 oneCount 變數，同時使用迄今為止遇到的最大值更新 maxZeroCount 和 maxOneCount 變數。
迴圈結束後，該函式返回使用 make_pair 建立的一對，其中包含零和一的最大計數。
主函式中的 arr 向量初始化為 {0, 1. 0. 1. 1. 0. 0} 以設定測試用例。此步驟之後，呼叫 findMaxPartition 函式來處理此陣列。此操作的結果隨後作為最大計數對儲存在 result 變數中。
最後，使用 cout 將零和一的最大計數列印到控制檯，確保清晰顯示所需的輸出。
總的來說，此程式碼有效地找到並顯示給定陣列中零和一的最大計數，展示了分割槽最佳化方法的功能。
方法 2：動態規劃方法
動態規劃方法使用記憶化來儲存陣列中每個索引處零和一的計數。透過利用先前計算的值，我們可以找到最大計數。
示例
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> findMaxPartition(const vector<int>& arr) {
int n = arr.size();
vector<int> zeroCount(n + 1, 0);
vector<int> oneCount(n + 1, 0);
for (int i = 1; i <= n; i++) {
zeroCount[i] = zeroCount[i - 1] + (arr[i - 1] == 0);
oneCount[i] = oneCount[i - 1] + (arr[i - 1] == 1);
}
int maxZeroCount = 0, maxOneCount = 0;
for (int i = 0; i < n; i++) {
int zerosLeft = zeroCount[i];
int onesRight = oneCount[n] - oneCount[i];
maxZeroCount = max(maxZeroCount, zerosLeft + onesRight);
maxOneCount = max(maxOneCount, zeroCount[n] - zerosLeft + oneCount[i]);
}
return make_pair(maxZeroCount, maxOneCount);
}
int main() {
// Test the findMaxPartition function
vector<int> arr = {0, 1, 0, 1, 1, 0, 0};
pair<int, int> result = findMaxPartition(arr);
cout << "Max Zero Count: " << result.first << endl;
cout << "Max One Count: " << result.second << endl;
return 0;
}
輸出
Max Zero Count: 4 Max One Count: 5
解釋
findMaxPartition 函式接受對整數向量 arr 的常量引用，並返回一對整數，分別表示零和一的最大計數。
動態規劃在我們的函式中使用，以促進在輸入陣列中每個索引處累積零和一的計數和記錄。為了實現這一點，我們在執行函式時初始化了兩個向量 - zeroCount 和 oneCount。透過分析輸入陣列中的值，我們能夠計算每個索引的這些計數。
接下來，該函式開始遍歷陣列中的每個元素，目標明確：在一定範圍的分割槽內獲得零和一的最大準確計數。為了實現這一點，它計算每個可能分割槽的“zerosLeft”和“onesRight”。最大計數相應地更新。
主函式首先使用特定值 {0 ,1 ,0 ,1 ,1 ,0 ,0} 初始化 arr 向量，這用於建立特定的測試用例。隨後，findMaxPartition 函式以我們最近製作的陣列作為其輸入引數被觸發。作為成功執行此演算法程式的結果，結果最大計數整齊地儲存在一個易於訪問的結果變數中。
最後，使用 cout 將零和一的最大計數列印到控制檯，提供所需的輸出。
此程式碼有效地應用動態規劃方法來解決分割槽問題併產生預期結果。
結論
在本文中，我們探討了兩種在 C++ 中查詢陣列左部分零計數和右部分一計數之和最大的分割槽的方法。貪心演算法透過僅遍歷一次陣列有效地執行任務，而動態規劃方法利用記憶化進行有效計算。最佳化 C++ 中可比較分割槽任務的演算法需要全面理解這兩種方法，並根據具體情況選擇最適合的方法。精心應用此知識的程式設計師將能夠輕鬆實現他們的願景。
49 次瀏覽
