数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
