极客笔记C++ 通过选择二进制字符串中每个‘1’的左边元素来最大化总和
在这个问题中，我们通过从当前‘1’的索引处选择未选择的元素的左边元素来找到数组元素的最大和。
我们可以使用向量列表和sort()方法或优先队列来解决问题。优先队列会按照排序顺序插入元素。
问题陈述 - 给定一个二进制字符串alpha和相同长度的arr[]，我们需要逐个选择alpha中的所有‘1’，并从arr[]的子数组中选择不被选择的最大元素，该子数组由0到p个元素组成。这里，P是二进制字符串中选择的‘1’的索引。我们需要打印这样的数组元素的最大和。
示例示例
输入
alpha = "01010"; arr[] = {30, 40, 3, 7, 20};
输出
70
说明
- 对于第一个索引处的’1’，我们可以选择40。
-
对于第三个索引处的’1’，我们可以选择30。
因此，40和30的和为70。
输入
alpha = "00000"; arr[] = {30, 40, 3, 7, 20};
输出
0
说明 - 二进制字符串中包含全部为0。因此，输出为0的和。
输入
alpha = "00001"; arr[] = {100, 70, 80, 8, 20};
输出结果
100
解释 - 我们将100选择为’1’，因为它位于子数组o到4之间且尚未被选择。
方法1
在这个方法中，我们将继续计算1的数量并将数组元素推送到列表中。同时，我们将对列表进行排序，当我们在二进制字符串中找到’0’时，我们将添加最后计数的元素数量到总和中并从已排序的数组中删除它们。这里，计数是在最后一个零和当前零之间出现的1的数量。
算法
步骤1 - 将’计数’和’数组总和’初始化为零，用于存储两个0之间的1的计数和最大总和的输出。
步骤2 - 同时，定义’numbers’列表以存储数组元素。
步骤3 - 开始遍历字符串。如果二进制字符串中的当前字符是’1’，则将’计数’增加1。
步骤4 - 否则，使用while循环迭代直到’计数’不等于0。在循环中，将最后一个元素添加到’数组总和’中，从列表中删除它，并将’计数’减1。
步骤5 - 将当前元素推送到列表中。
步骤6 - 使用sort()方法对列表进行排序。
步骤7 - 使用while循环迭代直到计数不等于零。在循环中，将数组的最后一个元素添加到数组总和中，并从列表中删除最后一个元素。
步骤8 - 返回数组总和的值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr, string alpha, int len) {
int count = 0, array_sum = 0;
vector<int> numbers;
// Iterate the string
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// Pop all count number of elements from the queue
while (count != 0) {
array_sum += numbers[numbers.size() - 1];
numbers.pop_back();
count--;
}
}
// Insert element to list
numbers.push_back(arr[p]);
// sort the list
sort(numbers.begin(), numbers.end());
}
// If the queue is not empty, then pop the elements and do its sum
while (count != 0) {
array_sum += numbers[numbers.size() - 1];
numbers.pop_back();
count--;
}
// return answer
return array_sum;
}
int main() {
int len = 5;
string alpha = "01010";
int arr[] = {30, 40, 3, 7, 20};
cout << "The maximum sum of array elements according to the given condition is " << getMaximumSum(arr, alpha, len) << endl;
return 0;
}
输出
The maximum sum of array elements according to the given condition is 70
时间复杂度 – O(N*NlogN)，其中O(N)用于遍历字符串，O(NlogN)用于对数组进行排序。
空间复杂度 – O(N)用于在列表中存储数组元素。
第二种方法
在这种方法中，我们将使用优先级队列来保持元素的有序列表。它类似于堆数据结构，在堆中插入非常高效。
我们可以插入元素，它会将元素在排序顺序中设置位置。当我们在二进制字符串中找到’0’时，我们可以从开头弹出元素。
算法
步骤1 - 将’count’和’array_sum’初始化为0。
步骤2 - 开始遍历二进制字符串。如果当前字符是’1’，将’count’增加1。
步骤3 - 如果当前字符是’0’，使用循环从队列中移除count个元素并添加到’array_sum’变量中。
步骤4 - 将当前元素推入队列。
步骤5 - 如果count不为零，从队列中移除count个元素。
步骤6 - 返回’array_sum’值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr, string alpha, int len) {
int count = 0, array_sum = 0;
priority_queue<int> queue;
// Iterate the string
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// Pop all count number of elements from the queue
while (count != 0) {
array_sum += queue.top();
queue.pop();
count--;
}
}
// Insert element to queue
queue.push(arr[p]);
}
// If the queue is not empty, then pop the elements and do its sum
while (count != 0) {
array_sum += queue.top();
queue.pop();
count--;
}
// return answer
return array_sum;
}
int main() {
int len = 5;
string alpha = "01010";
int arr[] = {30, 40, 3, 7, 20};
cout << "The maximum sum of array elements according to the given condition is " << getMaximumSum(arr, alpha, len) << endl;
return 0;
}
输出
The maximum sum of array elements according to the given condition is 70
时间复杂度 – O(N*logN)，其中O(N)用于遍历字符串，O(logN)用于将元素插入队列中。
空间复杂度 – O(N)，用于存储队列中的元素。
在这里，我们使用了列表和队列来解决问题。我们可以观察到队列是多么高效。如果我们需要在每次迭代后对数组进行排序，我们可以使用优先队列。