极客笔记C++ 找到使左侧0的计数和右侧1的计数之和最大化的分割
编程需要定期优化针对特定结果的算法。其中一个基本任务是在C++中识别数组的分区，以最大化完全由左侧的0和右侧的1组成的和。为了找到解决方案，本文将在逐步说明和两个功能代码演示的同时，对不同的方法进行概述。
语法
为了确保读者可以方便地按照我们的代码示例进行操作，我们需要事先确定一致的语法。因此，在介绍算法和方法之前，让我们确定这个重要的基线。
#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
}
步骤
这是我们算法的分步解析：
- 将零计数器和一计数器初始化为0。
-
将最大零计数和最大一计数初始化为0。
-
从左到右遍历数组arr-
-
如果元素为0，则将零计数加1。
-
如果元素为1，则将一计数加1。
-
再次从左到右遍历数组arr-
-
如果元素为0，则将零计数减1。
-
如果元素为1，则将一计数减1。
-
将最大零计数更新为maxZeroCount和zeroCount之间的最大值。
-
将最大一计数更新为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的常量引用，并返回一个表示最大的0和1数量的整数对。
我们的函数在其内部使用动态规划来便于计算和记录输入数组中每个索引处的累积0和1的数量。为了实现这一点，我们在执行函数时初始化了两个向量- zeroCount和oneCount。通过分析输入数组中的值，我们能够计算出每个索引的这些数量。
接下来，函数开始迭代数组中的每个元素，目的是获得一定范围内最大的0和1的准确计数。为了实现这一点，它计算了每个可能分区的“左侧零数”和“右侧1数”。最大计数相应地更新。
主函数首先使用特定值{0，1，0，1，1，0，0}初始化arr向量，这将建立一个特定的测试案例。随后，findMaxPartition函数以我们最近创建的数组作为其输入参数被触发。作为成功运行此算法程序的产物，所得的最大计数被整齐地存储在一个容易访问的result变量中。
最后，使用cout将最大的0和1的计数打印到控制台上，提供期望的输出。
这段代码有效地应用了动态规划方法来解决分区问题，并产生了预期的结果。
结论
在本文中，我们探讨了在C++中找到使左侧部分的零计数之和和右侧部分的一计数之和最大的分区的两种方法。贪婪的方法通过仅对数组迭代一次来高效地完成任务，而动态规划方法利用记忆化进行高效的计算。对于在C++中优化类似分区任务的算法，需要全面了解这两种方法，并根据个体情况选择最适合的方法。细致应用这些知识的程序员将能够轻松实现他们的愿景。