在 C++ 中查找最大化左侧部分 0 的数量和右侧部分 1 的数量的分区
编程需要定期优化面向特定结果的算法。一项基本任务是识别 C++ 中数组的分区，以最大化完全由左侧零和右侧一组成的总和。为了找到解决方案，本文将调查不同的方法以及分步说明和两个功能代码演示。
语法
为了确保我们的读者能够轻松跟随我们的代码示例。我们必须预先建立一致的语法。因此，在进入算法和方法之前，让我们确定这个基本基线。−
#include <iostream>
#include <vector>
using namespace std;
// 用于查找具有最大零和一计数的分区的函数
pair<int, int> findMaxPartition(const vector<int>& arr) {
// 实现代码
}
算法
下面是算法的分步分解 −
将两个计数器 zeroCount 和 oneCount 初始化为 0。
将两个变量 maxZeroCount 和 maxOneCount 初始化为 0。
从左到右遍历数组 arr −
如果元素为 0，则增加 zeroCount。
如果元素为 1，则增加 oneCount。
再次从左到右遍历数组 arr −
如果元素为0。
如果元素为 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() {
// 测试 findMaxPartition 函数
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 函数来处理此数组。然后将此操作的结果作为一对最大计数存储在结果变量中。
最后，使用 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() {
// 测试 findMaxPartition 函数
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++ 中可比分区任务的算法需要全面理解这两种方法，并根据具体情况选择最适合的方法。认真运用这些知识的程序员将能够轻松实现他们的愿景。
